ما قد يسألونه في المقابلة: هياكل البيانات في Java. الجزء 2

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

6. أخبرنا عن القائمة

القائمة هي واجهة تمثل بنية مرتبة من الكائنات، والتي تسمى القائمة. "الخدعة" في هذه البنية هي أن العناصر الموجودة في القائمة يمكن إدراجها أو تعديلها أو حذفها بواسطة الفهرس، أي المعرف الداخلي للقائمة . بمعنى آخر، الفهرس يعني: "كم عدد العناصر الموجودة في بداية القائمة". يحتوي عنصر القائمة الأول على فهرس 0، والثاني يحتوي على فهرس 1، وهكذا. إذن العنصر الخامس يبعد أربعة عناصر عن بداية القائمة. كما ذكر أعلاه، فإن الترتيب الذي تتم به إضافة العناصر إلى القائمة مهم. لهذا السبب تسمى بنية البيانات بالقائمة . ندرج الطرق الفريدة لهذه البنية والتي تهدف إلى العمل مع العناصر حسب الفهرس:

• الحصول على - إرجاع العنصر في الموضع المحدد (حسب قيمة الفهرس)،
• إزالة - إزالة العنصر في الموضع المحدد،
• set - يستبدل العنصر في الموضع المحدد بالعنصر المحدد في الطريقة.

التطبيقات الرئيسية هي ArrayList و LinkedList . سنتحدث أكثر عنهم بعد قليل. Vector عبارة عن قائمة آمنة لمؤشر الترابط، لذا تتم مزامنة كل طريقة في هذه الفئة. لكن ضع في اعتبارك أنه إذا كنت تريد تأمين بعض إجراءات القائمة، فسوف تقوم بمزامنة سلسلة كاملة من العمليات. وتعد مزامنة العمليات الفردية أقل أمانًا وأبطأ بكثير. بالطبع، لدى Vector أيضًا قفل علوي، حتى لو لم تكن بحاجة إلى القفل. لذلك، تعتبر هذه الفئة الآن قديمة وغير مستخدمة. بالمناسبة: ArrayList يشبه Vector ، لكنه لا يستخدم القفل، لذلك يتم استخدامه في كل مكان. Stack هي فئة فرعية من فئة Vector مع مُنشئ افتراضي واحد وجميع توابع الفئة Vector ، بالإضافة إلى عدد قليل من التوابع الخاصة بها (سنتحدث عنها لاحقًا). على سبيل المثال، يمكنك تخيل العملية كمجموعة من المجلدات مع المستندات. يمكنك وضع مجلد واحد في أعلى المكدس، ويمكنك فقط أخذ هذه المجلدات بترتيب عكسي، بدءًا من الأعلى. في الواقع، هذه آلية من نوع LIFO ، أي آخر من يدخل أولاً يخرج ، وآخر من يأتي هو أول من يغادر. ينفذ المكدس أساليبه الخاصة:

• دفع - يضيف العنصر الذي تم تمريره إلى أعلى المكدس؛
• نظرة خاطفة - إرجاع العنصر الموجود في الجزء العلوي من المكدس؛
• البوب ​​- يقوم أيضًا بإرجاع العنصر الموجود أعلى المكدس، ولكنه يقوم بإزالته؛
• فارغ - يتحقق مما إذا كانت المكدس فارغة - صحيحة أم لا - خاطئة ؛
• بحث - يبحث في المكدس عن عنصر معين. إذا تم العثور على عنصر، فسيتم إرجاع رقم التسلسل الخاص به بالنسبة إلى الجزء العلوي من المكدس. إذا لم يتم العثور على العنصر، فسيتم إرجاع القيمة -1.

في الوقت الحالي، لا يتم استخدام فئة Stack الفرعية فعليًا نظرًا لبساطتها وعدم مرونتها، ولكن مع ذلك، قد تواجهها. على سبيل المثال، عندما تتلقى بعض الأخطاء وترى في وحدة التحكم مجموعة من الرسائل حول هذا الموضوع. يمكنك قراءة المزيد عن المكدس وقائمة الانتظار في هذه المقالة .

7. أخبرنا عن الخريطة

كما هو مذكور أعلاه، الخريطة عبارة عن مجموعة تحتوي على بنية منفصلة للواجهات وتطبيقاتها. وهو منفصل لأنه هنا لا يتم تخزين القيم واحدة تلو الأخرى، ولكن في زوج "القيمة الرئيسية". طرق الخريطة الأساسية :

• put(مفتاح K، قيمة V) - إضافة عنصر إلى الخريطة؛
• الحصول على (مفتاح الكائن) - البحث عن قيمة بالمفتاح؛
• يحتوي على مفتاح (مفتاح الكائن) - يتحقق من وجود هذا المفتاح على الخريطة؛
• يحتوي على قيمة (قيمة الكائن) - يتحقق من وجود هذه القيمة في الخريطة؛
• إزالة (مفتاح الكائن) - إزالة القيمة بواسطة مفتاحها.

كما ترون، معظم العمليات تعمل باستخدام مفتاح. كقاعدة عامة، يتم اختيار الكائنات غير القابلة للتغيير كمفاتيح . والمثال النموذجي لهذا الكائن هو String . تطبيقات الخريطة الأساسية :

1. HashMap - مصمم لتخزين القيم بترتيب عشوائي، ولكنه يسمح لك بالبحث بسرعة عن عناصر الخريطة. يسمح لك بتحديد مفتاح باستخدام الكلمة الأساسية null ، ولكن ليس أكثر من مرة، لأن تتم كتابة الأزواج التي لها نفس المفاتيح فوق بعضها البعض. الشرط الرئيسي هو تفرد المفاتيح: يمكن تكرار القيم (قد يكون هناك عدة قيم فارغة).
2. LinkedHashMap هو نظير لـ HashMap يقوم بتخزين القيم بالترتيب الذي تمت إضافتها به. وفقًا لذلك، مثل LinkedList ، فهو يحتوي على رأس - رأس قائمة مرتبطة بشكل مضاعف. عند التهيئة، فإنه يشير إلى نفسه.

   يحتوي LinkedHashMap أيضًا على AccessOrder الذي يحدد كيفية الوصول إلى العناصر عند استخدام المكرر. إذا كانت قيمة AccessOrder خاطئة، فسيتم تنفيذ الوصول بالترتيب الذي تم به إدراج العناصر. إذا كان هذا صحيحًا، فستكون العناصر في آخر ترتيب تم الوصول إليه (سيتم وضع آخر عنصر تم الوصول إليه في النهاية).

3. TreeMap عبارة عن خريطة تقوم بفرز العناصر حسب القيم الأساسية. مشابه لـ TreeSet ، ولكن للأزواج بناءً على القيم الأساسية. لتعيين قواعد فرز TreeMap ، يجب أن تقوم المفاتيح بتنفيذ الواجهة القابلة للمقارنة . بخلاف ذلك، يجب أن يكون هناك مقارن موجه نحو المفتاح (الذي تم تحديده في مُنشئ TreeMap )، وTreeSet - يتم تنفيذه باستخدام كائن TreeMap بداخله، والذي يحدث فيه كل السحر في الواقع.

   يمكنك قراءة المزيد حول الفرز في TreeMap باستخدام الأشجار ذات اللون الأحمر والأسود في المقالة حول ميزات TreeMap .

4. يشبه Hashtable HashMap ، ولكنه لا يسمح بتخزين القيم الخالية كمفاتيح أو قيم. تتم مزامنتها بعناية من وجهة نظر متعددة الخيوط، وهذا بدوره يعني أنها آمنة من وجهة نظر متعددة الخيوط. لكن هذا التنفيذ قديم وبطيء، لذا لن ترى الآن Hashtable في المشاريع الجديدة تقريبًا.

8. ArrayList مقابل LinkedList. أيهما أفضل للاستخدام؟

ربما يكون هذا السؤال هو الأكثر شيوعًا في هياكل البيانات ويحمل في طياته بعض المخاطر. قبل الإجابة عليه، دعونا نتعلم المزيد عن هياكل البيانات هذه. يقوم ArrayList بتنفيذ واجهة القائمة ويعمل على مصفوفة داخلية يتم توسيعها حسب الحاجة. عندما تمتلئ المصفوفة الداخلية بالكامل، ويلزم إدراج عنصر جديد، يتم إنشاء مصفوفة جديدة بحجم (oldSize * 1.5) +1. بعد ذلك، يتم نسخ جميع البيانات من المصفوفة القديمة إلى العنصر الجديد + الجديد، وسيتم حذف العنصر القديم بواسطة أداة تجميع البيانات المهملة . يضيف أسلوب الإضافة عنصرًا إلى آخر خلية فارغة في المصفوفة. وهذا يعني أنه إذا كان لدينا بالفعل 3 عناصر هناك، فستضيف العنصر التالي إلى الخلية الرابعة. دعنا نستعرض أداء الطرق الأساسية:

• get(int Index) - أخذ عنصر في صفيف حسب الفهرس هو الأسرع في O(1) ؛
• add(Object obj) - إذا كانت هناك مساحة كافية في المصفوفة الداخلية لعنصر جديد، فسيتم إنفاق وقت الإدراج العادي O(1) ، نظرًا لأن الإضافة تستهدف الخلية الأخيرة.

  إذا أردنا إنشاء مصفوفة جديدة ونسخ محتوياتها، فسيكون وقتنا متناسبًا بشكل مباشر مع عدد العناصر في المصفوفة O(n) ؛

• إزالة (int Index) - عند إزالة عنصر، على سبيل المثال، من المنتصف، سنحصل على وقت O(n/2)، حيث سنحتاج إلى نقل العناصر الموجودة على يمينه خلية واحدة إلى الخلف. وعليه، إذا تم الحذف من بداية القائمة، فإن O(n)، من النهاية - O(1);
• add(int Index, Object obj) - موقف مشابه للحذف: عند الإضافة إلى المنتصف، سنحتاج إلى نقل العناصر الموجودة على اليمين إلى خلية واحدة للأمام، وبالتالي فإن الوقت هو O(n/2). بالطبع، من البداية - O(n)، من النهاية - O(1)؛
• set(int Index, Object obj) - هنا الوضع مختلف، حيث أنك تحتاج فقط إلى العثور على العنصر المطلوب والكتابة فوقه دون تحريك الباقي، لذلك O(1).

اقرأ المزيد عن ArrayList في هذه المقالة . ينفذ LinkedList واجهتين في وقت واحد - القائمة وقائمة الانتظار ، وبالتالي له خصائص وطرق متأصلة في بنيتي البيانات. من القائمة، تمكن من الوصول إلى عنصر حسب الفهرس، من قائمة الانتظار - وجود "الرأس" و"الذيل". داخليًا، يتم تنفيذه كبنية بيانات تمثل قائمة مرتبطة بشكل مزدوج. أي أن كل عنصر له رابط إلى العنصر التالي والسابق، باستثناء "الذيل" و"الرأس".

• get(int Index) - عند البحث عن عنصر موجود في منتصف القائمة، يبدأ البحث في جميع العناصر بالترتيب حتى يتم العثور على العنصر المطلوب. منطقيًا، يجب أن يستغرق البحث O(n/2) ، ولكن LinkedList أيضًا له ذيل، لذلك يتم إجراء البحث في وقت واحد من كلا الجانبين. وفقا لذلك، يتم تقليل الوقت إلى O(n/4) .

  إذا كان العنصر قريبًا من بداية القائمة أو نهايتها، فسيكون الوقت هو O(1) ؛

• add(Object obj) - عند إضافة عنصر جديد، سيكون لعنصر "الذيل" رابط للعنصر التالي المضاف، وسيتلقى العنصر الجديد رابطًا لهذا العنصر السابق ويصبح "الذيل" الجديد. وبناء على ذلك، سيكون الوقت O(1) ;
• إزالة (int Index) - منطق مشابه لطريقة get(int Index) . لإزالة عنصر من منتصف القائمة، يجب عليك أولاً العثور عليه. هذا مرة أخرى هو O(n/4) ، في حين أن الحذف نفسه لا يأخذ شيئًا في الواقع، لأنه يغير فقط مؤشر الكائنات المجاورة (تبدأ في الإشارة إلى بعضها البعض). إذا كان العنصر في البداية أو في النهاية، فمرة أخرى - O(1) ;
• add(int Index, Object obj) و set(int Index, Object obj) - سيكون للطرق تعقيد زمني مطابق لـ get(int Index) ، حيث يتم قضاء معظم الوقت في البحث عن العنصر. لذلك، في منتصف القائمة - O(n/4) ، في البداية - O(1).

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

• الخيار الأفضل إذا كانت العملية الأكثر شيوعًا هي البحث عن عنصر، أو الكتابة فوق عنصر ما؛
• الخيار الأسوأ إذا كانت العملية هي الإدراج والحذف في البداية-الوسطى، لأن عمليات الإزاحة للعناصر الموجودة على اليمين ستحدث.

قائمة مرتبطة:

• الخيار الأفضل إذا كانت عمليتنا المتكررة هي الإدراج والحذف في البداية والوسطى؛
• الخيار الأسوأ إذا كانت العملية الأكثر شيوعًا هي البحث.

9. كيف يتم تخزين العناصر في HashMap؟

تحتوي مجموعة HashMap على جدول Node[] للصفيف الداخلي ، وتسمى خلاياه أيضًا بالجرافات . تحتوي العقدة على:

• مفتاح - رابط للمفتاح،
• القيمة - إشارة إلى القيمة،
• التجزئة - قيمة التجزئة،
• التالي - الارتباط بالعقدة التالية .

قد تحتوي خلية واحدة من مصفوفة الجدول[] على مرجع إلى كائن عقدة مع رابط إلى عنصر العقدة التالي ، وقد تحتوي على رابط إلى عنصر عقدة آخر، وهكذا... ونتيجة لذلك، يمكن لعناصر العقدة هذه أن تشكل قائمة مرتبطة بشكل فردي ، مع عناصر مع رابط إلى التالي. في هذه الحالة، تكون قيمة التجزئة لعناصر سلسلة واحدة هي نفسها. بعد استطراد قصير، دعونا نلقي نظرة على كيفية تخزين العناصر في HashMap :

1. تم فحص المفتاح بحثًا عن null . إذا كان null ، فسيتم تخزين المفتاح في خلية الجدول [0] لأن رمز التجزئة للقيمة null هو دائمًا 0.
2. إذا لم يكن المفتاح فارغًا ، فسيتم استدعاء طريقة hashcode() الخاصة بالكائن الرئيسي ، والتي ستعيد رمز التجزئة الخاص به. يتم استخدام رمز التجزئة هذا لتحديد خلية الصفيف حيث سيتم تخزين كائن العقدة.
3. بعد ذلك، يتم وضع رمز التجزئة هذا في طريقة hash() الداخلية ، التي تحسب رمز التجزئة، ولكن ضمن حجم مصفوفة الجدول[] .
4. بعد ذلك، اعتمادًا على قيمة التجزئة، يتم وضع العقدة في خلية معينة في مصفوفة الجدول[] .
5. إذا كانت خلية الجدول [] المستخدمة لحفظ عنصر العقدة الحالي ليست فارغة، ولكنها تحتوي بالفعل على بعض العناصر، فسيتم تكرار عناصر العقدة على القيمة التالية حتى يتم الوصول إلى العنصر الأخير. أي أن حقله التالي فارغ .

   أثناء هذا البحث، تتم مقارنة مفتاح كائن العقدة المحمي بمفاتيح العناصر التي يتم البحث عنها:

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

غالبًا ما يُطرح السؤال أثناء المقابلات: ما هو الصراع ؟ يُطلق على الموقف الذي لا تقوم فيه خلية من مصفوفة الجدول[] بتخزين عنصر واحد، بل سلسلة من عنصرين أو أكثر، اسم الاصطدام . في الحالات العادية حيث يتم تخزين عنصر واحد فقط في خلية جدول[] واحدة ، فإن الوصول إلى عناصر HashMap له تعقيد زمني ثابت O(1) . ولكن عندما تحتوي الخلية التي تحتوي على العنصر المطلوب على سلسلة من العناصر ( الاصطدام ) ، فإن O(n) ، لأن الوقت في هذه الحالة يتناسب طرديًا مع عدد العناصر التي يتم فرزها.

10. شرح عن المكرر

في الرسم التخطيطي لتعيين التسلسل الهرمي للمجموعة أعلاه، كانت واجهة المجموعة هي المكان الذي بدأ فيه التسلسل الهرمي بأكمله، ولكن في الواقع ليس الأمر كذلك تمامًا. ترث المجموعة من واجهة باستخدام طريقة iterator() ، والتي تُرجع كائنًا ينفذ واجهة Iterator<E> . تبدو واجهة Iterator كما يلي:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - من خلال استدعاء هذه الطريقة، يمكنك الحصول على العنصر التالي. hasNext() - يسمح لك بمعرفة ما إذا كان هناك عنصر تالي، وما إذا كان قد تم الوصول إلى نهاية المجموعة. وعندما لا تزال هناك عناصر، فإن hasNext() ‎ ستُرجع true . عادةً، يتم استدعاء hasNext() قبل التابع next() ‎، نظرًا لأن التابع next() ‎ سوف يرمي NoSuchElementException عندما يصل إلى نهاية المجموعة . Remove() - يزيل العنصر الذي تم استرداده بواسطة الاستدعاء الأخير إلى next() . الغرض من Iterator هو التكرار على العناصر. على سبيل المثال:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

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

• hasPrevious سيعيد القيمة true إذا كان هناك عنصر سابق في المجموعة، والخطأ بخلاف ذلك؛
• السابق يُرجع العنصر الحالي وينتقل إلى العنصر السابق؛ إذا لم يكن هناك أي شيء، فسيتم طرح NoSuchElementException؛
• ستؤدي الإضافة إلى إدراج الكائن الذي تم تمريره قبل العنصر الذي سيتم إرجاعه بواسطة الاستدعاء التالي إلى next() ؛
• تعيين يعين العنصر الحالي مرجعا للكائن الذي تم تمريره؛
• يقوم nextIndex بإرجاع فهرس العنصر التالي. إذا لم يكن هناك شيء من هذا القبيل، فسيتم إرجاع حجم القائمة؛
• PreviousIndex يُرجع فهرس العنصر السابق. إذا لم يكن هناك أي شيء، فسيتم إرجاع الرقم -1.

حسنا، هذا كل شيء بالنسبة لي اليوم. آمل أنه بعد قراءة هذا المقال، تكون أقرب إلى حلمك العزيز - أن تصبح مطورًا.