Hash Tables Basics
الفكرة الجوهرية
نريد الوصول لأي عنصر فوراً، مثل المصفوفة، لكن المفاتيح قد تكون نصوصاً (Strings) وليست أرقاماً متسلسلة.
الحل: دالة (Hash Function) تحول المفتاح إلى رقم (Index).
- سريعة الحساب.
- توزع المفاتيح بالتساوي (Distribute Evenly) لتجنب التكتل.
- TableSize يفضل أن يكون عدداً أولياً (Prime) .
Collision Resolution Strategies
ماذا لو نتج نفس الـ Index لمفتاحين مختلفين؟ (تصادم!)
1. Separate Chaining
اجعل كل خانة في الجدول تحتوي على قائمة متصلة (Linked List).
عند التصادم، أضف العنصر الجديد للقائمة.
[1] -> Data1 -> Data2
[2] -> Data3
الأكثر أماناً وسهولة .
2. Open Addressing
إذا كانت الخانة مشغولة، ابحث عن خانة أخرى فارغة في الجدول نفسه.
- Linear Probing: جرب الخانة التالية (+1, +2, ...). .
- Quadratic Probing: جرب بتربيع المسافة ($+1^2, +2^2, ...$) لتجنب التكتل .
Binary Heap (Priority Queue)
Heap Structure & Order
- Structure Property: شجرة ثنائية مكتملة (Complete Binary Tree). تملأ من اليسار لليمين.
- Order Property (Min-Heap): كل أب يجب أن يكون أصغر من أو يساوي أبناءه. (الجذر هو الأصغر دائماً) .
تمثيل الشجرة في مصفوفة (Array Implementation)
Root at index 1
Heap Operations
1. Insert (Percolate Up)
لإضافة عنصر $X$:
1. ضعه في أول خانة فارغة في نهاية المصفوفة (للحفاظ على الهيكل).
2. قارنه بأبيه. إذا كان $X$ أصغر، بَدّل بينهما.
3. كرر الصعود حتى يستقر في مكانه الصحيح .
2. DeleteMin (Percolate Down)
لحذف أصغر عنصر (الجذر):
1. احذف الجذر (الفراغ يصبح في القمة).
2. خذ آخر عنصر في المصفوفة وضعه في الجذر.
3. قارنه بأبناءه. بَدّل مع الابن الأصغر.
4. كرر النزول حتى يستقر .
Heap Array Indices
إذا بدأت المصفوفة من Index 1:
عقدة عند $i$:
• الابن الأيسر: $2i$
• الابن الأيمن: $2i + 1$
• الأب: $\lfloor i/2 \rfloor$
تنبيه: إذا بدأت من 0، المعادلات تتغير!
Is Heap or Hash Table Sorted?
Hash Table: غير مرتبة تماماً (عشوائية).
Heap: مرتبة جزئياً (الأب أصغر من الأبناء)، لكن الأخوة ليس بينهم ترتيب، ولا يمكنك طباعتها مرتبة بسهولة (إلا بـ HeapSort).
للبحث المرتب، استخدم BST.