الخوارزميات للمحترفين مفهوم دوال التقطيع Hash Functions في الخوارزميات

تكون دالةُ ‎h()‎ دالةَ تقطيع Hash Functions إذا كانت تأخذ عنصرًا ‎x ∈ X‎ من أيّ حجم، وتعيد قيمة ‎y ∈ Y‎ من حجمٍ ثابت ‎y‎ = h (x)‎‎.

تتميز دوّال التقطيع النموذجية بالخصائص التالية:

• تتصرف مثل توزِيعات منتظمة uniform distribution
• دوال التقطيع حتمية deterministic، حيث ينبغي أن تعيد الدالة ‎h(x)‎ القيمة نفسها دائمًا لعنصر ‎x‎ محدد.
• ينبغي أن تكون سريعة الحساب (ذات تعقيد زمني O (1)‎‎).

حجم قيمة التقطيع عمومًا أصغر من حجم البيانات المُدخلة: ‎|y| < |x|‎، علاوة على أنّ دوال التقطيع غير قابلة للعكس، لأنه يجوز أن تكون لقيمتين مختلفتين قيمة التقطيع نفسها، أو بتعبير رياضي:

∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)

قد تكون المجموعة X منتهية أو غير منتهية، أما ‎Y‎ فهي دائمًا مجموعة منتهية. وتُستخدم دوال التقطيع في الكثير من مجالات الحوسبة مثل هندسة البرمجيات والتشفير وقواعد البيانات والشبكات وتعلُُّم الآلة ونحو ذك، وهناك العديد من أنواع دوال التقطيع، ولكل منها خصائص مميزة.

تكون قيمة التقطيع عددًا صحيحًا في الغالب، ومعظم لغات البرمجة لديها توابع ودوال خاصة لحساب قيم التقطيع، مثل الدالة GetHashCode()‎ في لغة C#‎‎ التي تعيد قيمة من النوع ‎Int32‎ (عدد صحيح من 32 بتة) لكل الأنواع. وكذلك في لغة جافا هناك تابع ‎hashCode()‎ يحسب قيمة التقطيع -من النوع int- لكل صنف من أصناف جافا.

طرق تعريف دوال التقطيع Hash methods

هناك عدة طرق لتعريف دوال التقطيع، يمكننا أن نفترض دون الإخلال بالعمومية، أنّ المجموعة X تساوي مجموعة الأعداد الصحيحة الموجبة، وx عنصر منها: أي ‎x ∈ X = {z ∈ ℤ: z ≥‎ 0}‎‎. وليكن m عددًا، ويُفضّل أن يكون أوليًا (شرط أن لا تكون قيمته قريبة جدًا من أي قوّة للعدد 2).

فيما يلي طريقتان لحساب قيم التقطيع الخاصة بعناصر X:

جداول التقطيع

تُستخدم دوال التقطيع مع جداول التقطيع hash tables لحساب الفهارس في مصفوفة من الحجرات array of slots، وجدول التقطيع هي هيكلية بيانات لتنفيذ القواميس dictionaries وهي بيانات من نوع مفتاح-قيمة.

التعقيد الزمني لتطبيقات لجداول التقطيع يساوي في العادة O (1)‎‎ للعمليات التالية:

• إدراج البيانات بحسب قيمة المفتاح.
• حذف البيانات بحسب قيمة المفتاح.

يمكن أن يكون لعدة مفاتيح نفس التقطيع (الحجرة)، وعندئذ فهناك طريقتان لحل هذه المشكلة:

• السلسلة Chaining: تُستخدم القوائم المترابطة لتخزين العناصر التي لها نفس قيمة التقطيع في الحجرة.
• العنونة المفتوحة Open addressing: يُخزّن عنصر واحد على الأكثر في كل حجرة.

تُستخدم الطرق التالية لحساب تسلسلات المسبار probe sequences المطلوبة في العنونة المفتوحة:

الدوال h"(x)‎‎ و h1(x)‎‎ و h2(x)‎‎ هي دوال مساعدة، وi ينتمي إلى المجموعة {0, 1, ..., m-1}، وc1 و c2 ثابتتان موجبتان.

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

لنأخذ المثال التالي، ليكن ‎x ∈ U{1, 1000}‎‎ و h = x mod m‎. يوضح الجدول التالي قيم التقطيع في حالة كان العدد m أوليا أو غير أولي، تشير النصوص الغليظة إلى قيم التقطيع المتساوية.

قيم التقطيع للأنواع الشائعة في C#‎‎

سنستعرض في هذه الفقرة قيم التقطيع hash codes التي ينتجها التابع ‎GetHashCode()‎ لأنواع C#‎‎المضمّنة في فضاء الاسم ‎System‎. يمكنك الاطلاع على توثيقات هذه الأنواع من github.

القيم المنطقية Boolean

1 إذا كانت القيمة صحيحة true، أو 0 خلاف ذلك.

الأنواع Byte و UInt16 و Int32 و UInt32 و Single

قيمة العنصر (تُحوّل عند الضرورة إلى النوع Int32).

النوع SByte

((int)m_value ^ (int)m_value << 8);

النوع Char

(int)m_value ^ ((int)m_value << 16);

النوع Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

النوعان Int64 و Double

تطبيق المعامل Xor بين أدنى 32 بتّة وأعلى 32 بتة في العدد المؤلف من 64 بتة.

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

الأنواع UInt64 و DateTime و TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

النوع Decimal

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Object

النوع Object هو الصنف الجذري الذي تنحدر منه جميع الكائنات.

RuntimeHelpers.GetHashCode(this);

استخدمنا التطبيق الافتراضي فهرس كتلة المزامنة sync block index.

السلاسل النصية String

يعتمد حساب قيمة التقطيع على نوع نظام التشغيل (Win32 أو Win64)، وإمكانية استخدام تقطيع السلاسل النصية العشوائية randomized string hashing، إضافة إلى الإصدار ووضعية المنقّح.

في حالة المنصة Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
   hash1 = ((hash1 << 5) + hash1) ^ c;
   c = s[1];
   if (c == 0)
       break;
   hash2 = ((hash2 << 5) + hash2) ^ c;
   s += 2;
}
return hash1 + (hash2 * 1566083941);

ValueType

يتم البحث عن أول حقل غير ساكن non-static field، وتُحسب قيمة التقطيع خاصته، إذا لم يكن للنوع أيّ حقل غير ساكن، تُعاد قيمة التقطيع الخاصة بذلك النوع. لا يمكن الاعتماد على قيمة التقطيع الخاصة بمتغير عضو ساكن static member، لأنه قد تنتجُ حلقة أبدية إذا كان نوع ذلك العضو يساوي النوع الأصلي.

النوع Nullable‎‎

return hasValue ? value.GetHashCode() : 0;

المصفوفات Array

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

ترجمة -بتصرّف- للفصل 43 من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقال السابق: أمثلة على أشهر خوارزميات المخططات والأشجار
• مدخل إلى الخوارزميات
• أمثلة عن أنواع الخوارزميات
• تعقيد الخوارزميات Algorithms Complexity