مناقشة موجزة حول جمع فئات التنفيذ وخريطة هياكل البيانات شائعة الاستخدام في جافا

الجداول الخطية والقوائم المرتبطة وجداول التجزئة هي هياكل بيانات شائعة الاستخدام. عند تطوير Java ، قدمت لنا JDK سلسلة من الفئات المقابلة لتنفيذ هياكل البيانات الأساسية. هذه الفئات كلها في حزمة java.util. تحاول هذه المقالة أن تشرح للقراء دور كل فصل وكيفية استخدامها بشكل صحيح من خلال وصف بسيط.

 مجموعة ├list │✜linkedlist │✜arraylist │└vector

واجهة جمع

المجموعة هي واجهة مجموعة أساسية. تمثل المجموعة مجموعة من الكائنات ، أي عناصر المجموعة (العناصر). تسمح بعض المجموعات بنفس العناصر بينما لا تفعل ذلك. يمكن للبعض الفرز ولكن البعض الآخر لا يستطيع ذلك. لا توفر Java SDK فصولًا موروثة مباشرة من المجموعة. الفصول الدراسية التي توفرها Java SDK هي كلها "Subinterfaces" الموروثة من مجموعة مثل List و Set.

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

كيف تكرر من خلال كل عنصر في مجموعة؟ بغض النظر عن النوع الفعلي للمجموعة ، فإنه يدعم طريقة Iterator () ، التي تُرجع جهاز التكرار ، ويستخدم هذا التكرار للوصول إلى كل عنصر في المجموعة واحدة تلو الأخرى.

الاستخدامات النموذجية هي كما يلي:

 iterator it = collection.iterator () ؛ // احصل على iterator بينما (it.hasnext ()) {object obj = it.next () ؛ // احصل على العنصر التالي}

الواجهتان المستمدون من واجهة التجميع هي قائمة ومجموعة.

قائمة الواجهة

القائمة هي مجموعة مرتبة ، ويسمح لك استخدام هذه الواجهة بالتحكم بدقة في موضع كل عنصر إدراج. يمكن للمستخدمين استخدام الفهارس (موضع العناصر في القائمة ، على غرار مشتركات الصفيف) للوصول إلى العناصر في القائمة ، والتي تشبه صفائف Java.

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

بالإضافة إلى طريقة ITerator () التي تحتوي على طريقة ITERATAR () الضرورية ، توفر القائمة أيضًا طريقة LISTIREITIRATOR () ، والتي تُرجع واجهة LISTITERATOR. بالمقارنة مع واجهة ITerator القياسية ، يحتوي ListIrator على المزيد من الطرق مثل Add () ، مما يسمح بإضافة العناصر وحذفها وتحديدها وتجارة للأمام أو للخلف.

تتضمن الفئات الشائعة التي تنفذ واجهات قائمة LinkedList و ArrayList و Vector و Stack.

LinkedList Class

ينفذ LinkedList واجهة القائمة ، مما يسمح عناصر فارغة. بالإضافة إلى ذلك ، يوفر LinkedList GET ، إزالة ، إدراج طرق في رأس أو ذيل LinkedList. تتيح هذه العمليات استخدام LinkedList لاستخدامها كمكدس أو قائمة انتظار أو قائمة انتظار ثنائية الاتجاه.

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

قائمة قائمة = collections.synchronizedList (New LinkedList (...)) ؛

فئة ArrayList

ArrayList ينفذ صفائف متغيرة الحجم. يسمح لجميع العناصر ، بما في ذلك فارغة. لا يتم مزامنة ArrayList.

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

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

مثل LinkedList ، ArrayList هو أيضا غير متزامن.

فئة المتجهات

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

فئة المكدس

يرث Stack من Vector ، وتنفيذ مكدس آخر في الخارج. يوفر المكدس 5 طرق إضافية لتمكين المتجه لاستخدامه كمكدس. تحصل أساليب الدفع والبوب ​​الأساسية ، وطريقة نظرة خاطفة على العناصر في الجزء العلوي من المكدس ، وتختبر الطريقة الفارغة ما إذا كانت المكدس فارغًا ، وتكتشف طريقة البحث موضع عنصر في المكدس. المكدس تم إنشاؤه للتو وهو مكدس فارغ.

تعيين واجهة

SET عبارة عن مجموعة لا تحتوي على عناصر مكررة ، أي أن هناك عنصرين e1 و e2 لهما e1.equals (e2) = false ، والمجموعة لديها على الأكثر عنصر فارغ واحد.

من الواضح أن مُنشئ المجموعة له قيد ، ولا يمكن أن تحتوي معلمة التجميع التي تم تمريرها على عناصر مكررة.

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

واجهة الخريطة

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

فئة الهاشت

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

استخدم (مفتاح ، قيمة) لإضافة بيانات ، استخدم GET (مفتاح) لاسترداد البيانات. الوقت النفقات العامة لهاتين العمليتين الأساسيتين ثابتة.

يقوم علامة التجزئة بضبط الأداء من خلال معلمات السعة الأولية ومعلمات عامل التحميل. عادة ، يمكن لعامل التحميل الافتراضي 0.75 تحقيق توازن الوقت والمساحة بشكل أفضل. يمكن أن توفر زيادة عامل التحميل المساحة ولكن سيزداد وقت البحث المقابل ، مما سيؤثر على عمليات مثل Get and Put.

مثال بسيط على استخدام علامة التجزئة على النحو التالي: وضع 1 و 2 و 3 في علامة تجزئة ، ومفاتيحهم هي "واحدة" ، "اثنان" ، "ثلاثة" على التوالي:

أرقام hashtable = new hashtable () ؛
الأرقام.
الأرقام.
الأرقام.

لإخراج رقم ، مثل 2 ، استخدم المفتاح المقابل:

عدد صحيح n = (عدد صحيح) number.get ("اثنين") ؛
System.out.println ("two =" + n) ؛

نظرًا لأن كائن كمفتاح سيحدد موضع القيمة المقابلة عن طريق حساب وظيفة التجزئة الخاصة به ، يجب على أي كائن كمفتاح تنفيذ الأساليب ومتساوي. ترث الأساليب hashcode و equals من كائن فئة الجذر. إذا كنت تستخدم فئة مخصصة كمفتاح ، فكن حذرًا جدًا. وفقًا لتعريف وظيفة التجزئة ، إذا كان الكائنان متماثلان ، أي OBJ1.equals (OBJ2) = صحيح ، يجب أن يكون رمز hashcode هو نفسه ، ولكن إذا كان الكائنان مختلفان ، فقد لا تختلف رموزها. إذا كانت الترميزات من كائنين مختلفين متماثلين ، فإن هذه الظاهرة تسمى الصراع. سيزيد الصراع من الوقت العام لتشغيل جدول التجزئة. لذلك ، حاول تحديد طريقة HashCode () لتسريع تشغيل جدول التجزئة.

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

تتم مزامنة الهاشتو.

فئة هاشماب

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

الفئة الضعيفة

DefehashMap هو hashmap محسّن ينفذ "مرجعًا ضعيفًا" للمفتاح. إذا لم يعد المشار إليه مفتاحًا خارجيًا ، فيمكن إعادة تدوير المفتاح بواسطة GC.

لخص

إذا تم إشراك Stack و Learue والعمليات الأخرى ، فيجب عليك التفكير في استخدام القائمة. بالنسبة للعناصر التي تحتاج إلى إدراج وحذفها بسرعة ، يجب عليك استخدام LinkedList. إذا كانت العناصر بحاجة إلى الوصول بسرعة ، فيجب عليك استخدام ArrayList.

java.util.collections فئة حزمة

تحتوي فئة java.util.collections على العديد من الأساليب المفيدة التي يمكن أن تجعل عمل المبرمجين أسهل ، ولكن هذه الطرق عادة لا يتم استخدامها بالكامل. يقدم Javadoc الوصف الأكثر اكتمالا لفئة المجموعات: "تحتوي هذه الفئة على فئة ثابتة مخصصة يمكنها تشغيل مجموعة أو إرجاعها.
"1.2 الطرق المشمولة
iterator ، arraylist ، عناصر ، عازلة ، خريطة ، مجموعات

ليزي:

 استيراد java.util.arraylist ؛ استيراد java.util.collection ؛ استيراد java.util.collections ؛ استيراد java.util.comparator ؛ استيراد java.util.list ؛ مجموعات الفئة العامة {public CollectionSort () {} public static void main (string [] args) {double array [] = {111 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ قائمة li = new ArrayList () ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ //list.add("+array budapi]) ؛ } double arr [] = {111} ؛ لـ (int j = 0 ؛ j <arr.length ؛ j ++) {li.add (new double (arr [j])) ؛ }}

2. عمليات محددة

1) فرز (فرز)

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

 صفيف مزدوج [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } collections.sort (list) ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {system.out.println (li.get (i)) ؛ } // النتيجة: 112،111،23،456،231

2) خلط

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

 collections.ushuffling (list) double array [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } collections.shuffle (list) ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {system.out.println (li.get (i)) ؛ } // النتيجة: 112،111،23،456،231

3) عكس

استخدم الطريقة العكسية لفرز القائمة المحددة بترتيب تنازلي وفقًا للترتيب الطبيعي للعناصر.

 collections.reverse (list) double array [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } المجموعات. عكس (قائمة) ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {system.out.println (li.get (i)) ؛ } // النتيجة: 231،456،23،111112 4) استبدل جميع العناصر في القائمة المحددة بالعنصر المحدد. String str [] = {"dd" ، "aa" ، "bb" ، "cc" ، "ee"} ؛ لـ (int j = 0 ؛ j <str.length ؛ j ++) {li.add (سلسلة جديدة (str [j])) ؛ } collections.fill (li ، "aaa") ؛ لـ (int i = 0 ؛ i <li.size () ؛ i ++) {system.out.println ("list [" + i + "] =" + li.get (i)) ؛ } // النتيجة: AAA ، AAA ، AAA ، AAA

5) نسخة (نسخة)

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

collections.copy (قائمة ، LI): المعلمة الأخيرة هي القائمة المستهدفة ، القائمة السابقة هي القائمة المصدر

 صفيف مزدوج [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ قائمة li = new ArrayList () ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } double arr [] = {1131،333} ؛ String str [] = {"dd" ، "aa" ، "bb" ، "cc" ، "ee"} ؛ لـ (int j = 0 ؛ j <arr.length ؛ j ++) {li.add (new double (arr [j])) ؛ } collections.copy (list ، li) ؛ لـ (int i = 0 ؛ i <list.size () ؛ i ++) {system.out.println ("list [" + i + "] =" + list.get (i)) ؛ } // النتيجة: 1131،333،23،456،231

6) يعيد أصغر عنصر في المجموعات (دقيقة)

إرجاع أصغر عنصر في المجموعة المحددة وفقًا للترتيب الذي يتم فيه إنشاء المقارنة المحددة. يجب مقارنة جميع العناصر في المجموعة مع بعضها البعض من خلال المقارنة المحددة

 collections.min (list) double array [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } collections.min (list) ؛ لـ (int i = 0 ؛ i <list.size () ؛ i ++) {system.out.println ("list [" + i + "] =" + list.get (i)) ؛ } // النتيجة: 23

7) يعيد أصغر عنصر (كحد أقصى) في المجموعات

إرجاع العنصر الأقصى للمجموعة المحددة وفقًا للترتيب الذي يتم فيه إنشاء المقارنة المحددة. يجب مقارنة جميع العناصر في المجموعة مع بعضها البعض من خلال المقارنة المحددة

 collections.max (list) double array [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } collections.max (list) ؛ لـ (int i = 0 ؛ i <list.size () ؛ i ++) {system.out.println ("list [" + i + "] =" + list.get (i)) ؛ } // النتيجة: 456

8) LastIndExofSublist

إرجاع موضع البداية لقائمة الهدف المحددة التي ظهرت آخر مرة في قائمة المصدر المحددة

 int count = collections.lastindexofSublist (list ، li) ؛ صفيف مزدوج [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ قائمة li = new ArrayList () ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } double arr [] = {111} ؛ String str [] = {"dd" ، "aa" ، "bb" ، "cc" ، "ee"} ؛ لـ (int j = 0 ؛ j <arr.length ؛ j ++) {li.add (new double (arr [j])) ؛ } مواقع int = المجموعات. LastIndExofSublist (قائمة ، li) ؛ System.out.println ("==="+ مواقع) ؛ // النتيجة 3

9) IndexOfSublist

إرجاع موضع البداية لأول مرة تظهر قائمة الهدف المحددة في قائمة المصدر المحددة

 int count = collections.indexofSublist (list ، li) ؛ صفيف مزدوج [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ قائمة li = new ArrayList () ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } double arr [] = {111} ؛ String str [] = {"dd" ، "aa" ، "bb" ، "cc" ، "ee"} ؛ لـ (int j = 0 ؛ j <arr.length ؛ j ++) {li.add (new double (arr [j])) ؛ } int soligations = collections.indexofSublist (list ، li) ؛ System.out.println ("==="+ مواقع) ؛ // النتيجة 1

10) تدوير

نقل عناصر في القائمة المحددة استنادًا إلى المسافة المحددة
collections.rotate (قائمة ، -1) ؛
إذا كان رقمًا سالبًا ، فإنه يتحرك بشكل إيجابي ، وإذا كان يتحرك بشكل إيجابي ، فإنه يتحرك بشكل إيجابي.

 صفيف مزدوج [] = {112 ، 111 ، 23 ، 456 ، 231} ؛ قائمة قائمة = ArrayList () جديد ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {list.add (new double (Array [i])) ؛ } collections.rotate (قائمة ، -1) ؛ لـ (int i = 0 ؛ i <list.size () ؛ i ++) {system.out.println ("list [" + i + "] =" + list.get (i)) ؛ } // النتيجة: 111،23،456،231،112

تناقش المقالة أعلاه باختصار جمع فئات التنفيذ وخريطة هياكل البيانات الشائعة الاستخدام في Java. هذا هو كل المحتوى الذي شاركته معك. آمل أن تتمكن من إعطائك مرجعًا وآمل أن تتمكن من دعم wulin.com أكثر.