Space and Time Trade-Offs II مقايضات المساحة والوقت II

Breaking the $O(\log n)$ barrier with Hashing and mastering external memory with B-Trees. كسر حاجز $O(\log n)$ باستخدام الـ Hashing وإتقان الذاكرة الخارجية باستخدام B-Trees.

Hashing Hashing Collision Resolution Collision Resolution Open Addressing Open Addressing B-Trees B-Trees

Hashing: The $O(1)$ Dream Hashing: حلم الـ $O(1)$

The Dictionary Problem مشكلة القاموس (Dictionary Problem)

We need to implement a set with three operations: Find, Insert, and Delete. Balanced Trees do this in $O(\log n)$. Hashing aims for $O(1)$ on average by trading space. نحتاج لتنفيذ مجموعة بثلاث عمليات: بحث، إدراج، و حذف. الأشجار المتوازنة تفعل ذلك في $O(\log n)$. يهدف الـ Hashing إلى $O(1)$ في المتوسط عن طريق مقايضة المساحة.

The Hash Function $h(K)$ دالة التجزئة (Hash Function) $h(K)$

Maps a key $K$ (large universe) to a small table index $[0, m-1]$. تقوم بتعيين مفتاح $K$ (من نطاق واسع) إلى فهرس جدول صغير $[0, m-1]$.

$h(K) = K \mod m$

Ideally, $m$ should be a Prime Number to minimize patterns. من الناحية المثالية، يجب أن يكون $m$ عدداً أولياً لتقليل الأنماط.

Key: 105 Key: 24
$h(K) \% 10$
0
...
4 -> 24
5 -> 105
...

Handling Collisions معالجة التصادمات (Handling Collisions)

A Collision occurs when $h(K_1) = h(K_2)$. Since the table size $m < n$ (universe), collisions are inevitable. يحدث تصادم (Collision) عندما $h(K_1) = h(K_2)$. بما أن حجم الجدول $m < n$ (الكون)، فإن التصادمات لا مفر منها.

1. Open Hashing 1. Open Hashing (التجزئة المفتوحة)

Separate Chaining Separate Chaining

Keys are stored in Linked Lists attached to the table cells. يتم تخزين المفاتيح في قوائم مرتبطة (Linked Lists) ملحقة بخلايا الجدول.

  • Logic: If collision, append node to the list. المنطق: إذا حدث تصادم، ألحق العقدة بالقائمة.
  • Load Factor ($\alpha$): Can be $> 1$. معامل التحميل ($\alpha$): يمكن أن يكون $> 1$.
  • Search: $1 + \alpha/2$ (average). البحث: $1 + \alpha/2$ (في المتوسط).

2. Closed Hashing 2. Closed Hashing (التجزئة المغلقة)

Open Addressing Open Addressing

Keys are stored inside the table itself. يتم تخزين المفاتيح داخل الجدول نفسه.

  • Linear Probing: If occupied, check $i+1, i+2...$ Linear Probing: إذا كان مشغولاً، تحقق من $i+1, i+2...$
  • Load Factor ($\alpha$): Must be $\le 1$. معامل التحميل ($\alpha$): يجب أن يكون $\le 1$.
  • Clustering: Keys tend to clump together, slowing performance. التكتل (Clustering): تميل المفاتيح للتجمع معاً، مما يبطئ الأداء.

B-Trees B-Trees (أشجار B)

Why B-Trees? لماذا B-Trees؟

Standard BSTs and AVL trees are great in RAM. But when data is too large (Databases, File Systems), it lives on Disk. Disk access is 10,000x slower than RAM. B-Trees minimize disk accesses (height) by expanding the node width. تعتبر BSTs و AVL القياسية ممتازة في الـ RAM. ولكن عندما تكون البيانات ضخمة جداً (قواعد البيانات، أنظمة الملفات)، فإنها توجد على القرص (Disk). الوصول للقرص أبطأ بـ 10,000 مرة من الـ RAM. تقلل B-Trees من عمليات الوصول للقرص (الارتفاع) عن طريق توسيع عرض العقدة.

Properties of a B-Tree of Order $m$ خصائص B-Tree من الدرجة $m$

1. Balance 1. التوازن (Balance)

Perfectly balanced. All leaves are at the same depth. متوازنة تماماً. جميع الأوراق في نفس العمق.

2. Node Capacity 2. سعة العقدة

Every node (except root) has between $\lceil m/2 \rceil$ and $m$ children. كل عقدة (ما عدا الجذر) لها ما بين $\lceil m/2 \rceil$ و $m$ من الأبناء.

3. Keys 3. المفاتيح (Keys)

A node with $k$ children contains $k-1$ keys. العقدة التي بها $k$ من الأبناء تحتوي على $k-1$ من المفاتيح.

4. Growth 4. النمو

Grows upwards. When a node overflows, it splits and pushes a key to the parent. تنمو للأعلى. عندما تفيض العقدة، تنقسم وتدفع مفتاحاً للأب.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: The Naming Confusion فخ: ارتباك التسميات

This is the most common mistake:
Open Hashing = Separate Chaining (Linked Lists outside).
Open Addressing = Closed Hashing (Everything inside).
Memorize this opposition. "Open Addressing" means the address is open to other keys, but it is a "Closed Hashing" system. هذا هو الخطأ الأكثر شيوعاً:
Open Hashing = Separate Chaining (قوائم مرتبطة بالخارج).
Open Addressing = Closed Hashing (كل شيء بالداخل).
احفظ هذا التضاد. "Open Addressing" تعني أن العنوان مفتوح لمفاتيح أخرى، لكنه نظام "Closed Hashing".

TRAP: Hashing Worst Case فخ: أسوأ حالة للـ Hashing

"Is Hashing always $O(1)$?"
NO! That is the average case. In the worst case (all keys collide to the same index), it degrades to $O(n)$ (searching a linked list). Never promise $O(1)$ without saying "average". "هل الـ Hashing دائماً $O(1)$؟"
لا! تلك هي الحالة المتوسطة. في أسوأ حالة (كل المفاتيح تتصادم في نفس الفهرس)، تتدهور إلى $O(n)$ (البحث في قائمة مرتبطة). لا تعد بـ $O(1)$ دون قول "في المتوسط".

SECRET: Why Primes? سر: لماذا الأعداد الأولية؟

Why do we choose table size $m$ to be Prime?
If keys have a pattern (e.g., 10, 20, 30) and $m$ is 10, they all collide at index 0. A Prime number $m$ breaks up arithmetic patterns in the input keys, distributing them more evenly. لماذا نختار حجم الجدول $m$ ليكون أولياً؟
إذا كان للمفاتيح نمط (مثلاً، 10، 20، 30) وكان $m$ هو 10، فستتصادم جميعها في الفهرس 0. الرقم الأولي $m$ يكسر الأنماط الحسابية في مفاتيح الإدخال، ويوزعها بشكل أكثر توازناً.

KEY CONCEPT: B+ Trees مفهوم مفتاحي: أشجار B+

The PDF mentions B+ Trees in the summary. The key difference from B-Trees: in B+ Trees, all data is stored in the leaves. Internal nodes only contain keys for navigation. This allows for faster sequential access (linked leaves). يذكر الـ PDF أشجار B+ Trees في الملخص. الفرق الرئيسي عن B-Trees: في B+ Trees، يتم تخزين كل البيانات في الأوراق. العقد الداخلية تحتوي فقط على مفاتيح للتنقل. هذا يسمح بوصول تسلسلي أسرع (أوراق مرتبطة).