جداول التجزئة
جداول التجزئة: بحث سريع
- جدول التجزئة يخزن عناصرًا يمكنك العثور عليها بسرعة كبيرة — عادةً في خطوة واحدة.
- هو قائمة من الخانات. دالة التجزئة تحول المفتاح إلى رقم خانة.
- بدلاً من البحث في كل عنصر، تقفز مباشرة إلى الخانة التي ينتمي إليها المفتاح.
دالة تجزئة
- دالة التجزئة تأخذ مفتاحًا وترجع فهرس خانة من
0إلىsize - 1. - نفس المفتاح يعطي دائمًا نفس الخانة، حتى تتمكن من العثور عليه لاحقًا.
- بسيط: اجمع رموز الأحرف، ثم خذ
% sizeللبقاء ضمن النطاق.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
التصادمات
- يمكن لمفتاحين مختلفين أن يتجزأا إلى نفس الخانة. هذا تصادم.
- الجدول له عدد محدود من الخانات، لذا التصادمات لا مفر منها كلما امتلأ.
- نحتاج إلى قاعدة لما نفعله عندما تكون الخانة المطلوبة مشغولة بالفعل.
المسح الخطي
- المسح الخطي: إذا كانت الخانة ممتلئة، جرب الخانة التالية، ثم التالية، مع الالتفاف حول.
- استمر في التحرك
(slot + 1) % sizeحتى تجد خانة فارغة. - بالأسفل،
AوFكلاهما يريدان الخانة 0، لذا يُدفعFإلى الخانة 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
البحث عن مفتاح
- لـإيجاد مفتاح: تجزئته، ثم امسح للأمام، مقارنة كل خانة بالمفتاح.
- توقف وأرجع الفهرس عند العثور عليه.
- إذا وصلت إلى خانة فارغة (أو فحصت كل خانة)، فإن المفتاح غير موجود — أرجع
-1.
لماذا جداول التجزئة سريعة
- مع القليل من التصادمات، الإدراج والبحث يأخذ حوالي خطوة واحدة — نسمي هذا
O(1). - كلما امتلأ الجدول، أصبح المسح أطول، لذا من الحكمة ترك بعض الخانات فارغة.
- في أسوأ الحالات (كل شيء يتصادم) يتباطأ إلى مسح خطي،
O(n).
أخطاء شائعة
- دالة التجزئة تربط المفتاح بفهرس في الجدول.
- يمكن أن تتصادم مفتاحان عند نفس المؤشر. تعامل معها، كما تفعل هذه الدرس، باستخدام المسح الخطي؛ الترابط هو الطريقة الشائعة الأخرى.
الآن جرب بنفسك
- بِنِ الثلاثة أجزاء: دالة التجزئة، الإدراج بالمسح، والبحث.
- كل مهمة تتحقق من دالتك على حالات التصادم والالتفاف حول.
- اضغط على تحقق من الإجابة لاختبارها.
التجزئة إلى دلو
دالة التجزئة ترسل كل مفتاح إلى دلو؛ التصادمات تشابك.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب hash_key(key, size). أضف رموز الأحرف في key (استخدم ord(ch)) وأرجع المجموع % size، بحيث يكون الناتج من فتحة 0 إلى size - 1. مثال: hash_key("AB", 10) هو (65 + 66) % 10 = 1. السلسلة الفارغة تُعطي 0.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
hash_key مُقدَّم. اكتب insert(table, key) باستخدام الحفر الخطي: اذهب إلى فتحة تجزئة المفتاح؛ طالما أن تلك الفتحة ممتلئة (ليست None)، انتقل إلى (slot + 1) % len(table)؛ ضع المفتاح في أول فتحة فارغة وأرجع فهرسه.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
hash_key مُقدَّم. اكتب find(table, key) الذي يرجع فهرس key، أو -1 إذا كان مفقوداً. ابدأ من فتحة التجزئة وحفر للأمام، ومقارنة كل فتحة. توقف عند فتحة فارغة (المفتاح غير موجود). تأكد من انتهائه حتى لو كانت الجدول ممتلئاً — لا تكرر إلى الأبد أبداً.
اضغط تشغيل لرؤية المخرجات هنا.