Home برمجة الــ Collections في الجافا
الــ Collections في الجافا

الــ Collections في الجافا

1.62K
3

السلام عليكم و رحمة الله و بركاته

البداية ستكون مع تعريف بسيط و مختصر لهياكل البيانات بشكل عام ثم نأتي بعد ذلك إلى الـ Collections و أهميتها في البرمجة لننتقل إلى التغيرات الجديدة التي أضافها الـ Collections FrameWork من خلال استعراض الـ Hierarchy الجديد و شرح دور مختلف الـ interfaces الموجودة مثل Map, Set, List, SortedSet, SotedMap و الـ Iterators المرافقة لكل interface بالإضافة إلى شرح مفصل لمختلف الدوال الموجودة في كل واحدة مع أمثلة في نهاية كل فقرة.
بعد ذلك ننتقل إلى الـ views و أنواعها الموجودة و كيفية استخدامها.
الفقرة الموالية تتعلق بترتيب الـ Collections مع توضيح الفرق بين Comparable و Comparator و متى نستخدم كل واحدة منهما مع مثال توضيحي شامل.
الختام سيكون مع الـ algorithmes التي تُمكن من التعامل مع الـ collections من خلال وصف دقيق لكل خورارزمية على حدة بالإضافة إلى كيفية الحصول على نسخة multi-thread أو unmodifiable لـ list معينة

تعريف مختصر لهياكل البيانات

عبارة عن طريقة خاصة لتخزين وتنظيم البيانات على شكل array, list, stack .. etc, هذه الخصوصية تكمن في كمية الذاكرة المستخدمة لتخزين البيانات بالإضافة إلى الوقت المستغرق لإجراء بعض العمليات على تلك البيانات. تختلف أنواع هياكل البيانات باختلاف التطبيقات البرمجية أو نوعية الاستخدام, كل حسب ما يناسبه. فمثلا نجد أن الــ B-Tree تناسب التطبيقات الخاصة بقواعد البيانات بينما نجد الــ Hash Table يُستخدم بكثرة في برمجة الــ compilers خصوصا عند البحث عن الــ identifiers.

ما هي الــ Collections ؟

تقوم الــ collections بإدارة و تسيير مجموعة من الكائنات ذات نوع معين أو يمكننا القول بأنها عبارة عن كائن يمكنه تخزين بيانات من نوع آخر. في أولى إصدارات الجافا, اقتصر تمثيل الــ collections في Vector, Stack, Hashtable, Bitset ثم ظهر بعد ذلك الــ Collections frameWork في Java 1.2 الذي حافظ على المبادئ الأساسية لهياكل البيانات و أضاف العديد من التعديلات و التحسينات بحيث تم تصميم تلك الهياكل على شكل شجري محكم التنسيق.

يمكن للــ collections تخزين العناصر أيا كان نوعها بشرط أن تكون كائنات. يمكن مثلا أن تكون String, Integer, Float, Manager أو أي كائن آخر .. لكن مع ذلك من الخطر جدا استخدام collection تحتوي على أنواع مختلفة من الكائنات لأنك ستحتاج دوما إلى استخدام الــ casting أو instanceof من أجل تحديد صنف  الكائن. بالتالي يُستحسن دائما تخزين كائنات من نفس النوع في الــ collection الواحدة.

عند إدراج عنصر معين في الــ collection يتم الاكتفاء بتخزين الــ reference الخاص بالــ object و بالتالي يمكننا أحيانا إدراج الــ null reference داخل collection.

مالجديد في Collections FrameWork ؟

يحتوي الإصدار الجديد على العديد من الفئات و الواجهات كما يُقدم أيضا بعض الــ abstract classes التي تقوم بعمل implementation لبعض الــ interfaces.

الواجهات التي يمكن استخدامها مع كائنات للتعامل مع الــ collections هي :

  • Collection : معظم الفئات التي تتعامل مع الــ collections قامت بعمل implement لهذه الواجهة.
  • Map : هذه الواجهة تحتوي على الدوال أو الــ methods الخاصة بالكائنات التي تتعامل مع الــ associative array على شكل key/value.
  • Set : خاصة بالكائنات التي لا تقبل التكرار داخل المجموعة.
  • List : الكائنات التي تقبل التكرار داخل المجموعة و تدعم الوصول إلى العناصر بشكل مباشر.
  • SortedSet : هذه الواجهة ترث الواجهة Set و تسمح بترتيب العناصر.
  • SortedMap : ترث الواجهة Map و تسمح بترتيب العناصر.

بعض الدوال (اعذرني أخي القارئ فأنا أفضل كلمة الدوال على مصطلح الطرق) الموجودة في الواجهات السابقة, اختيارية بمعنى أن تعريفها اجباري لكن إذا كانت العملية غير مدعومة فيمكن للدالة أن تُصدر exception تُوضح نوع خطأ الاستخدام. الهدف من شيء كهذا هو تقليل عدد الواجهات و تلبية أكبر عدد ممكن من الحاجات المطلوبة.

 أيضا, الــ framework يوفر العديد من الكائنات التي تدعم الواجهات السابقة و يمكن استخدامها بشكل مباشر:

  • HashSet : عبارة عن Hash table أو جدول هاش يدعم الواجهة Set.
  •  TreeSet : شجرة (tree) قامت بعمل implement للواجهة SortedSet.
  • ArrayList : مصفوفة ديناميكية قامت بعمل implement للواجهة List.
  • LinkedList : قائمة متصلة مزدوجة قامت بعمل implement للواجهة List.
  • HashMap : جدول هاش (Hash table) قام بعمل implement للواجهة Map.
  • TreeMap : شجرة (tree) قامت بعمل implement للواجهة SortedMap.

بالنسبة للواجهات التي تُمكن من المرور على عناصر الــ collections و ترتيبها فهي :

  • Iterator : للتجول بين مختلف عناصر الــ collection.
  • ListIterator : تسمح بالمرور على عناصر List في الاتجاهين كما تسمح بتغيير عناصر المجموعة.
  • Comparable : لتعريف نوع الترتيب الطبيعي لكائن معين.
  • Comparator : لتعريف ترتيب كيفي (لا على التعيين).

هذا بالإضافة إلى فئتين كانتا توجدان في النسخة السابقة و أجريت عليهما بعض التعديلات لدعم بعض الواجهات الجديدة:

  • Vector : مصفوفة ديناميكية قامت بعمل implement للواجهة الجديدة List
  • HashTable : Hash table قام بعمل implement للواجهة الجديدة Map

المخطط الجديد لــ Collections FrameWork

1 –  Collection Hierarchy

1

1.1 –  الواجهة Collection

كما قلنا سابقا, أغلب الواجهات الجديدة تحتوي على دوال اختيارية, هذه الخاصية تسمح لك بالتعامل مع هياكل البيانات الخاصة دون أن تحتاج إلى تعريف دوال جديدة. الدوال الاختيارية تُستعمل عند الحاجة فقط. على سبيل المثال إذا كان لدينا Set غير قابلة للتعديل يمكننا إعادة تعريف الدالة add بحيث نمنع التعديل أو الإضافة. تختلف الدوال باختلاف مهامها فهناك بعض الدوال ينفذ العملية بشكل فردي (أي على كائن واحد) و هناك أخرى تنفذها بشكل جماعي أي على مجموعة كائنات في آن واحد.

  • الدالتان add و remove تسمحان بإضافة أو حذف عنصر معين بينما تقوم addAll أو removeAll بحذف أو إضافة مجموعة كائنات بشكل جماعي.
  • الدالة contains تتحقق من وجود عنصر داخل المجموعة. إذا أردنا التحقق من وجود مجموعة عناصر في آن واحد نستخدام containsAll.
  • size, isEmpty و clear يمكنهم (على التوالي) معرفة حجم الــ collection, التحقق من أن الــ collection فارغة و الأخيرة تُمكن من حذف محتوى الــ collection.
  • retainAll تُستعمل لإيجاد تقاطع الــ collections, فمثلا إذا كانت  A={1,2,5,8} و B={3,8} فإن A ستصبح {8}.
  • equals تتحقق من تطابق الــ collections.
  • hashCode تُعيد كود الــ hash code الخاص بالــ collection.
  • toArray تُعيد عناصر الــ collection على شكل مصفوفة.
  • toArray(Object a[])l تسمح بتحديد نوع المصفوفة المعادة.

للمرور على عناصر collection نستخدم الواجهة Iterator :

  • hasNext : تتحقق من وجود عنصر قادم.
  • next : تُشير إلى العنصر القادم.
  • remove : تحذف العنصر الحالي.

ملاحظة:

الدالة next تُصدر NoSuchElementException عند استدعائها بعد انتهاء عناصر الــ collection. لتفادي هذه الـــ Exception يكفي تطبيق hasNext على الكائن المُعاد من طرف الدالة next, هكذا :

 

1.2 –  الواجهة Set

هذه الواجهة عبارة عن Collection غير مرتبة, لا تسمح بتكرار العناصر. يوجد نوعان من الــ implementation, الاختيار بينهما يكون حسب ضرورة ترتيب العناصر:

  • HashSet : العناصر غير مرتبة, عملية الإضافة سريعة جدا.
  • TreeSet : العناصر مرتبة, عملية الإضافة تكون ابطأ.

مالفرق بين الاثنين ؟

  • HashSet : تستخدم تقنية الــ hashing لتحديد تكرار العنصر و تعتمد على الدالة hashCode في الترتيب.
  • TreeSet : تستخدم binary tree لترتيب العناصر و تعتمد على الدالة compareTo في الترتيب.

ملاحظات:

  1. نوع الترتيب المُستخدم يتم تحديده من طرف الكائنات المضافة إلى TreeSet من خلال عمل implementation للواجهة Comparable إذا أردنا الترتيب حسب natural sort order أو يمكننا تمرير كائن من Comparator لدالة بناء TreeSet إذا أردنا تحديد الــ sort order.
  2. للتأكد من وجود عنصر معين داخل Set استخدم الدالة equals. مع العلم طبعا بأنه يجب إعادة تعريف equals حتى تستطيع التأكد من وحدانية أو عدم تكرار الكائن المضاف.

انظر المثال:

 

1.3 –  الواجهة List

List عبارة عن collection مرتبة تسمح بتكرار العناصر, تحتوي هذه الواجهة على دوال تُمكن من إضافة أو حذف عنصر في أي مكان من المجموعة. كما تسمح بالتعامل مع القوائم المتداخلة, في أغلب الحالات نستخدم ArrayList إلا إذا كانت هناك عمليات إضافة في المنتصف, عندها يُستحسن استخدام LinkedList لتفادي عمليات الإزاحة المتكررة.

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

  • الدالة get تُعيد العنصر الموجود في الموقع index.
  • set تُغير العنصر الموجود في الموقع index.
  • indexOf (على التوالي lastIndexOf) تبحث عن وجود العنصر في المجموعة و تُعيد رقم موقعه (على التوالي رقم آخر ظهور له) في المجموعة.
  • subList تسمح بإنشاء قائمة داخل أخرى.

للمرور على عناصر List تم إنشاء Iterator خاص :

حيث يسمح بالمرور على عناصر List في الاتجاهين بالإضافة إلى إمكانية تغيير عنصر معين أو إضافة آخر جديد :

nextIndex تُعيد رقم موقع العنصر الحالي و بقية الدوال رأيناها سابقاً.

1.4 –  الكلاس ArrayList

هذا الكلاس يرث الكلاس AbstractList مما يعني أنه قام بعمل implement للواجهة List يُمثل مصفوفة ديناميكية من الكائنات. طريقة عمله مطابقة تماما لتلك الخاصة بــ Vector, الفرق بينهما هو أن هذا الأخير يدعم الــ multi-thread (جميع الدوال synchronized). اذا اردنا استخدام thread واحد فالــ synchronization تكون مكلفة و عديمة الفائدة لذا من الأفضل استخدام ArrayList في مثل هذه الحالات.

اضافة إلى الدوال السابقة توجد:

  • ensureCapacity : تسمح بزيادة حجم المصفوفة لضمان تخزين العناصر الجديدة.
  • trimToSize : تسوية سعة المصفوفة على حجمها الحالي.

مثال أول:

 مُخرجات الكود ستكون بهذا الشكل:

3

بعد حذف 2, 5 و 8 سيكون طول المصفوفة يساوي 7 و بالتالي عندما نحاول حذف العنصر الثامن سيتم رفع استثناء من نوع IndexOutOfBoundsException.

مثال ثاني:

مُخرجات الكود ستكون على النحول التالي:

4

2 – Map Hierarchy

2

2.1 – ماهو الــ Map ؟

الــ Map عبارة عن مجموعة أزواج, كل زوج يحتوي على مفتاح و قيمة key/value مع العلم أن المفتاح لا يمكن تكراره. (في الحقيقة يمكننا اسناد عدة قيم لمفتاح واحد, في هذه الحالة سنكون أمام multimap). الهدف الأساسي من الــ Map هو الوصول بسرعة إلى المفتاح للحصول على القيمة المقابلة له.

2.2 – عرض سريع لمختلف الدوال الموجودة داخل الواجهة Map

  • الدالة clear تسمح بحذف جميع عناصر الــ Map.
  • containsKey تُحدد ما إذا كان المفتاح key موجود أو لا.
  • containsValue تُحدد ما إذا كانت القيمة value موجودة داخل الــ Map.
  • entrySet تُعيد Set تحتوي على جميع قيم الــ Map.
  • get تُعيد القيمة المرافقة للمفتاح key.
  • isEmpty تتحق من فراغ الــ Map.
  • keySet تُعيد Set تحتوي على كافة مفاتيح الــ Map.
  • put تضيف المفتاح key و القيمة المرافقة له value داخل الــ Map.
  • putAll تضيف كافة المفاتيح و القيم داخل الــ Map.
  • values تُعيد قيم الــ Map على شكل collection.
  • remove يحذف العنصر المقابل للمفتاح key.
  • size تُعيد عدد عناصر الــ Map.

 

2.3 – ماهي انواع الــ implementation الموجودة ؟

يوجد نوعان من الــ Map :

  • HashMap, Hashtable : يستخدمان جدول هاش.
  • TreeMap : تستخدم شجرة ثنائية.

ملاحظات :

  1. الفئة HashMap ليست synchronized. للتعامل مع الــ concurrent access, قم بتغليف الكائن داخل كائن من Map باستخدام الدالة synchronizedMap الموجودة في الواجهة Collection.
  2. إذا كان المفتاح المُمرر إلى put موجود مسبقا سيتم استبدال القيمة القديمة بالجديدة. put تُعيد القيمة القديمة إذا كان المفتاح موجود مسبقا و إلا فستعيد null.
  3. TreeMap قامت بعمل implement لــ SortedMap, ترتيب العناصر يتم تحديده عن طريق كائن من نوع Comparable.

2.4 – ماهي الــ view ؟

  • تسمح الــ view بالمرور على عناصر الـــ Map.
  • نظريا, الفئتان HashMap و TreeMap لا يملكان أي Iterator.
  • الدالة entrySet تسمح برؤية Map كمجموعة ازواج.
  • الزوج عبارة عن كائن من نوع الواجهة Map.entry حيث يجمع كائنين في آن واحد.
  • الدالتان getKey و getValue الموجودتان في Map.entry تسمحان باستخراج مفتاح و قيمة زوج معين.

انظر المثال:

بالإضافة إلى الــ view السابقة توجد أخرى, للحصول على كافة المفاتيح نستخدم الدالة keySet :

للحصول على كافة القيم نستخدم الدالة values :

ملاحظات:

  1. أي تغيير يحدث في الـــ Map سيتم اجراؤه أيضا على الــ view المقابلة.
  2. حذف الزوج أو العنصر الحالي (باستخدام remove) في الــ view يقتضي أيضا حذف العنصر المقابل له في الــ Map.
  3. لا يُسمح بإضافة عناصر مباشر من داخل الــ view.

مثال جامع :

ليكن لدينا الكلاس التالي:

نُعطي الكلاس EnregistrementProduit المعرف كما يلي: 

  1. قم بتعريف الدالة enreg بحيث تقوم بتخزين الــ Produit الذي تم تمريره كوسيط داخل جدول الهاش prod. نعتبر أن idProduit هو المفتاح.
  2. قم أيضا بتعريف الدالة chercherProduits بحيث تقوم بإعادة مجموعة الــ Products ذو quantite أقل من 15000.

الحل:

 

ترتيب الــ Collections

يتم تحديد نوع الترتيب المُستخدم في الــ Collections باستخدام احدى الواجهتين :

Comparable Or Comparator

1 – الواجهة java.lang.Comparable

جميع الكائنات التي تستخدم natural sort order يجب أن تقوم بعمل implement لهذه الواجهة:

بعض الفئات مثل String, File, Date, Integer, Float الخ, عملت implement لهذه الواجهة.

Comparable تحتوي على دالة واحدة فقط هي compareTo التي تعيد احدى القيم التالية:

  • قيمة اكبر من الصفر, إذا كان الكائن الحالي (current object) اكبر من الكائن الذي تم تمريره.
  • اصغر من الصفر, إذا كان الكائن الحالي (current object) اصغر من الكائن الذي تم تمريره.
  • صفر, اذا تطابق الكائنان.

مثال:

قم بكتابة كلاس باسم TestComparable يقوم بعمل implement للواجهة Comparable و يسمح بترتيب عناصر موجودة في HashMap على النحو التالي:

  1. الدالة void tri (Object [ ]o)l تسمح بترتيب جدول من Object.
  2. الدالة ArrayList triHashMap (HashMap map)l تستقبل HashMap كوسيط و تُعيد ArrayList يحتوي على قيم الــ HashMap بشكل مرتب.
  3. مع العلم أنه يجب اعادة تعريف الدالة CompareTo حتى توافق المتطلبات.

الحل:

 

2 – الواجهة java.util.Comparator

هذه الواجهة تُمثل sort order كيفي, أي أن المبرمج هو من يحدده. حيث تسمح بترتيب الكائنات التي لم تقم بعمل implement للواجهة Comparable أو تعريف sort order مختلف عن الذي تقدمة الواجهة السابقة.

 

الدالة compare تعيد:

  • قيمة اكبر من الصفر, إذا كان o اكبر من v.
  • اصغر من الصفر, إذا كان o اصغر من v.
  • صفر, اذا كان o و v متطابقان.

قم بعمل المثال السابق باستخدام الواجهة Comparator.

الـــ Algorithmes :

مجموعة الـــ algorithmes التي تُمكن من التعامل مع الـــ collections موجودة في الكلاس Collections (انتبه جيداً, الكلاس Collections يختلف تماما عن الواجهة Collection). تم تعريف جميع تلك الدوال على أنها static.

نبدأ بالـــ algorithmes الخاصة بــ List :

الترتيب:

  • sort(List list)l : ترتيب List
  • sort(List list,Comparator comp)l : ترتيب List باستخدام comparator

الــ Merge :

shuffle(List liste)l  : يخلط العناصر بطريقة عشوائية

البحث:

  • binarySearch(List list, Object element)l : البحث عن عنصر باستخدام خوارزمية البحث الثنائي
  • binarySearch(List list, Object element, Comparator comp)l : البحث عن عنصر باستخدام خوارزمية البحث الثنائي اعتمادا على comparator.

بعض العمليات الأخرى:

  • reverse(List liste)l : قلب عناصر List
  • fill (List liste, Object element)l : تقوم بعمل initialization لـ List باستخدام element
  • copy(List dest, List src)l  : نسخ src داخل dest

أيضا هناك خوارزميات أخرى يمكن تطبيقها على جميع الــ collections مثل :

  • min (Collection)l : للبحث عن أصغر عنصر
  • max (Collection)l : للبحث عن أكبر عنصر

ملاحظات:

  • لاستخدام الدالة sort(List)l يجب أن تقوم كافة عناصر الـــ List بعمل implement للواجهة Comparable وإلا سيتم رفع استثناء من نوع ClassCastException.
  • الكلاس Collections يحتوي على دوال خاصة تسمح بالحصول على نسخة multi-thread و Unmodifiable لمعظم الــ interfaces  الموجودة مثل Collection, List, Map,Set, SortedMap, SortedSet :
  1. synchronizedXXX ( XXX)l : للحصول على نسخة multi-thread من الكائنات التي قامت بعمل impelement للواجهة XXX
  2. unmodifiableXXX (XXX)l : للحصول على نسخة Unmodifiable من الكائنات التي قامت بعمل impelement للواجهة XXX

مثال على خاصية الــ Unmodifiable :

 

محاولة تغيير Unmodifiable List تقتضي اصدار استثناء من نوع java.lang.UnsupportedOperationException.

مثال على خاصية الــ synchronization :

استدعاء الدالة synchronizedXXX يُعيد كائن يدعم الــ synchronization لبعض العمليات مثل الاضافة و الحذف. أما بالنسبة لعملية المرور على العناصر باستخدام Iterator فيجب وضع الكود المخصص داخل synchronized bloc. يجب أيضا وضع استدعاء الدالة داخل الجزء المخصص.

محاولة اضافة عنصر جديد أثناء المرور على عناصر المجموعة, تقتضي اصدار استثناء من نوع java.util.ConcurrentModificationException.

 

مراجع:

Développons en Java – Jean Michel DOUDOUX

Notes de cours du mon Prof Joseph NDONG

Cours Java – Bernard Caylux

(1622)

أحمد محمد أحمد محمد ، مهندس برمجيات و طالب دكتوراه في مجال Complex Networks Analysis. مهتم بالبرمجة و دراسة الشبكات.

Comment(3)

LEAVE YOUR COMMENT

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

مشاركة