ما هي جدول التجزئة (Hash Table) وكيف تحقق البحث بتعقيد O(1)؟

Question

Accepted Answer

جدول التجزئة (hash map) يخزن أزواج **key → value** ويوفر إدراج وبحث وحذف بمتوسط **O(1)**. يعمل بتمرير كل مفتاح عبر **دالة تجزئة (hash function)** التي تعينه على فهرس في مصفوفة أساسية ("دلو").

## كيفية العمل

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## مثال

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## التعقيد الزمني

| العملية | المتوسط | الأسوأ حالة |
|---|---|---|
| إدراج | O(1) | O(n) |
| بحث | O(1) | O(n) |
| حذف | O(1) | O(n) |

حالة **الأسوأ** O(n) تحدث عندما يتصادم العديد من المفاتيح في نفس الدلو.

## المقارنات والخصائص

- **المميزات:** وصول سريع جداً قائم على المفتاح؛ مفاتيح مرنة.
- **العيوب:** لا يوجد ترتيب للمفاتيح؛ ذاكرة إضافية؛ حالة أسوأ O(n)؛ تحتاج إلى دالة تجزئة جيدة.

## لماذا يهم

جداول التجزئة هي في الواقع الهيكل الأكثر استخداماً في الممارسة العملية — حيث تقف وراء القواميس والمجموعات والمخزن المؤقت وفهارس قواعد البيانات وإزالة التكرار.

استبدال المسح الخطي بالبحث في جدول التجزئة هو أحد أكثر الطرق شيوعاً لتحويل خوارزمية O(n²) إلى O(n).