اذهب إلى المحتوى

مفهوم دوال التقطيع 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:

الطريقة دالة التقطيع
طريقة القسمة h(x) = x mod m
طريقة الضرب h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1}

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

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

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

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

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

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

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

الطريقة الصيغة
السبر الخطي h(x, i) = (h”(x) + i) mod m
السبر التربيعي h(x, i) = (h”(x) + c1*i + c2*i^2) mod m
السبر المضاعف h(x, i) = (h1(x) + i*h2(x)) mod m

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

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

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

x m = 100 - غير أولي m = 101 - أولي
723 23 16
103 3 2
738 38 31
292 92 90
61 61 61
87 87 87
995 95 86
549 49 44
991 91 82
757 57 50
920 20 11
626 26 20
557 57 52
931 31 23
619 19 13

قيم التقطيع للأنواع الشائعة في 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.

اقرأ أيضًا


تفاعل الأعضاء

أفضل التعليقات

لا توجد أية تعليقات بعد



انضم إلى النقاش

يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.

زائر
أضف تعليق

×   لقد أضفت محتوى بخط أو تنسيق مختلف.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   جرى استعادة المحتوى السابق..   امسح المحرر

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • أضف...