الخرائط Maps في جافا

يُمكِننا التفكير بمصفوفةٍ مكونةٍ من N عنصر كما لو كانت طريقةً لربط عنصرٍ معينٍ بالأعداد الصحيحة 0، و 1، وصولًا إلى N-1. إذا كان i أحد تلك الأعداد الصحيحة، يُمكِننا استرجاع get القيمة المرتبطة بالعدد i، كما يُمكِننا وضع put عنصرٍ جديدٍ في الموضع i، حيث تُعرِّف العمليتان get و put ماهية المصفوفة.

تُعدّ الخرائط maps نوعًا عامًا من المصفوفة؛ حيث يُمكِننا تعريفها باستخدام عمليتي get و put، إلا أنّ هذه العمليات لا تَكون مُعرَّفةً للأعداد الصحيحة 0، و 1، وصولًا إلى N-1، وإنما تَكون مُعرَّفةً لكائناتٍ objects عشوائية من نوع T، كما يرتبط بكل كائنٍ منها كائنٌ من نوعٍ آخر مختلف S.

تستخدِم بعض لغات البرمجة مصطلح المصفوفة الارتباطية associative array بدلًا من مصطلح الخريطة، كما تَستخدِم نفس الترميز مع المصفوفات العادية والارتباطية. فقد ترى ترميزًا، مثل A["fred"]‎ للإشارة إلى العنصر المرتبط بالسلسلة النصية "fred" بمصفوفةٍ ارتباطية A.

لا تَستخدِم جافا نفس الترميز العادي مع الخرائط، ولكن الفكرة تبقى واحدةً بالنهاية؛ حيث تُشبه الخريطة أي مصفوفة، ولكن تكون فهارسها indices كائناتٍ objects وليس أعدادًا صحيحة. يُطلَق على الكائن الذي يعمل مثل فهرسٍ index ضمن خريطة اسم مفتاح key؛ أما العنصر المرتبط بالمفتاح، فيُطلَق عليه اسم قيمة value. يُقابل كل مفتاحٍ قيمةً واحدةً على الأكثر، ولكن يُمكِن لنفس القيمة الارتباط بعدة مفاتيحٍ مختلفة. يُمكنك أن تنظر للخريطة على أنها مجموعةٌ من الارتباطات associations، حيث يُمثِّل كل ارتباطٍ زوج مفتاحٍ وقيمة key/value pair.

واجهة تمثيل الخرائط

تُوفِّر جافا الواجهة java.util.Map لتمثيل الخرائط، حيث تتضمَّن تلك الواجهة التابعين get و put بالإضافة إلى عدة توابعٍ أخرى للعمل مع الخرائط في العموم. تُعدّ الواجهة Map<K,V>‎ من الأنواع ذات المعاملات غير محدَّدة النوع parameterized، وتَملُك تحديدًا معاملي نوع، الأول هو K، والثاني هو V؛ حيث يُخصِّص K نوع الكائن المُستخدَم مثل مفتاح بالخريطة؛ بينما يُخصِّص V نوع الكائن المُستخدَم مثل قيمة. على سبيل المثال، تَربُط خريطةٌ من النوع Map<Date,Button>‎ قيمًا من النوع Button بمفاتيحٍ من النوع Date؛ بينما تَربُط خريطةٌ من النوع Map<String,String>‎ قيمًا بمفاتيحٍ من نفس النوع String.

نستعرِض فيما يلي بعضًا من التوابع المتاحة لمُتغيّر map يُمثِل خريطةً من النوع Map<K,V>‎ لنوعين K و V:

map.get(key)‎: يُعيد كائنًا من النوع V يُمثِّل القيمة المرتبطة بالمفتاح key؛ ويُعيد القيمة الفارغة null إذا لم تحتوي الخريطة على قيمةٍ مقابلةٍ للمفتاح المُمرَّر، أو في حالة كانت القيمة الفارغة مرتبطةً صراحةً بذلك المفتاح. يُشبه كثيرًا استدعاء map.get(key)‎ لخريطة map استخدام A[key]‎ مع مصفوفة A، ولكن لا يحدث اعتراضٌ exception من النوع IndexOutOfBoundsException في حالة الخرائط.
map.put(key,value)‎: يَربُط قيمة value المُمرَّرة مع المفتاح key، حيث يجب أن يكون key من النوع K، وأن يَكون value من النوع V. إذا كانت الخريطة تَربُط بالفعل قيمةً ما مع نفس المفتاح المُخصَّص، يَستبدِل التابع القيمة الجديدة بالقيمة القديمة، ويُشبه ذلك الأمر A[key] = value المُستخدَم مع المصفوفات.
map.putAll(map2)‎: إذا كانت map2 خريطةً أخرى من النوع Map<K,V>‎، فسينسخ التابع جميع القيم الموجودة بها إلى map.
map.remove(key)‎: إذا كانت map تَربُط قيمةً معينةً بالمفتاح key، فسيحذف التابع هذا الارتباط من الخريطة map.
map.containsKey(key)‎: يُعيد القيمة المنطقية true إذا كانت الخريطة map تَربُط قيمةً معينةً بالمفتاح المُمرَّر key.
map.containsValue(value)‎: يُعيد القيمة المنطقية true إذا كانت الخريطة map تَربُط القيمة المُمرَّرة value بأي مفتاحٍ ضمن الخريطة.
map.size()‎: يُعيد قيمةً من النوع int تُمثِّل عدد الارتباطات بين المفاتيح والقيم الموجودة بالخريطة map.
map.isEmpty()‎: يُعيد القيمة المنطقية true إذا كانت الخريطة map فارغةً، أي لا تَربُط أي قيمٍ بأي مفاتيح.
map.clear()‎: يحذف جميع الارتباطات الموجودة بالخريطة map.

يُعدّ التابعان put و get أكثر التوابع استخدامًا من بين التوابع الأخرى المُعرَّفة بالواجهة Map، حيث يقتصر استخدام الكثير من التطبيقات للخرائط على هذين التابعين فقط دون غيرهما، ويكون عندها استخدام الخريطة بنفس سهولة استخدام أي مصفوفةٍ عادية.

تُوفِّر جافا الصنفين TreeMap<K,V>‎ و HashMap<K,V>‎ المُنفِّذين للواجهة Map<K,V>‎، حيث تُخزِّن الخرائط من الصنف TreeMap ارتباطات المفاتيح بالقيم key/value associations ضمن شجرة tree، وتكون الارتباطات مُرتَّبةً بحسب مفاتيحها. يَعنِي ذلك ضرورة إمكانية موازنة مفتاحٍ بآخر، أي يجب أن تُنفِّذ أصناف المفاتيح الواجهة Comparable<K>‎، أو أن نُوفِّر كائنًا من النوع Comparator لإجراء الموازنة من خلال تمريره معاملًا لباني الصنف TreeMap. تستخدم الخرائط من النوع TreeMap التابع compareTo()‎، أو compare()‎ كما هو الحال مع الأطقم من النوع TreeSet للموازنة بين مفتاحين، وهو ما قد يَتسبَّب بنتائجٍ غير مُتوقَّعة إذا لم يَكُن التابع compareTo()‎ مُعرَّفٌ بما يتوافق مع مفهوم التساوي.

لا تُخزِّن الخرائط من النوع HashMap الارتباطات وفقًا لأي ترتيبٍ معين، ولذلك ليس من الضروري لأصناف المفاتيح المُستخدَمة أن تكون قابلة للموازنة، لكن يتوجب عليها تعريف التابعين equals()‎ و hashCode()‎ تعريفًا ملائمًا، وهو ما تَضمَنه غالبية أصناف جافا القياسية. تُعدّ غالبية العمليات على الخرائط من الصنف HashMap أكثر كفاءةً عمومًا بالموازنة مع نظيراتها بالصنف TreeMap، لذلك اِستخدِم الصنف HashMap، خاصةً إذا كان استخدامك للخريطة مقتصرًا على التابعين put و get؛ واِستخدِم الصنف TreeMap إذا كنت تحتاج إلى خاصية الترتيب.

لنفحص الآن مثالًا على استخدام الخرائط. تعرَّضنا في مقال البحث والترتيب في المصفوفات Array في جافا للصنف PhoneDirectory المُستخدَم لربط أرقام الهواتف بأسماء الأشخاص، حيث يُعرِّف ذلك الصنف العمليتين التاليتين:

addEntry(name,number)‎
getNumber(name)‎‎

حيث name و number من النوع String. يشبه الصنف PhoneDirectory خريطةً يؤدي تابعيها addEntry و getNumber دور عمليتي put و get على الترتيب.، ولا نُعرِّف عادةً بأي تطبيقٍ حقيقي مثل ذلك الصنف، وإنما نَستخدِم ببساطةٍ خريطةً من النوع Map<String,String>‎ على النحو التالي:

Map<String,String> directory = new TreeMap<>();

لاحِظ أننا استخدمنا الصنف TreeMap حتى تكون أرقام الهواتف مُرتَّبةً بحسب أسماء الأشخاص، ويُمكِننا الآن ببساطة إضافة رقم هاتف إلى الخريطة باستدعاء directory.put(name,number)‎ أو استرجاع رقم الهاتف المرتبط باسمٍ معينٍ باستدعاء directory.get(name)‎.

العروض والأطقم الجزئية والخرائط الجزئية

لا تُعدّ الخرائط من النوع Map تجميعاتٍ من النوع Collection، لعدم تنفيذ الخرائط جميع العمليات المُعرَّفة بالتجميعات.لا تحتوي الخرائط مثلًا على مُكرِّرات iterators، ولكن قد نحتاج في بعض الأحيان إلى المرور عبر جميع الارتباطات الموجودة ضمن خريطةٍ معينة، وهو ما تُوفِّره جافا لحسن الحظ. بفرض أن map مُتغيّرٌ من النوع Map<K,V>‎، فسيُعيد التابع التالي طقمًا يحتوي على جميع الكائنات المُمثِلة لمفاتيح الارتباطات ضمن الخريطة map:

map.keySet()

تَكون القيمة المعادة كائنًا مُنفِّذًا للواجهة Set<K>‎، تُمثِّل عناصره مفاتيح الخريطة. قد تظن أن التابع keySet()‎ يُنشِئ طقمًا جديدًا، ويُضيف إليه جميع مفاتيح الخريطة، ثم يُعيده، ولكن هذا غير صحيح؛ فليس الكائن الذي يُعيده الاستدعاء map.keySet()‎ كائنًا مستقلًا، وإنما هو بمثابة عرض view للكائنات الفعلية المُخزَّنة بالخريطة. على الرغم من تنفيذ العرض للواجهة Set<K>‎، إلا إنه يُنفِّذها بحيث تشير التوابع المُعرَّفة ضمنه إلى مفاتيح الخريطة مباشرةً. إذا حذفت مفتاحًا من عرضٍ على سبيل المثال، فسيُحذف أيضًا مع قيمته value المرتبط بها من الخريطة. في المقابل، لا يُمكِنك إضافة كائنٍ إلى عرض؛ لأن عملية إضافة مفتاح بدون تخصيص قيمته المرتبط بها لا يكون لها معنى. بناءً على ما سبق، يَعمَل التابع map.keySet()‎ بكفاءةٍ عاليةٍ حتى مع الخرائط الكبيرة.

إذا كان لديك طقمٌ من النوع Set، يُمكِنك بسهولةٍ الحصول على مُكرّرٍ من النوع Iterator، واستخدامه للمرور عبر جميع عناصر ذلك الطقم واحدًا تلو الآخر؛ وتستطيع كذلك استخدِام مُكرِّرٍ للطقم المُمثِّل لمفاتيح خريطة للمرور عبر جميع الارتباطات الموجودة بها. فإذا كانت map خريطةً من النوع Map<String,Double>‎، يُمكِننا كتابة ما يَلي:

Set<String> keys = map.keySet();     // The set of keys in the map.
Iterator<String> keyIter = keys.iterator();
System.out.println("The map contains the following associations:");
while (keyIter.hasNext()) {
   String key = keyIter.next();  // استرجع المفتاح التالي
   Double value = map.get(key);  // استرجع قيمة ذلك المفتاح
   System.out.println( "   (" + key + "," + value + ")" );
}

أو قد نتجنَّب الاستخدام الصريح للمُكرّر باستخدام حلقة التكرار for-each على النحو التالي:

System.out.println("The map contains the following associations:");
for ( String key : map.keySet() ) {  // "for each key in the map's key set"
    Double value = map.get(key);
    System.out.println( "   (" + key + "," + value + ")" );
}

إذا كانت map من النوع TreeMap، تكون مفاتيحها مُرتّبةً بالطقم، ويَمُرّ المُكرِّر بناءً على ذلك على المفاتيح بحسب ترتيبها التصاعدي؛ أما إذا كانت من النوع HashMap، يمر بها المُكرِّر مرورًا عشوائيًا غير مُتوقَّع.

تُعرِّف الواجهة Map عرضين views آخرين. إذا كان map مُتغيِّرًا من النوع Map<K,V>‎، سيعيد التابع التالي تجميعةً من النوع Collection<V>‎ تحتوي على جميع قيم الارتباطات المُخزَّنة بالخريطة:

map.values()

نظرًا لأن الخريطة قد تَربُط نفس القيمة بأكثر من مجرد مفتاحٍ واحد، كان من الضروري أن تَكون القيمة المعادة من النوع Collection وليس من النوع Set؛ لأن الأول قادرٌ على تخزين عناصرٍ مُكرَّرة بخلاف الثاني.

ألقِ نظرةً على التابع التالي، الذي يُعيد طقمًا يحتوي على جميع الارتباطات الموجودة بالخريطة.

map.entrySet()

لاحِظ أن عناصر الطقم هي كائناتٌ تنتمي للواجهة Map.Entry<K,V>‎ المُعرَّفة مثل واجهةٍ ساكنة static nested داخل الواجهة Map<K,V>‎، ولهذا يَحتوِي اسمها على نقطة، وهذا يَعنِي أن القيمة المُعادة من التابع map.entrySet()‎ هي من النوع Set<Map.Entry<K,V>>‎. في تلك الحالة، يكون معامل النوع type parameter ذاته نوعًا ذا معاملات غير محدَّدة النوع parameterized type. قد يبدو ذلك مُربِكًا في البداية، ولكنه يَعنِي ببساطة أن عناصر الطقم هي نفسها من النوع Map.Entry<K,V>‎.

لا تختلف المعلومات المُخزَّنة بالطقم المُعاد من استدعاء map.entrySet()‎ عن تلك المُخزَّنة بالخريطة ذاتها، حيث يُوفِّر الطقم فقط عرضًا مختلفًا لنفس المعلومات، كما يُوفِّر بعض العمليات الآخرى. يَحتوِي كل كائنٍ من النوع Map.Entry على زوج مفتاح/قيمة، ويُعرِّف التابعين getKey()‎ و getValue()‎ لاسترجاعهما، كما يُعرِّف التابع setValue(value)‎ لضبط القيمة. عند استدعاء التابع setValue على كائنٍ من النوع Map.Entry، تُعدَّل قيمته بالخريطة أيضًا كما لو كنا قد استدعينا التابع put المُعرَّف بالخريطة.

يُمكِننا استخدام طقم الارتباطات المُعاد من التابع لطباعة جميع القيم والمفاتيح الموجودة بالخريطة، ويُعدّ هذا أكثر كفاءةً من استخدام طقم المفاتيح لطباعة نفس المعلومات (كما فعلنا بالمثال السابق)؛ لأننا لن نضطّر لاستدعاء التابع get()‎ لمعرفة القيمة المرتبطة بكل مفتاح. تَنفِّذ الشيفرة التالية ذلك بفرض أن map خريطةٌ من النوع Map<String,Double>‎:

Set<Map.Entry<String,Double>> entries = map.entrySet();
Iterator<Map.Entry<String,Double>> entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) {
   Map.Entry<String,Double> entry = entryIter.next();
   String key = entry.getKey();  // ‫استرجع المفتاح من entry
   Double value = entry.getValue();  // استرجع القيمة
   System.out.println( "   (" + key + "," + value + ")" );
}

أو قد نَستخدِم حلقة التكرار for-each لشيفرةٍ أكثر وضوحًا:

System.out.println("The map contains the following associations:");
for ( Map.Entry<String,Double> entry : map.entrySet() ) {
   System.out.println( "   (" + entry.getKey() + "," + entry.getValue() + ")" );
}

يُعدّ هذا مثالًا جيدًا على استخدام var للتصريح عن المتغيرات (انظر مقال مفهوم التصريحات (declarations) في جافا)، ويُمكِّننا هذا من كتابة الشيفرة على النحو التالي:

var entries = map.entrySet();
var entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) { . . .

ملاحظة: تتطلَّب تلك الشيفرة الإصدار 10 من جافا على الأقل.

تُستخدَم العروض بأماكنٍ أخرى غير الخرائط، حيث تُعرِّف الواجهة List<T>‎ مثلًا قائمةً جزئيةً sublist مثل عرضٍ view لجزءٍ من القائمة الأصلية. بفرض أن list تُنفِّذ الواجهة List<T>‎، ألقِ نظرةً على الشيفرة التالية:

list.subList( fromIndex, toIndex )

حيث أن fromIndex و toIndex أعدادٌ صحيحة. يعيد التابع عرضًا يُمثِل ذلك الجزء من القائمة المُتضمِّن للعناصر الواقعة بين الموضعين fromIndex و toIndex، متضمنًا الأول دون الثاني، مما يَسمَح بإجراء أيٍّ من العمليات المُعرَّفة بالقوائم على جزءٍ معينٍ من قائمة. ليست القوائم الجزئية sublists قوائمًا مستقلةً؛ أي أنه في حال إجراء أي تعديلٍ عليها، فسيُنفَّذ أيضًا على القائمة الأصلية.

يُمكِننا كذلك الحصول على عرضٍ لتمثيل طقمٍ جزئي subset من طقمٍ معين. إذا كان set طقمًا من النوع TreeSet<T>‎، فسيعيد الاستدعاء التالي:

 7set.subSet(fromElement,toElement)‎ 7

طقمًا من النوع Set<T>‎ يحتوي على جميع عناصر الطقم set الواقعة بين fromElement و toElement. يجب أن يكون المعاملان fromElement و toElement كائنين من النوع T. فإذا كان words طقمًا من النوع TreeSet<String>‎ على سبيل المثال، وكانت جميع عناصره سلاسلًا نصيةً مُكوَّنةً من أحرفٍ أبجدية بحالةٍ صغيرة lower case، فسيحتوي الطقم الجزئي subset المُعاد من الاستدعاء words.subSet("m","n")‎ على جميع عناصر الطقم الأصلي البادئة بالحرف "m".

يُعدّ الطقم الجزئي عرضًا view لجزءٍ معينٍ من الطقم الأصلي، حيث لا يتضمَّن إنشاءه نَسْخًا لأي عنصرٍ من العناصر الأصلية؛ أي إذا عدَّلت الطقم الجزئي بإضافة عناصرٍ إليه أو بحذفها، ستُعدَّل عناصر الطقم الأصلي أيضًا. يُعيد الاستدعاء set.headSet(toElement)‎ عرضًا view مُكوَّنًا من جميع عناصر الطقم set الأقل من قيمة toElement؛ بينما يُعيد الاستدعاء set.tailSet(fromElement)‎ عرضًا مُكوَّنًا من جميع عناصر الطقم set الأكبر من قيمة fromElement.

يُعرِّف الصنف TreeMap<K,V>‎ ثلاثة عروضٍ لتمثيل خرائطٍ جزئية submaps، والتي هي أيضًا خريطةٌ من النوع Map تحتوي على جزءٍ من مفاتيح الخريطة الأصلية إلى جانب قيمها المرتبطة بها. إذا كان map مُتغيرًا من النوع TreeMap<K,V>‎، وكان fromKey و toKey من النوع K، فسيُعيد الاستدعاء map.subMap(fromKey,toKey)‎ عرضًا يحتوي على جميع مفاتيح وقيم الخريطة map بشرط وقوع المفتاح بين fromKey و toKey.

يتوفَّر أيضًا التابعين map.headMap(toKey)‎ و map.tailMap(fromKey)‎ المُشابهين تمامًا للتابعين headSet و tailSet. لنفترض أن phoneBook خريطةٌ من النوع TreeMap<String,String>‎، حيث تُمثِّل مفاتيحها أسماء أشخاص، بينما تُمثِّل قيمها values أرقام هواتف هؤلاء الأشخاص. تطبع الشيفرة التالية أرقام هواتف الأشخاص الموجودين بالخريطة phoneBook شرط أن تبدأ أسماؤهم بالحرف "M":

Map<String,String> ems = phoneBook.subMap("M","N");
    // 1

if (ems.isEmpty()) {
   System.out.println("No entries beginning with M.");
}
else {
   System.out.println("Entries beginning with M:");
   for ( Map.Entry<String,String> entry : ems.entrySet() )
      System.out.println( "   " + entry.getKey() + ": " + entry.getValue() );
}

[1] تحتوي هذه الخريطة الجزئية على الارتباطات، التي مفتاحها أكبر من أو يُساوِي "M" وأقل من "N".

يُمكِننا التفكير بالأطقم الجزئية subsets والخرائط الجزئية submaps كما لو كانت عملية بحثٍ مُعمَّمةٍ تُمكِّننا من العثور على جميع العناصر الواقعة ضمن نطاقٍ معينٍ من القيم بدلًا من مجرد العثور على قيمةٍ واحدة. إذا خزَّنا مثلًا قاعدة بياناتٍ database لمجموعةٍ من المناسبات events ضمن خريطةٍ من النوع TreeMap<Date,Event>‎، بحيث يُمثِّل المفتاح تاريخ توقيت المناسبة. بفرض أردنا عرض قائمة المناسبات الواقعة بتاريخٍ معين، مثل July 4, 2018، يُمكِننا ببساطة الحصُول على خريطةٍ جزئيةٍ تحتوي على جميع المفاتيح الواقعة من التاريخ ‎12:00 AM, July 4, 2018 حتى التاريخ ‎12:00 AM, July 5, 2018، ثم طباعة جميع الارتباطات الموجودة بتلك الخريطة الجزئية، ويُعرَف هذا النوع من البحث باسم الاستعلام ضمن نطاقٍ جزئي subrange query، وهو شائعٌ جدًا.

جداول Hash والشيفرات المعماة

تُنفِّذ جافا الصنفين HashMap و HashSet باستخدام بنية بياناتٍ data structure تُعرَف باسم جدول hash. لا نحتاج في العموم لفهم طريقة عمل تلك الجداول لنتمكَّن من استخدام الصنفين HashSet و HashMap، لكن يجب أن يكون كل مبرمجٍ على اطلاعٍ بطريقة عملها.

تُعدّ جداول Hash حلًا فعالًا لمشكلة البحث، فهي تُخزِّن أزواجًا من المفاتيح keys والقيم values مثل الصنف HashMap، وإذا كان لدينا مفتاحٌ معين، يُمكِننا البحث عن القيمة المقابلة له ضمن الأزواج المخزَّنة بالجدول؛ بينما لايكون هناك أي قيمٍ، إذا اِستخدَمنا جدول hash لتنفيذ طقمٍ، ويكون السؤال الوحيد هو: هل المفتاح موجودٌ بالطقم أم لا؟ ويبقى علينا البحث عن المفتاح لاختبار إذا كان موجودًا أم لا.

بالنظر إلى غالبية خوارزميات البحث، حيث يَكون الغرض هو العثور على عنصرٍ معين، فستَجِد أنها تضطّر للمرور عبر مجموعةٍ من العناصر الأخرى، والتي نحن في الحقيقة غير مهتمين بها إطلاقًا. إذا أردنا مثلًا العثور على قيمةٍ معينةٍ ضمن قائمةٍ list غير مُرتَّبة، فسنمر على جميع عناصر القائمة واحدًا تلو الآخر حتى نعثُر على ذلك العنصر الذي نبحث عنه؛ أما إذا كان لدينا شجرة بحثٍ ثنائية binary search tree، فسنبدأ من جذر الشجرة root، ثم نستمر بالتحرُّك إلى أسفل الشجرة حتى نعثر على العنصر المطلوب؛ بينما إذا أردت البحث عن زوج مفتاح/قيمة ضمن جدول hash، نستطيع الذهاب مباشرةً إلى موضع العنصر المطلوب دون الحاجة للمرور عبر أي عناصرٍ اخرى؛ حيث يُستخدَم المفتاح لحساب الموضع المُخزَّن به العنصر.

ربما تتساءل الآن عن كيفية فعل بذلك. لنفترض أن مفاتيح جدولٍ معينٍ مُكوَّنةٌ من الأعداد الصحيحة الواقعة بين 0 و 99، فيُمكِننا إذًا تخزين أزواج المفاتيح والقيم key/value pairs ضمن مصفوفةٍ A مُكوَّنةٍ من 100 عنصر. بناءً على ذلك، يكون الزوج ذو المفتاح K مُخزَّنًا بعنصر المصفوفة A[K]‎. يَعنِي ذلك، أننا نستطيع الذهاب مباشرةً إلى الموضع المُتضمِّن لزوجٍ معين بناءً على مفتاحه.

تَكْمُن المشكلة في وجود عددٍ كبيرٍ جدًا من المفاتيح المُحتمَلة لدرجةٍ يَستحيل معها استخدام مصفوفةٍ بموضعٍ لكل مفتاحٍ مُحتمَل. قد يكون المفتاح أي قيمةٍ من النوع int، وعندها سنحتاج إلى مصفوفةٍ تحتوي على أكثر من 4 بليون موضع، وهو ما سيُمثِل هدرًا كبيرًا للمساحة إذا كنا سنُخزِّن بالنهاية بضعة آلافٍ من العناصر فقط. وقد يكون المفتاح أي سلسلةٍ نصية string بأي طول، وسيكون في تلك الحالة عدد المفاتيح المُحتمَلة لا نهائيًا، وسيَستحِيل عندها من الأساس استخدام مصفوفة بموضعٍ لكل مفتاحٍ مُحتمَل.

بالرغم من ذلك، تُخزِّن جداول hash البيانات ضمن مصفوفة، حيث يَعتمِد فهرس index مفتاحٍ معينٍ على المفتاح ذاته؛ أي لا يكون الفهرس هو نفسه المفتاح، ولكنه يُحسَب على أساسه. يُطلَق على فهرس مفتاح معين اسم الشيفرة المُعمَّاة hash code لذلك المفتاح؛ بينما يُطلَق اسم دالة التعمية hash function على الدالة المُستخدَمة لحساب الشيفرة المعمَّاة hash code لمفتاحٍ معين. إذا أردنا العثور على مفتاحٍ معينٍ ضمن جدول hash، سنحتاج فقط إلى حساب الشيفرة المعمَّاة الخاصة بذلك المفتاح، ثم سنذهب مباشرةً إلى موضع المصفوفة المُخصَّص لتلك الشيفرة. على سبيل المثال، إذا كانت الشيفرة المعمَّاة تُساوِي 17، علينا فحَص موضع المصفوفة رقم 17.

نظرًا لوجود مواضع مصفوفة أقل من المفاتيح المُحتمَلة، قد يؤدي ذلك إلى محاولة تخزين مفتاحين أو أكثر بنفس موضع المصفوفة، وهو ما يُعرَف باسم التصادم collision. لا يُعدّ التعارض خطأً error؛ لأنه لا يُمكِننا رَفض مفتاحٍ معينٍ لمجرد وجود مفتاحٍ آخر صَدَفَ أن كان له نفس الشيفرة المعمَّاة hash code. ومع ذلك، يجب أن يَكون جدول hash قادرًا على معالجة التعارضات بطريقةٍ معقولة. بلغة جافا: يَحمِل كل موضع مصفوفة قائمةً مترابطةً linked list من أزواج المفاتيح والقيم key/value pairs؛ وفي حال وجود عنصرين بنفس الشيفرة المعمَّاة، فسيُخزَّن كلاهما بنفس القائمة المترابطة. يوضح الشكل التالي جدول hash.

يوجد بالشكل الموضح بالأعلى عنصران لهما نفس الشيفرة المعمَّاة 0؛ بينما لا يوجد أي عنصرٍ بشيفرة معمَّاة تُساوي 1؛ في حين يوجد عنصرٌ واحدٌ فقط بشيفرةٍ معمَّاة تُساوِي 2، وهكذا. إذا كان جدول hash مُصمَّمًا تصميمًا مناسبًا، يجب أن يكون طول غالبية القوائم المترابطة linked lists مُساويًا للصفر أو للواحد، وأن يكون طولها في المتوسط أقل من الواحد.

على الرغم من أنه ليس من الضروري للشيفرة المعمَّاة لمفتاحٍ معين أن تأخذك مباشرةً إلى ذلك المفتاح، فليس هناك أكثر من مجرد عنصرٍ واحدٍ أو اثنين تحتاج للمرور بهما قبل العثور على المفتاح المطلوب، حيث يجب أن يكون عدد العناصر الموجودة بالجدول أقل من عدد مواضع المصفوفة ليعمَل ذلك بالشكل المناسب في العموم. بلغة جافا: عندما يجتاز عدد العناصر 75% من حجم المصفوفة، فإنها تُستبدَل بواحدةٍ جديدةٍ أكبر منها، وتُنقَل بالطبع جميع العناصر من المصفوفة القديمة إلى المصفوفة الجديدة، ولهذا يتسبَّب أحيانًا إدخال عنصرٍ واحد بالجدول إلى تَغيُّر ترتيب عناصره تمامًا.

سنوضِح الآن طريقة الحصول على الشيفرات المعمَّاة hash codes، حيث يَملُك كل كائنٍ بلغة جافا شيفرةً معمَّاة، ويُعرِّف الصنف Object التابع hashCode()‎ الذي يُعيد قيمةً من النوع int. عندما نُخِّزن كائنًا، وليَكُن اسمه obj، بجدول hash يَحتوي على عدد N من المواضع، فسنحتاج إلى شيفرةٍ معمَّاةٍ تقع بين 0 وN-1؛ حيث تُحسَب تلك الشيفرة باستخدام الآتي:

 Math.abs(obj.hashCode()) % N

أي أنها تُساوِي باقي قسمة القيمة المُطلَقة المُعادة من obj.hashCode()‎ على N. لاحِظ ضرورة استخدام Math.abs؛ لأن قيمة obj.hashCode()‎ قد تكون سالبة، ونحن بالتأكيد نريد فهرس مصفوفةٍ موجب.

لتعمل التعمية hashing على النحو الصحيح، يجب أن يَكون لأيِّ كائنين objects متساويين وفقًا للتابع equals()‎ نفس الشيفرة المعمَّاة، ويَستوفِي الصنف Object ذلك الشرط لحسن الحظ؛ لأن التابعين equals()‎ و hashCode()‎ معتمدان على عنوان موضع الذاكرة الخاص بالكائن. يعيد مع ذلك كثيرٌ من الأصناف classes تعريف التابع equals()‎، كما رأينا بمقال مفهوم البرمجة المعممة Generic Programming؛ فإذا أعدت تعريف التابع equals()‎ ضمن صنفٍ معين، وكنت تَنوِي استخدام كائناته مفاتيحًا ضمن جداول hash، فلا بُدّ من إعادة تعريف التابع hashCode()‎ ضمن ذلك الصنف أيضًا.

يُعيد الصنف String على سبيل المثال تعريف التابع equals()‎ ليَضمَن تَساوِي كائنين من النوع String فيما إذا كانا يحتويان على نفس متتالية المحارف، كما يُعيد تعريف التابع hashCode()‎ ليَحسِب الشيفرة المعمَّاة من محارف السلسلة النصية بدلًا من حسابها بناءً على موضعها بالذاكرة. لا يوجى داعٍ للقلق بشأن أصناف جافا القياسية Java's standard classes؛ فهي تُعرِّف التابعين على النحو الصحيح. اهتم فقط بالأصناف التي تكتبها بنفسك واحرص على تعريف التابعين معًا إذا أردت تعريف إحداهما.

تشبه كتابة دوال التعمية hash function الفن؛ فمن أجل كتابة دالة تعميةٍ جيدة، ينبغي لها أن تُوزِّع المفاتيح المُحتمَلة بالتساوي على طول الجدول، وإلا فقد تتركَّز عناصره ضمن جزءٍ معينٍ فقط من المواضع المتاحة، وسينمو عندئذٍ حجم القوائم المترابطة linked lists الخاصة بتلك المواضع بصورةٍ كبيرة، مما يؤدي إلى الحد من كفاءة الجدول، والذي هو السبب الرئيسي لوجودها أساسًا. لن نُغطِي التقنيات المُستخدَمة لإنشاء دوال التعمية، فهي لا تُعدّ جزءًا أساسيًا من موضوع الكتاب.

ترجمة -بتصرّف- للقسم Section 3: Maps من فصل Chapter 10: Generic Programming and Collection Classes من كتاب Introduction to Programming Using Java.