السلام عليكم ورحمة الله وبركاته
سبق وعرفنا ما هو جدول التلبِيد Hash Table في مقالنا السابق، وهذا الدرس نستأنف شرحه ونبرمجه، فنختم به الفصل الخامس من كتاب (استيعاب الخوارزميات)، وبالله التوفيق!

تطبيقات جدول التلبِيد

لعلك تساءلت فيمَ ينفعك جدول التلبِيد؟ فما استعمالاته؟
إن أكبر الشركات في مجال التقانة تستعمله، مثل شركة جوجل Google، وقد أتى صاحب الكتاب بثلاثة استعمالات، الأول للبحث والثاني لحذف المكرر والأخير للتخبئة caching.

الأول، البحث

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

فكيف ستبرمجه وأي شيء ستستعمل؟
جدول التلبيد أيها القارئ الكريم، فهي مناسبة لتعليق شيء بشيء، الاسم تعلق الرقم به، ثم تبحث عنه بسرعة.

برمجة ذلك في بايثون سهل يسير، أولا ننشئ جدول التلبيد:

phone_book = {}

ثم تضيف الاسم والرقم هكذا:

phone_book["allunlocker"] = 777563332

انتهينا!
ومثل هذا يكون عند إدخال عنوان الموقع، فعنوان الموقع ذاك يُتَرجم إلى أرقام، فكل عنوان مرتبط برقم، فاسم موقعنا bassye.org لكنه يُتَرجم إلى أرقام، وهذا يتم باستعمال جدول التلبيد ولا إشكال!

الثاني، حذف المكرر

وأحسن مثال لذلك صندوق الانتخابات!
هب أن عندك الصندوق، وأنت عليه مسؤول، فأنت تقول للناس: (كل واحد منكم سيصوت مرة واحدة)، ومن صوت مرتين فلا تُقبَل منه إلا واحدة.
سيأتي محمد ويصوت، وستكتب اسمه كاملًا على لائحة المصوتين، فإن أتاك غدًا مرة ثانية وأراد التصويت فإنك فاضحه إذا استعمل نفس الاسم الذي صوت به.

تمر الأيام ويصوت الناس وتزداد الأسماء على لائحة المصوتين،

أفأنت مقتدر على قراءة لائحة المصوتين كل مرة لتفضح الغشاش المصوت مرتين؟

استعمل جدول التلبيد يا صاحبي!

برمجة ذلك يسير، سننشئ جدول تلبيد نخزن فيه المصوتين:

 

voted = {}

ثم إن أتى فلان ليصوِّت ترى أهو في اللائحة أم لا؟
نستعمل وظيفة get في بايثون:

value = voted.get("Ali")

سترجع الوظيفة get قيمة إن كان علي في اللائحة، وإن لم يكن فيها سترجع None، أي لا شيء هنا.

هلَّا برمجت هذا قبل رؤية الحل باستعمال أداة الشرط if؟

هذه وظيفة تصويت، تعطيها اسم المصوت فإن كان لم يصوِّت أخذت بصوته، وإن كان صوَّت لم تقبل منه ذلك:

voted = {}
def check_voter(voter):
    if voted.get(voter):
        print("انصرف أيها الغشاش")
    else:
        voted[voter] = True
        print("أخذنا صوتك، مع السلامة!")

الثالث، التخبئة caching

إن كنت تعمل على موقع أو استعملت بعض البرامج فلعلك سمعت قولهم cache، ويعني التخبئة، مثل ذاكرة التخبئة cache memory وهي ذاكرة مؤقتة ليست بدائمة.

إن فتحت موقعنا فأنت ترسل طلبًا إلى خادومنا server وتقول لنا هات صفحة الموقع، والخادوم سينهض من أريكته ليحضر لك الصفحة ثم يرسلها لك، قد يتأخر بضع ثوانٍ، ونهاية تُعرَض الصفحة على حاسوبك.

هب أن خادومنا قد شاخ وهرم فلا يقوى على خدمة جمع غفير من الناس يفتحون الموقع في لحظة، ومنهم ثلة تفتح نفس الصفحة مرة بعد مرة، فقل لي أينهض الخادوم الهرم ليحضر لهذه الثلة نفس الشيء مرة بعد مرة؟

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

هذا مفهوم ذاكرة التخبئة على وجه الاختصار، وسنبرمجها باستعمال جدول التلبيد!
برمجة ذلك سهل، ننشئ جدول تلبيد ونسميه التخبئة cache، ثم نكتب وظيفة تأخذ الرابط وترى، هل الرابط في التخبئة أم لا؟
إن كان فيها أرجعت لنا الرابط، وإلا أضافت الرابط إلى جدول التلبيد.

برمجته:

cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
    data = get_data_from_server(url)
    cahce[url] = data
    return data

كل ما سبق كان يسيرا، ولم نغص في التفاصيل حتى الآن، وذلك لأسباب، أولها الكتاب للمبتدئين ولا يتعمق ذاك التعمق، وثانيها كما -قال الكاتب-: (كل لغات البرمجة عندها جدول التلبيد جاهزًا للاستعمال فلا تحتاج لبرمجته). تعمق الكاتب قليلًا في آلية جدول التلبيد، وأنا سأخبرك بما قاله، أما التعمق الحق فأنا إن شاء اللّٰه مفصِّله لكن في سلسلة مقالات ثانية عن الخوارزميات، أما هذه فستكون مُيسَّرة للمبتدئين.

التصادم

إني محدثك في هذه الفقرة عن أداء جدول التلبيد، وأنت لن تفهمه إن لم تفهم التصادم collisions.
يقول الكاتب إنه لم يكن دقيقًا لما قال لك إن وظيفة التلبيد function hash ترجع قيمة مختلفة لكل مُدخل، أي أن وظيفة التلبيد لن تربط أو تقرن أكثر من مُدخل بخانة في الصفيفة array، فكتابة وظيفة تفعل هذا شبه مستحيل إن لم يكن مستحيلًا!

هب أن عندك صفيفة فيها ٢٨ خانة ستخزن فيها السلعة وسعرها، وهذه الخانات مرتبة ترتيبًا هجائيًا، أي إذا كانت السلعة تبدأ بالألف كانت في الخانة الأولى، وإن كانت تبدأ بالباء كانت في الخانة الثانية وهكذا…

تأتيك السلعة الأولى بحرف الألف، تأخذها وظيفة التلبيد وتربطها بالخانة الأولى في الصفيفة،

ثم تأتيك سلعة ثانية بحرف الباء وتدخلها في الخانة الثانية.

تأتيك السلعة الثالثة بحرف الألف، ستأخذها وظيفة التلبيد وتضعها في الخانة الأولى، لكن مهلًا، تصيح الوظيفة قائلة: الخانة مشغولة، ففيه سلعة أخرى، يا ويلتاه ما العمل!

هذا اسمه التصادم: أن تربط وظيفة التلبيد مدخلين بخانة واحدة مشغولة غير خالية.

ذكر الكاتب حلًا لهذا وكان استعمال لائحة مترابطة linked list، التي درسناها في هذا المقال:

استيعاب الخوارزميات -الفصل الثاني، الدرس الأول- اللائحة المترابطة والصفيفة

سنضع أكثر من سلعة تبدأ بنفس الحرف في مكان واحد باستعمال اللائحة المترابطة:

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

انظر في الصورة الآنفة:

كل السلع في خانة واحدة وباقي الصفيفة فارغة!

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

وظيفة التلبيد المعتبرة تضع كل قيمة في خانة مختلفة:

أما وظيفة التلبيد السيئة تضع كل قيمة في خانة واحدة:

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

الأداء

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

أما خوارزمية البحث الثنائية فأسرع:

انظر كيف سيكون الأمر في جدول التلبيد مع الثابت الزمني:

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

جدول التلبيد في الحالة المتوسطة سريع جدًا، لكنه في أسوأ حالة يكون خطيًا O(س).

راجع الدروس السابقة إن لم تفهم ما أعنيه

انظر لهذه المقارنة بين جدول التلبيد والصفيفة واللائحة المترابطة:

انظر الحالة المتوسطة لجدول التلبيد، سريع مثل الصفيفة في البحث، وسريع مثل اللائحة المترابطة في الإدخال والحذف، جمع الحُسنيين!
لكنه في أسوأ حالة كان الأبطأ، لذا عليك تجنب التصادم، ولأجل الإتيان بوظيفة تلبيد جيدة، وعليك فهم معامل الحمل الحمل Load Factor.

معامل الحمل

معامل الحمل = عدد عناصر جدول التلبيد مقسومًا على عدد الخانات.

إذا قسمت عدد المدخلات المخزونة على سعة جدول التلبيد ظفرت بهذا المعامل. فإذا كان في جدول التلبيد خمسة عناصر وكان سعته عشرة خانات، فمعامل الحمل يكون خمسة من عشرة 0.5، أي النصف (قسمنا خمسة على عشرة).

كلما ازدادت العناصر المخزنة ارتفع هذا المعامل، حتى إذا امتلأ جدول التلبيد بلغ الواحد الصحيح 1، وإن زاد عن الواحد الصحيح فهذا يدل على أن حجم المدخلات يفوق حجم الخانات.

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

لو أن عندك مئتي عنصر والخانات مئة فقط؟
اقسم ٢٠٠ على ١٠٠ وسيكون الناتج ٢، أي تحتاج إلى خانات جديدة، أي عليك توسعة جدول التلبيد.

نفع معامل الحمل أنه يُنبئك عن مدى حاجة جدولك إلى التوسيع، فكلما اقترب من الامتلاء علمت أن الوقت قد حان لتوسعته، زيادة حجمه.

قال الكاتب إن زاد عن 0.7 فعليك توسعة جدولك، جدول التلبيد.

الخاتمة

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

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

أرجو منك تقييم كفاءة المعلومات من أجل تزويدي بالملاحظات والنقد البناء في خانة التعليقات أو عبر حساب الموقع، والسلام عليكم ورحمة اللّٰه تعالى وبركاته.