تحليل الأسئلة والأجوبة من المقابلات لمطور جافا. الجزء 9

الألعاب النارية! أن تكون مبرمجًا ليس بالأمر السهل. عليك أن تتعلم باستمرار، وأن تتعلم دائمًا شيئًا جديدًا. ولكن، كما هو الحال في أي عمل آخر، فإن أصعب شيء هو البدء، واتخاذ الخطوة الأولى نحو هدفك. وبما أنك جالس على هذا الموقع وتقرأ هذا المقال، فقد أكملت الخطوة الأولى. هذا يعني أنك الآن بحاجة إلى التحرك بشكل هادف نحو هدفك، دون التباطؤ أو التوقف على طول الطريق. إذا فهمت بشكل صحيح، فإن هدفك هو أن تصبح مطور Java أو تعزيز معرفتك إذا كنت واحدًا. إذا كان الأمر كذلك، فأنت في المكان الصحيح، لأننا سنستمر في تحليل قائمة واسعة تضم أكثر من 250 سؤالًا لمقابلة مطوري Java. فلنكمل!

المجموعات

84. أخبرنا عن التكرارات واستخدامها

تعد المجموعات أحد الموضوعات المفضلة في أي مقابلة لمطوري Java، وعند الحديث عن التسلسل الهرمي للمجموعات، غالبًا ما يقول المرشحون إنها تبدأ بواجهة المجموعة . ولكن هذا ليس صحيحا، لأنه فوق هذه الواجهة هناك واجهة أخرى - Iterable . تمثل هذه الواجهة طريقة iterator() ، والتي تسمح لك باستدعاء كائن Iterator للمجموعة الحالية. وما هو كائن Iterator هذا بالضبط ؟ التكرار هو كائن يوفر القدرة على التنقل عبر مجموعة والتكرار على العناصر دون أن يحتاج المستخدم إلى معرفة تنفيذ مجموعة معينة. وهذا هو، هذا هو نوع من المؤشر لعناصر المجموعة، والتي تبدو وكأنها مكان معين فيها. يحتوي المكرر على الطرق التالية:

• hasNext() - يُرجع صحيحًا إذا كان هناك عنصر يقع بعد المؤشر (تسمح لك هذه الطريقة بمعرفة ما إذا كان قد تم الوصول إلى نهاية المجموعة)؛
• next() - يُرجع العنصر التالي بعد المؤشر. إذا لم يكن هناك أي شيء، فسيتم طرح NoSuchElementException . أي أنه من الأفضل التأكد من وجود العنصر قبل استخدام هذه الطريقة - باستخدام hasNext() ;
• إزالة () - إزالة العنصر الأخير المستلم من المجموعة باستخدام الطريقة التالية () . إذا لم يتم استدعاء next() مطلقًا قبل استدعاء إزالة() ، فسيتم طرح استثناء - IllegalStateException ؛
• forEachRemaining(<Consumer>) - ينفذ الإجراء الذي تم تمريره مع كل عنصر من عناصر المجموعة (ظهرت الطريقة في Java 8).

فيما يلي مثال صغير للتكرار عبر قائمة وإزالة جميع عناصرها باستخدام طرق التكرار التي تمت مناقشتها:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

ستعرض وحدة التحكم: وهذا يعني أن إزالة العناصر كانت ناجحة. بمجرد حصولنا على مُكرِّر، يمكننا استخدام طريقة لطباعة جميع العناصر على الشاشة:

iterator.forEachRemaining(x -> System.out.print(x));

ولكن بعد ذلك، سيصبح المُكرِّر غير مناسب لمزيد من الاستخدام، لأنه سيجتاز القائمة بأكملها، ولا يمتلك المُكرِّر العادي طرقًا للتراجع. نحن هنا نقترب تدريجيًا من LinkedList ، أي طريقة listIterator() الخاصة به ، والتي تُرجع نوعًا حديثًا من المكرر - ListIterator . بالإضافة إلى طرق التكرار العادية (القياسية)، تحتوي هذه الطريقة على طرق إضافية:

• add(<Element>) - يُدرج عنصرًا جديدًا في القائمة؛
• hasPrevious() - تُرجع صحيحًا إذا كان هناك عنصر يقع قبل المؤشر (سواء كان هناك عنصر سابق)؛
• nextIndex() - يُرجع الفهرس في قائمة العنصر التالي بعد المؤشر؛
• السابق () - يُرجع العنصر السابق (حتى المؤشر)؛
• PreviousIndex() - يُرجع فهرس العنصر السابق؛
• set(<Element>) - يستبدل العنصر الأخير الذي تم إرجاعه بواسطة الطرق التالية () أو السابقة () .

كما ترون، فإن وظيفة هذا المكرر أكثر إثارة للاهتمام: فهو يسمح لك بالتحرك في كلا الاتجاهين وتحرير يديك عند العمل مع العناصر. أيضًا، عندما يتحدث الناس عن المُكرِّرات، فإنهم يقصدون أحيانًا النمط نفسه. لتجنب الوقوع في المشاكل والحديث عنها بشكل مقنع، اقرأ هذا المقال عن نمط التكرار .

85. ما هو التسلسل الهرمي للمجموعة في Java Collection Framework؟

هناك نوعان من التسلسلات الهرمية للمجموعات في Java. التسلسل الهرمي الأول هو التسلسل الهرمي للمجموعات نفسها مع البنية التالية: وهي بدورها مقسمة إلى المجموعات الفرعية التالية:

• المجموعة عبارة عن واجهة تصف بنية البيانات كمجموعة تحتوي على عناصر فريدة غير مرتبة (غير متكررة). تحتوي الواجهة على تطبيقات قياسية - TreeSet و HashSet و LinkedHashSet .
• القائمة عبارة عن واجهة تصف بنية البيانات التي تخزن تسلسلًا مرتبًا للكائنات. يمكن إدراج المثيلات الموجودة في القائمة وحذفها بواسطة فهرسها في هذه المجموعة (مماثل للمصفوفة، ولكن مع تغيير الحجم الديناميكي). تحتوي الواجهة على تطبيقات قياسية - ArrayList و Vector ( التي تعتبر قديمة وغير مستخدمة فعليًا ) و LinkedList .
• قائمة الانتظار عبارة عن واجهة تصف بنية البيانات التي تخزن العناصر في شكل قائمة انتظار تتبع قاعدة FIFO - أول ما يدخل أولاً يخرج . تحتوي الواجهة على التطبيقات القياسية التالية: LinkedList (نعم، إنها تنفذ قائمة الانتظار أيضًا) و PriotityQueue .

التسلسل الهرمي الثاني للمجموعات هو Map ، الذي يحتوي على البنية التالية: في هذه المجموعة لا توجد أقسام إلى مجموعات فرعية (نظرًا لأن التسلسل الهرمي للخريطة نفسه يشبه مجموعة فرعية، ولكنه يقع بشكل منفصل). تطبيقات الخريطة القياسية هي Hashtable (تعتبر مهملة) و LinkedHashMap و TreeMap . في الواقع، عند السؤال عن Collection ، عادةً ما يُقصد كلا التسلسلين الهرميين.

86. ما هو الهيكل الداخلي لقائمة ArrayList؟

ArrayList يشبه المصفوفة، ولكن مع إمكانية التوسع ديناميكيًا. ماذا يعني ذلك؟ الحقيقة هي أن ArrayList يعمل على أساس مصفوفة عادية، أي أنه يخزن العناصر في مصفوفة داخلية (حجمها الافتراضي هو 10 خلايا). عندما يمتلئ المصفوفة الداخلية، يتم إنشاء مصفوفة جديدة، يتم تحديد حجمها بواسطة الصيغة:

<размерТекущегоМассива> * 3 / 2  + 1

أي أنه إذا كان حجم المصفوفة لدينا هو 10، فسيكون حجم المصفوفة الجديدة: 10 * 3 / 2 + 1 = 16. بعد ذلك، يتم نسخ كافة القيم من المصفوفة الأولى (القديمة) إليها باستخدام الأمر طريقة System.arraycopy () الأصلية ، ويتم حذف المصفوفة الأولى. في الواقع، هذه هي الطريقة التي يتم بها تنفيذ التوسعة الديناميكية لـ ArrayList . دعونا نلقي نظرة على أساليب ArrayList الأكثر استخدامًا : 1. add(<Elelement>) - يضيف عنصرًا إلى نهاية المصفوفة (إلى آخر خلية فارغة)، ويتحقق أولاً مما إذا كانت هناك مساحة في هذه المصفوفة. إذا لم يكن هناك، فسيتم إنشاء مصفوفة جديدة يتم نسخ العناصر إليها. التعقيد اللوغاريتمي لهذه العملية هو O(1). هناك طريقة مشابهة - add(<Index>,<Elelement>) . فهو يضيف عنصرًا ليس إلى نهاية القائمة (المصفوفة)، بل إلى خلية معينة تحتوي على الفهرس الذي يأتي كوسيطة. في هذه الحالة، سيختلف التعقيد اللوغاريتمي اعتمادًا على مكان إضافته:

• إذا كانت هذه بداية القائمة تقريبًا، فسيكون التعقيد اللوغاريتمي قريبًا من O(N)، لأن جميع العناصر الموجودة على يمين العنصر الجديد يجب نقلها خلية واحدة إلى اليمين؛
• إذا تم إدراج العنصر في المنتصف - O(N/2) لأن نحن بحاجة إلى نقل نصف عناصر القائمة فقط خلية واحدة إلى اليمين.

أي أن التعقيد اللوغاريتمي لهذه الطريقة يتراوح من O(N) إلى O(1) اعتمادًا على مكان إدراج العنصر. 2.set (<Index>,<Elelement>) - يكتب عنصرًا إلى الموضع المحدد في القائمة. إذا كان هناك بالفعل عنصر في هذا الموضع، فقم بالكتابة فوقه. التعقيد اللوغاريتمي لهذه العملية هو O(1)، لأنه لا توجد تحولات: فقط البحث عن طريق الفهرس في المصفوفة، والتي، كما نتذكر، لديها تعقيد O(1)، وكتابة العنصر. 3.remove (<index>) - إزالة عنصر حسب فهرسه في المصفوفة الداخلية. عند حذف عنصر غير موجود في نهاية القائمة، يجب عليك نقل جميع العناصر إلى يمينه خلية واحدة إلى اليسار لسد الفجوة المتبقية بعد حذف العنصر. ولذلك، فإن التعقيد اللوغاريتمي سيكون هو نفسه add(<Index>,<Elelement>) إذا كان العنصر في المنتصف - O(N/2) - لأنك تحتاج إلى نقل نصف العناصر واحدًا إلى اليسار. وبناء على ذلك، إذا كان في البداية - O(N). حسنًا، إذا كان O(1) في النهاية، فلا داعي لتحريك أي شيء. بالنسبة لأولئك الذين يريدون التعمق في هذا الموضوع، سأترك هذا الرابط لمقال مع تحليل فئة ArrayList .

87. ما هو الهيكل الداخلي للLinkedList؟

إذا كانت ArrayList تحتوي على عناصر في مصفوفة داخلية، فإن LinkedList تكون في شكل قائمة مرتبطة بشكل مزدوج. وهذا يعني أن كل عنصر يحتوي على رابط للعنصر السابق ( السابق ) والعنصر التالي ( التالي ). العنصر الأول ليس له رابط للعنصر السابق (هو الأول)، لكنه يعتبر رأس القائمة، والقائمة المرتبطة لها رابط مباشر إليها. العنصر الأخير، في الواقع، ليس له عنصر تالي، فهو ذيل القائمة، وبالتالي يوجد رابط مباشر إليه في LinkedList نفسها . ولذلك، فإن التعقيد اللوغاريتمي للوصول إلى رأس القائمة أو ذيلها هو O(1). في ArrayList، عندما نمت القائمة، زاد المصفوفة الداخلية، ولكن هنا يحدث كل شيء ببساطة أكثر - عند إضافة عنصر، يتغير زوج من الروابط ببساطة. دعونا نلقي نظرة على بعض طرق LinkedlList الأكثر استخدامًا : 1. add(<Elelement>) - الإضافة في نهاية القائمة، أي: بعد العنصر الأخير (5) سيتم إضافة رابط للعنصر الجديد على النحو التالي . سيكون للعنصر الجديد رابط للعنصر الأخير (5) كالعنصر السابق . سيكون التعقيد اللوغاريتمي لمثل هذه العملية هو O(1)، نظرًا لأن هناك حاجة فقط إلى رابط للعنصر الأخير، وكما تتذكر، يحتوي الذيل على رابط مباشر من LinkedList والتعقيد اللوغاريتمي للوصول إليه ضئيل. 2. add(<Index>,<Elelement>) - إضافة عنصر حسب الفهرس. عند إضافة عنصر، على سبيل المثال، إلى منتصف القائمة، يتم تكرار العناصر من الرأس والذيل (على كلا الجانبين) أولاً حتى يتم العثور على المكان المطلوب. إذا أردنا إدراج عنصر بين العنصر الثالث والرابع (في الشكل أعلاه)، فعند البحث عن المكان الصحيح، سيشير الرابط التالي للعنصر الثالث بالفعل إلى العنصر الجديد. بالنسبة للرابط الجديد، فإن الرابط السابق سيشير إلى الرابط الثالث. وعليه، فإن رابط العنصر الرابع - السابق - سيشير بالفعل إلى العنصر الجديد، وسيشير الرابط التالي للعنصر الجديد إلى العنصر الرابع: وسيعتمد التعقيد اللوغاريتمي لهذه الطريقة على الفهرس المعطى للعنصر الجديد:

• إذا كان قريبًا من الرأس أو الذيل، فسوف يقترب من O(1)، لأنه لن يكون من الضروري فعليًا التكرار على العناصر؛
• إذا كان قريبًا من المنتصف، فسيتم فرز العناصر من الرأس والذيل في وقت واحد حتى يتم العثور على العنصر المطلوب.

3.set (<Index>,<Elelement>) - يكتب عنصرًا إلى الموضع المحدد في القائمة. سيتراوح التعقيد اللوغاريتمي لهذه العملية من O(1) إلى O(N/2)، مرة أخرى اعتمادًا على مدى قرب العنصر من الرأس أو الذيل أو المنتصف. 4.remove (<index>) - يزيل عنصرًا من القائمة، مما يجعل العنصر الذي يأتي قبل العنصر الذي تتم إزالته ( السابق ) يشير إلى العنصر الذي يأتي بعد العنصر الذي تتم إزالته ( التالي ). والعكس صحيح: بحيث يكون العنصر الذي يأتي بعد العنصر المحذوف يشير إلى العنصر الذي يأتي قبل العنصر المحذوف: والنتيجة هي عملية عكسية للإضافة بواسطة الفهرس ( add(<Index>,<Elelement>) ). بالنسبة لأولئك الذين يرغبون في معرفة المزيد عن البنية الداخلية لـ LinkedList ، أوصي بقراءة هذا المقال .

88. ما هو الهيكل الداخلي لـ HashMap؟

ربما يكون أحد الأسئلة الأكثر شيوعًا عند إجراء مقابلة مع مطور Java. يعمل HashMap v مع أزواج القيمة الرئيسية . كيف يتم تخزينها داخل HashMapv نفسها ؟ يوجد داخل HashMap مجموعة من العقد:

Node<K,V>[] table

افتراضيًا، حجم المصفوفة هو 16، ويتضاعف في كل مرة يتم ملؤها بالعناصر (عند الوصول إلى LOAD_FACTOR - نسبة معينة من الامتلاء، تكون افتراضيًا 0.75 ). تقوم كل عقدة بتخزين تجزئة المفتاح، ومفتاح، وقيمة، ورابط إلى العنصر التالي: في الواقع، "رابط إلى العنصر التالي" يعني أننا نتعامل مع قائمة مرتبطة بشكل فردي، حيث يحتوي كل عنصر على رابط إلى التالي. أي أن HashMap يخزن البيانات في مجموعة من القوائم المرتبطة بشكل فردي. لكنني سألاحظ على الفور: عندما تحتوي خلية واحدة من مصفوفة الجدول على رابط لقائمة مرتبطة منفردة مماثلة تتكون من أكثر من عنصر واحد، فهذا ليس جيدًا. وتسمى هذه الظاهرة الاصطدام . ولكن أول الأشياء أولا. دعونا نرى كيف يتم حفظ زوج جديد باستخدام طريقة الوضع . أولاً، يتم أخذ hachCode() للمفتاح. لذلك، لكي يعمل hashmap بشكل صحيح ، عليك أن تأخذ دروسًا يتم فيها تجاوز هذه الطريقة كمفاتيح. يتم بعد ذلك استخدام رمز التجزئة هذا في الطريقة الداخلية - hash() - لتحديد الرقم الموجود ضمن حجم مصفوفة الجدول . بعد ذلك، باستخدام الرقم المستلم، يتم الوصول إلى خلية معينة من مصفوفة الجدول . وهنا لدينا حالتان:

1. الخلية فارغة - يتم تخزين قيمة العقدة الجديدة فيها .
2. الخلية ليست فارغة - تتم مقارنة قيمة المفاتيح. إذا كانت متساوية، فإن قيمة العقدة الجديدة تحل محل القيمة القديمة، وإذا لم تكن متساوية، فسيتم الوصول إلى العنصر التالي ومقارنته بمفتاحه... وهكذا حتى تحل القيمة الجديدة محل القيمة القديمة أو تصل إلى نهاية العنصر قائمة مرتبطة بشكل فردي وسيتم تخزينها هناك كعنصر أخير.

عند البحث عن عنصر بالمفتاح ( طريقة get(<key>) )، يتم حساب رمز التجزئة للمفتاح، ثم قيمته داخل المصفوفة باستخدام hash() ، وباستخدام الرقم الناتج يتم العثور على خلية مصفوفة الجدول ، حيث يتم إجراء البحث بالفعل عن طريق تعداد العقد ومقارنة مفتاح العقدة المطلوبة بمفتاح العقدة الحالية. العمليات في الخريطة، في الوضع المثالي، لها تعقيد خوارزمي O(1)، لأنها تصل إلى مصفوفة، وكما تتذكر، بغض النظر عن عدد العناصر، فإن العمليات على المصفوفة لها تعقيد O(1) . ولكن هذا مثالي. عندما لا تكون خلية المصفوفة المستخدمة فارغة (2) ويوجد بالفعل بعض العقد هناك، يتحول التعقيد الخوارزمي إلى خطي O(N)، لأنه من الضروري الآن التكرار على العناصر قبل العثور على المكان الصحيح. لا يسعني إلا أن أذكر هذا: بدءًا من Java 8، إذا كانت عقدة القائمة المرتبطة بشكل فردي تحتوي على أكثر من 8 عناصر (تصادمات)، فإنها تتحول إلى شجرة ثنائية. في هذه الحالة، لن يكون التعقيد الخوارزمي هو O(N)، ولكن O(log(N)) - هذه مسألة أخرى، أليس كذلك؟ يعد HashMap موضوعًا كبيرًا، ويحب الأشخاص طرح أسئلة حوله في المقابلات. لذلك أنصحك بفهمها بالتفصيل (حتى ترتد عن أسنانك). أنا شخصياً لم أجري مقابلة بدون أسئلة HashMap . يمكنك العثور على نظرة عميقة حول HashMap في هذه المقالة . هذا كل ما لدينا اليوم، يتبع..