تنفيذ الخرائط باستخدام التعمية hashing في جافا

سنُعرِّف في هذه المقالة الصنفَ MyBetterMap الذي يُنفِّذ الواجهة Map بشكلٍ أفضلَ من MyLinearMap، كما سنتناول تقنية التعمية hashing التي ساعدتنا على تنفيذ الصنف MyBetterMap بتلك الكفاءة.

التعمية Hashing

بهدف تحسين أداء الصنف MyLinearMap، سنُعرِّف صنفًا جديدًا هو MyBetterMap يحتوي على تجميعة كائناتٍ تنتمي إلى الصنف MyLinearMap. يُقسِّم الصنف الجديد المفاتيح على الخرائط المُرفقة لكي يُقلِّل عدد المُدْخَلات الموجودة في كل واحدةٍ منها، وبذلك يتمكَّن من زيادة سرعة التابع findEntry والتوابع التي تعتمد عليه.

انظر إلى تعريف الصنف:

public class MyBetterMap<K, V> implements Map<K, V> {

    protected List<MyLinearMap<K, V>> maps;

    public MyBetterMap(int k) {
        makeMaps(k);
    }

    protected void makeMaps(int k) {
        maps = new ArrayList<MyLinearMap<K, V>>(k);
        for (int i=0; i<k; i++) {
            maps.add(new MyLinearMap<K, V>());
        }
    }
}

يُمثِل متغير النسخة maps تجميعة كائناتٍ تنتمي إلى الصنف MyLinearMap، حيث يَستقبِل الباني constructor المعاملَ k الذي يُحدِّد عدد الخرائط المُستخدَمة مبدئيًا على الأقل، ثم يُنشِئ التابع makeMaps تلك الخرائط ويُخزِّنها في قائمةٍ من النوع ArrayList.

والآن، سنحتاج إلى طريقة تُمكِّننا من فحص مفتاح معين، وتقرير الخريطة التي ينبغي أن نَستخدِمها. وعندما نَستدعِي التابع put مع مفتاح جديد، سنختار إحدى الخرائط؛ أما عندما نَستدعِي التابع get مع نفس المفتاح، فعلينا أن نتذكّر الخريطة التي وضعنا فيها المفتاح.

يُمكِننا إجراء ذلك باختيار إحدى الخرائط الفرعية عشوائيًا وتعقّب المكان الذي وضعنا فيه كل مفتاح، ولكن كيف سنفعل ذلك؟ يُمكِننا مثلًا أن نَستخدِم خريطةً من النوع Map للبحث عن المفتاح والعثور على الخريطة الفرعية المُستخدَمة، ولكن الهدف الأساسي من هذا التمرين هو كتابة تنفيذٍ ذي كفاءةٍ عاليةٍ للواجهة Map، وعليه، لا يُمكِننا أن نفترض وجود ذلك التنفيذ فعليًا.

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

يُوفِّر أيّ كائنٍ من النوع Object بلغة جافا تابعًا اسمه hashCode، حيث يَحسِب هذا التابع شيفرة التعمية الخاصة بالكائن. يختلف تنفيذ هذا التابع باختلاف نوع الكائن، وسنرى مثالًا على ذلك لاحقًا.

يختار التابعُ المساعدُ التالي الخريطةَ الفرعيّةَ المناسبة لمفتاحٍ معينٍ:

protected MyLinearMap<K, V> chooseMap(Object key) {
    int index = 0;
    if (key != null) { 
        index = Math.abs(key.hashCode()) % maps.size();
    }
    return maps.get(index);
}

إذا كان key يساوي null، فإننا سنختار الخريطة الفرعية الموجودة في الفهرس 0 عشوائيًا. وفيما عدا ذلك، سنَستخدِم التابع hashCode لكي نحصل على عددٍ صحيحٍ، ثم نُطبِّق عليه التابع Math.abs لكي نتأكّد من أنه لا يحتوي على قيمة سالبة، ثم نَستخدِم عامل باقي القسمة ‎\%‎ لكي نحصل على قيمةٍ واقعةٍ بين 0 وmaps.size()-1، وبذلك نضمَن أن يكون index فهرسًا صالحًا للاستخدام مع التجميعة maps دائمًا. وفي الأخير، سيعيد chooseMap مرجًعا reference إلى الخريطة المختارة.

لاحِظ أننا استدعينا chooseMap بالتابعين put وget، وبالتالي عندما نبحث عن مفتاحٍ معينٍ، يُفترَض أن نحصل على نفس الخريطة التي حصلنا عليها عندما أضفنا ذلك المفتاح. نقول هنا أنه يُفترَض وليس حتمًا، لأنه من المحتمل ألا يحدث، وهو ما سنشرح أسبابه لاحقًا.

انظر إلى تعريف التابعين put و get:

public V put(K key, V value) {
  MyLinearMap<K, V> map = chooseMap(key);
    return map.put(key, value);
}

public V get(Object key) {
    MyLinearMap<K, V> map = chooseMap(key);
    return map.get(key);
}

ربما لاحظت أن الشيفرة بسيطةٌ للغاية، حيث يَستدعِي التابعان التابعَ chooseMap للعثور على الخريطة الفرعية الصحيحة، ثم يَستدعِيان تابعًا في تلك الخريطة الفرعية، وهذا كلّ ما في الأمر. والآن، لنفحص أداء التابعين.

إذا كان لدينا عدد مقداره n من المُدْخَلات مُقسّمًا على عدد مقداره k من الخرائط الفرعية، فسيصبح لدينا في المتوسط عدد n/k من المُدْخَلات في كل خريطة. وعندما نبحث عن مفتاح معين، سنضطرّ إلى حساب شيفرة تعميته، والتي تستغرق بعض الوقت، ثم سنبحث في الخريطة الفرعية المقابلة.

لمّا كان حجم قوائم المُدْخَلات في الصنف MyBetterMap أقلّ بمقدار k مرة من حجمها في الصنف MyLinearMap، فمن المُتوقَّع أن يكون البحث أسرع بمقدار k مرة، ومع ذلك، ما يزال زمن التشغيل متناسبًا مع n، وبالتالي ما يزال الصنف MyBetterMap خطيًّا. سنعالج تلك المشكلة في التمرين التالي.

كيف تعمل التعمية؟

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

كمثال على الكائنات غير القابلة للتعديل، سنُعرِّف الصنف SillyString، حيث يُغلِّف ذلك الصنف سلسلةً نصيّةً من النوع String:

public class SillyString {
    private final String innerString;

    public SillyString(String innerString) {
        this.innerString = innerString;
    }

    public String toString() {
        return innerString;
    }

في الواقع، هذا الصنف ليس ذا فائدةٍ كبيرةٍ، ولهذا السبب سميناه SillyString، ولكنه مع ذلك يُوضِّح كيف يُمكِن لصنفٍ أن يُعرِّف دالة التعمية الخاصّة به:

    @Override
    public boolean equals(Object other) {
        return this.toString().equals(other.toString());
    }

    @Override
    public int hashCode() {
        int total = 0;
        for (int i=0; i<innerString.length(); i++) {
            total += innerString.charAt(i);
        }
        return total;
    }

أعاد الصنف SillyString تعريفَ التابعين equals وhashCode، وهذا الأمر ضروري لأننا لو أردنا له أن يَعمَل بشكل مناسب، فلا بُدّ أن يكون التابع equals متوافقًا مع التابع hashCode. يَعنِي هذا أنه لو كان لدينا كائنان متساويين -يُعيد التابع equals القيمة true عند تطبيقه عليهما-، فلا بُدّ أن تكون لهما نفس شيفرة التعمية، ولكن هذا صحيحٌ من اتجاهٍ واحدٍ فقط، فمن المحتمل أن يملك كائنان نفس شيفرة التعمية، ومع ذلك لا يكونان متساويين.

يَستدعِي equals التابعَ toString الذي يعيد قيمةَ متغير النسخة innerString، ولذلك يتساوى كائنان من النوع SillyString إذا تساوى متغير النسخة innerString المُعرَّف فيهما.

يمرّ التابع hashCode عبر محارف السلسلة النصية -من النوع String- ويَحسِب حاصل مجموعها. وعندما نضيف محرفًا إلى عددٍ صحيحٍ من النوع int، ستُحوِّل جافا المحرف إلى عددٍ صحيحٍ باستخدام رقم محرف يونيكود Unicode code point الخاصّ به. يُمكنكِ قراءة المزيد عن أرقام محارف اليونيكود إذا أردت، ولكنه غير ضروريٍّ لفهم هذا المثال.

تُحقِّق دالّةُ التعمية السابقة الشرطَ التالي:

اقتباس

إذا احتوى كائنان من النوع SillyString على سلاسلَ نصيّةٍ متساوية، فإنهما يحصلان على نفس شيفرة التعمية.

تَعمَل الشيفرة السابقة بشكل صحيح، ولكنها ليست بالكفاءة المطلوبة؛ فهي تعيد شيفرة التعمية نفسها لعدد كبير من السلاسل النصية المختلفة؛ فمثلًا لو تكوَّنت سلسلتان من نفس الأحرف مهما كان ترتيبها، فإنهما ستحصلان على نفس شيفرة التعمية، بل حتى لو لم تتكونا من نفس الأحرف، فقد يكون حاصل المجموع متساويًا مثل ac وbb.

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

التعمية والقابلية للتغيير mutation

يُعَد الصنف String غير قابلٍ للتعديل، وكذلك الصنف SillyString؛ وذلك لأننا صرحنا عنه باستخدام final. بمجرد أن تُنشِئ كائنًا من النوع SillyString، فإنك لا تستطيع أن تُعدِّل متغير النسخة innerString المُعرَّف فيه لتجعله يشير إلى سلسلةٍ نصيّةٍ مختلفةٍ من النوع String، كما أنك لا تستطيع أن تُعدِّل السلسلة النصيّةَ التي يشير إليها، وبالتالي ستكون للكائن نفس شيفرة التعمية دائمًا.

ولكن، ماذا يحدث لو كان الكائن قابلًا للتعديل؟ انظر إلى تعريف الصنف SillyArray المطابقَ للصنف SillyString باستثناء أنه يَستخدِم مصفوفةَ محارفَ بدلًا من الصنف String:

public class SillyArray {
    private final char[] array;

    public SillyArray(char[] array) {
        this.array = array;
    }

    public String toString() {
        return Arrays.toString(array);
    }

    @Override
    public boolean equals(Object other) {
        return this.toString().equals(other.toString());
    }

    @Override
    public int hashCode() {
        int total = 0;
        for (int i=0; i<array.length; i++) {
            total += array[i];
        }
        System.out.println(total);
        return total;
    }

يُوفِّر الصنف SillyArray التابع setChar الذي يَسمَح بتعديل المحارف الموجودة في المصفوفة:

public void setChar(int i, char c) {
    this.array[i] = c;
}

والآن، لنفترض أننا أنشأنا كائنًا من النوع SillyArray، ثم أضفناه إلى خريطةٍ كالتالي:

SillyArray array1 = new SillyArray("Word1".toCharArray());
map.put(array1, 1);

شيفرة التعمية لتلك المصفوفة هي 461. والآن إذا عدَّلنا محتويات المصفوفة، وحاولنا أن نسترجعها كالتالي:

array1.setChar(0, 'C');
Integer value = map.get(array1);

ستكون شيفرة التعمية بعد التعديل قد أصبحت 441. بحصولنا على شيفرة تعميةٍ مختلفةٍ، فإننا غالبًا سنبحث في الخريطة الفرعيّة الخاطئة، وبالتالي لن نعثر على المفتاح على الرغم من أنه موجود في الخريطة، وهذا أمرٌ سيّء.

لا يُعَد استخدام الكائنات القابلة للتعديل مفاتيحًا لهياكل البيانات المبنية على التعمية -مثل MyBetterMap وHashMap- حلًّا آمنًا، فإذا كنت متأكّدًا من أن قيم المفاتيح لن تتعدّل بينما هي مُستخدَمة في الخريطة، أو أن أي تعديلٍ يُجرَى عليها لن يؤثر على شيفرة التعمية؛ فلربما يكون استخدامها مناسبًا، ولكن من الأفضل دائمًا أن تتجنَّب ذلك.

تمرين 8

ستُنهِي في هذا التمرين تنفيذ الصنف MyBetterMap، حيث ستجد ملفات شيفرة التمرين في مستودع السلسلة:

MyLinearMap.java: يحتوي على حل تمرين مقالة "تحليل زمن تشغيل الخرائط المُنفَّذة باستخدام مصفوفة" الذي سنبني عليه هذا التمرين.
MyBetterMap.java: يحتوي على شيفرة من نفس المقالة مع إضافة بعض التوابع التي يُفترَض أن تُكملها.
MyHashMap.java: يحتوي على تصوّرٍ مبدئيٍّ -عليك اكماله- لجدولٍ ينمو عند الضرورة.
MyLinearMapTest.java: يحتوي على اختباراتِ وحدةٍ للصنف MyLinearMap.
MyBetterMapTest.java: يحتوي على اختبارات وحدةٍ للصنف MyBetterMap.
MyHashMapTest.java: يحتوي على اختبارات وحدةٍ للصنف MyHashMap.
Profiler.java: يحتوي على شيفرةٍ لقياس الأداء ورسم تأثير حجم المشكلة على زمن التشغيل.
ProfileMapPut.java: يحتوي على شيفرة تقيس أداء التابع Map.put.

كالعادة، عليك أن تُنفِّذ الأمر ant build لكي تُصرِّف ملفات الشيفرة، ثم الأمر ant MyBetterMapTest. ستفشل العديد من الاختبارات؛ وذلك لأنه ما يزال عليك اكمال بعض التوابع.

راجع تنفيذ التابعين put وget من ذات المقالة المشار إليها في الأعلى، ثم أكمل متن التابع containsKey. سيكون عليك استخدام التابع chooseMap، وبعدما تنتهي نفِّذ الأمر ant MyBetterMapTest مرةً أخرى، وتأكّد من نجاح testContainsKey.

أكمل متن التابع containsValue، ولا تَستخدِم لذلك التابع chooseMap. نفِّذ الأمر ant MyBetterMapTest مرةً أخرى، وتأكّد من نجاح testContainsValue. لاحِظ أن العثور على القيمةِ يتطلَّب عملًا أكبر من العثور على المفتاح.

يُعَد تنفيذ التابع containsKey تنفيذًا خطيًّا مثل التابعين put وget؛ لأنه عليه أن يبحث في إحدى الخرائط الفرعية. سنشرح في المقال التالي كيف يُمكِننا تحسين هذا التنفيذ أكثر.

ترجمة -بتصرّف- للفصل Chapter 10: Hashing من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.