جدول تلبيد هو أحد بنى البيانات في علم الحاسوب يملك

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

علاوةً على ذلك، جدول العنونة سنطبقها بواسطة مصطفة أي جداول العنونة مباشرة (directed adress table) سيكون [T[0,...,m-1 وكل مكان في الجدول يسمى خلية أو slot الذي يلائم مفتاحا من المجموعة الكلية إذا الجدول لم يحوِ أيّ مفتاح قيمته k حينها [nil=T[k

جداول التلبيد ذات العنونة المباشرة (المفتوحة)

علاوةً على ذلك، العنونة المباشرة هي طريقة بسيطة التي تعمل كما يجب عندما المجموعة الكلية للمفاتيح U تكون صغيرة نسبيا لنفترض انه لتطبيق معين طلب مجموعة ديناميكية حيث ان لكل فرد في المجموعة أخذ مفتاح من {U={1,2,3,...,m-1 عندما m ليس عددا ضخما سنفترض أن المفاتيح المأخوذة مختلفة تماما.

direct-adress-search(T,k)

في هذا الإطار، في الحالة المثالية، يفترض بجدول التلبيد، ربط كل مفتاح بحجرة معينة، ولكن في الواقع ذلك يجعل زمن البحث فيه عن القيم المتضاربة كبيراً جداً، لذلك تم إيجاد عدة حلول ونماذج لجداول التلبيد يُفترض فيها وجود قيم متضاربة على حساب تخفيض زمن البحث.

return T[k]

Direct-adress-insert(T,x)

enter x in the haed of T[h(key(x))]

chained-hash-search(T,k)
search item with key value k in the list of T[h(k)]
chained-hash-delete(T,x)

دوال تلبيد

إذا كان التوزيع معطى أي انه لكل مفتاح عندها:(h(k)=floor(km

ثمة عدة حالات بناء على المعلومات التي لدينا عن التوزيع:

علاوةً على ذلك، في الحالات الأخرى وعند الافتراض ان المفاتيح ارقام طبيعية نستطيع استخدام الطرق التالية :

T[key[x<-x

Direct-adress-delete(T,x)

T[key[x<-NIL

علاوةً على ذلك، كل الخوارزميات في الأعلى سريعة وفعالة حيث ان كل منها يقوم بعدد قليل من العمليات (O(1

h:U->{0,1,...,m-1}

من جانب آخر، نقول ان المفتاح k منقول (hashes)للخلية (h(k ; أي انه (h(k يسمى قيمة الهاش (hash value).

من جهة ثانية، الطريقة الأفضل لحل هذه المشكلة هي السلسلة (chaining) وهناك طريقة أخرى وهي العنونة المفتوحة (open addressing)

وعلى صعيد آخر، تسمى هذه الظاهرة بالتشابك في جدول الهاش أو collision ولهذه المشكلة يوجد حلول جيدة وفعالة.

من جانب آخر، مشكلة من نوع اخر تظهر في الهاش وهي عندما يكون هناك مفتاحان k,t قيم الهاش خاصتهما متشابه أي: (h(t)=h(k

كذلك، قد يتبادر إلى الذهن حل عن طريق جعل h دالة عشوائية وساعتها سيكون هنالك اقل تشابك ولكن هذا الحل ليس طبيعي لأننا نريد الدالة h قطعية (deterministic)

* طريقة القسمة أي: h(k)=m mod k

وفي هذا الصدد، * طريقة الضرب أي: ((h(k)=(floor(m(1 kA mod عندما: A بين 0 و 1

حل مشكلة التشابك على طريق السلسلة

في طريقة السلسلة (chaining) كل التشابكات في نفس الخلية نسلسلها بواسطة سلسلة
عند حل التشابكات بواسطة السلسلة من السهل ان نطبق عمليات الجدول T
Chained-hash-Insert(T,x)

delete x from T[h(key(x))]

في هذا الإطار، عملية الإدخال تتم ب-(O(1 وقت اما البحث ففي الحالة الأسوأ يكون البحث (|O(|T[h[key ولكن في حالات الوسط يكون (O(1 اما الحذف (O(1 عندما تكون السلسلة ذو اتجاهين اما إذا كانت ذو اتجاه واحد عندها سيتطلب منا البحث اولا من ثم الحذف أي انه سيتطلب وقتا كما في البحث

جداول هاش

ومن ناحية أخرى، عندما تكون المجموعة K (القاموس) صغيرة جدا بالنسبة ل-U جدول هاش سيتطلب مكان اقل من جداول عنونة مباشرة أي سيتطلب جدول هاش (|O(|K بالرغم من أن بحث قيمة معينة في الجدول سيكون كذلك (O(1 المشكلة الوحيدة هو ان البحث في جدول الهاش هو متوقع بينما في العنونة المباشرة البحث هو (O(1 دائما

في هذا الإطار، الصعوبة في جداول العنونة المباشرة هي كبر المجموعة U حيث ان القيام بحفظ مصفوفة بحجم |U| غير واقعي وغير تطبيقي ومن ناحية أخرى قد تكون المجموعة K صغيرة كثيرا بالنسبة ل-U وعندها أغلب الأماكن في U ستكون حتما غير نافعة.

وفي هذا الصدد، بالعنونة المباشرة حفظنا المفتاح k في الخلية k اما في الهاش فهذا المفتاح سوف يحفظ في (h(k أي اننا سوف نستعمل دالة هاش (hash function) لحساب الخلية التي سنحفظ فيها المفتاح k،

تحليل الهاش مع سلسلة

من جانب آخر، في السيناريو الأسوأ فعالية الهاش مع سلسلة جدا سيئة : كل n المفاتيح موزعين لنفس الخلية ونكون سلسلة طويلة جدا والبحث عندها سيكون (O(n +الوقت المطلوب لحساب دالة الهاش وهو ليس بأفضل من البحث في سلاسل عادية

وفي هذا السياق، اما في السيناريو الوسط فعالية الهاش تقاس بمدى توزيع الدالة h للقيم بين المفاتيح سنفترض ان التوزيع سيكون بالتساوي أي ان الاحتمال بان قيمة معينة تذهب إلى مفتاح متساوية بين كل المفاتيح وكذلك سنفترض ان حساب دالة الهاش هو (O(1

اثبات :

من جانب آخر، ومن القانونين في الأعلى نستنتج ان كبر الجدول يجب أن يكون مشابها لعدد القيم المراد تخزينها أي بحالة وجود (O(n قيم عندها كبر الجدول هو (O(n وعندها تكون العلمليات كل واحد منها تنفذ ب-(O(1 وقت

وفي هذا الصدد، في جدول هاش مع سلسلة فيه التوزيع متساو لكل المفاتيح بحث فاشل يقوم ب-(O(1+a فعاليات (وقت الفعالية)

الوقت المتوقع هو : (O(1+a.

قانون :

علاوةً على ذلك، بما ان التوزيع متساو لكل المفاتيح الاحتمال بان مفتاح K يذهب لخلية معينة متساو لكل الخلايا (m خلايا) لذا الوقت المتوسط للبحث الفاشل عن k مساو تماما للوقت المتوسط لبحث أحد السلاسل والطول المتوقع لسلسلة كهذه هو مقدم الكثافة أو a أي ان وقت البحث المتوسط هو a ومع حساب دالة الهاش :

كذلك، في جدول هاش مع تشابك وفي الجدول التوزيع للمفاتيح متساو, بحث ناجح متوسط وقت البحث هو: (O(1+a.