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

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

1. أخبرنا قليلاً عن هياكل البيانات

بنية البيانات عبارة عن مخزن بيانات يحتوي على معلومات منظمة بطريقة معينة. تم تصميم هذه الهياكل لتحقيق الأداء الفعال لعمليات معينة. الأمثلة النموذجية لهياكل البيانات هي:

• صفائف,
• مداخن,
• طوابير,
• قوائم ذات صلة،
• الرسوم البيانية,
• الأشجار،
• أشجار البادئة,
• جدول التجزئة.

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

2. ماذا تعرف عن المصفوفات؟

المصفوفة عبارة عن حاوية لتخزين قيم من نفس النوع، تم تحديد عددها مسبقًا. مثال على إنشاء مصفوفة بقيم سلسلة:

String[] strArray = {"Java","is","the","best","language"};

عند إنشاء مصفوفة، يتم تخصيص الذاكرة لجميع عناصرها: كلما تم تحديد المزيد من الخلايا للعناصر في البداية، سيتم تخصيص المزيد من الذاكرة. إذا تم إنشاء مصفوفة فارغة تحتوي على عدد معين من الخلايا، فسيتم تعيين قيم افتراضية لجميع عناصر المصفوفة. على سبيل المثال:

int[] arr = new int[10];

لذلك، بالنسبة للمصفوفة التي تحتوي على عناصر من النوع المنطقي ، ستكون القيم الأولية ( الافتراضية ) خاطئة ، بالنسبة للمصفوفات ذات القيم الرقمية - 0، مع عناصر من النوع char - \u0000 . بالنسبة لمصفوفة من نوع الفئة (الكائنات) - null (ليست سلاسل فارغة - "" ولكن على وجه التحديد null ). أي أنه في المثال أعلاه، ستكون جميع قيم المصفوفة arr 0 حتى يتم تحديدها مباشرة. على عكس المجموعات، المصفوفات ليست ديناميكية. بمجرد الإعلان عن مصفوفة ذات حجم معين، لا يمكن تغيير الحجم نفسه. لإضافة عنصر جديد إلى مصفوفة، تحتاج إلى إنشاء مصفوفة جديدة أكبر ونسخ جميع العناصر من المصفوفة القديمة إليها (هذه هي الطريقة التي تعمل بها ArrayList). هناك نقطة واحدة لا يعرفها الجميع والتي يمكنك التعرف عليها جيدًا. هناك نوعان من المتغيرات في Java - الأنواع البسيطة والمراجع للكائنات الكاملة. أي من هذه المصفوفات؟ على سبيل المثال، هنا:

int[] arr = new int[10];

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

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

عند الإخراج إلى وحدة التحكم قد تحصل على شيء مثل: اقرأ المزيد عن ميزات المصفوفات في Java في هذه المقالة حول Java Array . لتعزيز معرفتك، يمكنك حل العديد من المشاكل من هذه المجموعة .

3. شرح التسلسل الهرمي للمجموعات

تُستخدم المجموعات في المواقف التي تحتاج فيها إلى المرونة عند التعامل مع البيانات. يمكن للمجموعات إضافة عنصر وإزالة عنصر وتنفيذ العديد من العمليات الأخرى. هناك العديد من التطبيقات المختلفة في Java، ونحتاج فقط إلى اختيار المجموعة المناسبة للوضع الحالي. عادةً، عندما تذكر واجهة المجموعة ، يُطلب منك إدراج بعض تطبيقاتها وعلاقتها بالخريطة . حسنا، دعونا معرفة ذلك. لذا، فإن المجموعة والخريطة هما تسلسلان هرميان مختلفان لهياكل البيانات. الشكل الذي يبدو عليه التسلسل الهرمي للمجموعة : واجهة المجموعة هي الرابط العلوي الرئيسي الذي يحتوي على قائمة من الأساليب الأساسية، والتي تنشأ منها ثلاثة أنواع أساسية من هياكل البيانات - Set ، وList ، و Queue . Set<T> هي واجهة تمثل مجموعة من الكائنات التي يكون كل كائن فيها فريدًا. List<T> هي واجهة تمثل تسلسلًا مرتبًا للكائنات تسمى القائمة. Queue<T> هي واجهة مسؤولة عن الهياكل التي يتم تنظيمها كقائمة انتظار (التخزين المتسلسل للعناصر). كما ذكرنا سابقًا، الخريطة عبارة عن تسلسل هرمي منفصل: Map<K, V> هي واجهة تمثل قاموسًا يتم فيه تضمين العناصر كأزواج قيمة المفتاح. علاوة على ذلك، فإن جميع المفاتيح (K) فريدة داخل كائن الخريطة . هذا النوع من التجميع يجعل من السهل العثور على عنصر ما إذا كنا نعرف المفتاح - المعرف الفريد للكائن.

4. ماذا تعرف عن ست؟

كما ذكرنا سابقًا، تتميز هذه المجموعة بالعديد من العناصر الفريدة. بمعنى آخر، لا يمكن أن يظهر نفس الكائن أكثر من مرة في مجموعة Java. أود أيضًا أن أشير إلى أنه لا يمكننا استخراج عنصر من مجموعة حسب الرقم (الفهرس) - فقط بالقوة الغاشمة. الشيء المهم هو أن تطبيقات Set المختلفة لها طرق مختلفة لتنظيم البيانات. سننظر في تطبيقات محددة بشكل أكبر. لذا، فإن التطبيقات الرئيسية لـ Set : HashSet هي مجموعة تعتمد على جدول التجزئة، والذي بدوره يساعد في البحث. يستخدم وظيفة التجزئة التي تعمل على تحسين الأداء أثناء عمليات البحث والإدراج. بغض النظر عن عدد العناصر، بشكل عام، يتم إجراء الإدراج والبحث (أحيانًا الحذف) في وقت قريب من ثابت - O(1). سننظر في وظيفة التجزئة بمزيد من التفصيل بعد قليل. أود أيضًا أن أشير إلى أن HashSet تحتوي على HashMap ، حيث يحدث كل السحر. فيما يلي مقالة مفصلة حول HashSet في Java . LinkedHashSet - تعمل هذه الفئة على توسيع HashSet دون إضافة أي طرق جديدة. مثل LinkedList ، تحتفظ هذه الفئة بقائمة مرتبطة بعناصر المجموعة بالترتيب الذي تم إدراجها به. يتيح لك هذا تنظيم الترتيب اللازم في تطبيق Set معين . تقوم فئة TreeSet بإنشاء مجموعة تعتمد على شجرة حمراء وسوداء لتنظيم بنية تخزين العناصر. بمعنى آخر، في مجموعة معينة يمكننا ترتيب العناصر بترتيب تصاعدي. إذا استخدمنا بعض الكائنات القياسية من "المربع"، على سبيل المثال، Integer ، فلن نحتاج إلى القيام بأي شيء لترتيب مجموعة الأعداد الصحيحة ترتيبًا تصاعديًا:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

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

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

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

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

كما لاحظت، يُرجع التابع CompareTo قيمة int :

• 1 إذا كان الكائن الحالي (هذا) يعتبر كبيرًا؛
• -1 إذا كان الكائن الحالي يعتبر أصغر من الكائن الذي جاء كوسيطة؛
• 0 إذا كانت العناصر متساوية (لا نستخدم هذا في هذه الحالة).

في هذه الحالة، سوف يعمل TreeSet الخاص بنا بشكل صحيح ويعرض النتيجة: هناك طريقة أخرى تتمثل في إنشاء فئة فرز منفصلة تنفذ واجهة المقارنة وطريقة المقارنة الخاصة بها :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

في هذه الحالة، لاستخدامه، يجب علينا تعيين كائن من هذه الفئة إلى مُنشئ TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

بعد ذلك، سيتم فرز جميع كائنات فئة Cat المضمنة في TreeSet باستخدام فئة Cat Comparator . يمكنك معرفة المزيد حول Comparator و Comparable في Java من هذه المقالة .

5. أخبرنا عن قائمة الانتظار

قائمة الانتظار هي واجهة مسؤولة عن الهياكل التي يتم تنظيمها كقائمة انتظار - وهي بنية بيانات تقوم بتخزين العناصر بشكل تسلسلي. على سبيل المثال، من قائمة انتظار من الأشخاص، سيكون أول شخص يدخل هو الشخص الذي وصل قبل الآخرين، وسيكون الأخير هو الشخص الذي وصل متأخرًا عن أي شخص آخر. تسمى هذه الطريقة FIFO ، أي الوارد أولاً يخرج أولاً . تركز أساليب قائمة الانتظار الفريدة على العمل مع العنصر الأول أو الأخير، على سبيل المثال:

• إضافة وعرض - إدراج عنصر في نهاية قائمة الانتظار ،
• إزالة - استرداد وإزالة رأس قائمة الانتظار هذه،
• نظرة خاطفة - يسترد رأس قائمة الانتظار ولكن لا يزيله.

الجزء 2