كيف تُحسّن جداول التجزئة الخوارزميات؟

Question

Accepted Answer

تعطي **جدول التجزئة** (hash map) أو القاموس **O(1) متوسط** للبحث والإدراج والحذف. استبدال البحث المتكرر بعمليات بحث فورية يحوّل العديد من خوارزميات O(n²) إلى O(n) مقابل ذاكرة O(n).

## الفكرة الأساسية

بدلاً من البحث في قائمة في كل مرة، احفظ القيم المرئية في جدول تجزئة وتحقق من العضوية في وقت ثابت.

## مثال: مجموع عددين في O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

بدون الخريطة هذا O(n²)؛ معها، ممر واحد فقط.

## الاستخدامات الشائعة

- **إزالة التكرارات / عضوية** مع مجموعة.
- **عد التكرارات** (`Counter`).
- **تجميع / فهرسة** حسب المفتاح.
- **تخزين مؤقت / تذكر** النتائج.

## التعقيد

- **متوسط:** O(1) لكل عملية. **الأسوأ:** O(n) عند التصادمات الكثيفة. **الذاكرة:** O(n).

## مزالق شائعة

يجب أن تكون المفاتيح **قابلة للتجزئة** وثابتة. التصادمات في الحالات الأسوأ تقلل الأداء. جداول التجزئة غير مرتبة (استخدم البدائل المرتبة إذا كان الترتيب مهماً).

## لماذا يهم

التجزئة هي أكثر تحسين شيوعاً في مقابلات البرمجة والأنظمة الحقيقية — فهي تحول "البحث مراراً وتكراراً" إلى "البحث مرة واحدة".

تبادل المساحة بالسرعة هو رافعة هندسية متكررة.

عد التكرارات والتخزين المؤقت والفهرسة كلها تعتمد على هذه الفكرة الواحدة.