```
🔷 DOUBLE HASHING VISUALIZER
Hashing • Collision Resolution • Two Hash Functions • Step-by-Step Animation
```
```
📥 Hash Table Configuration
```
```
```
🗂️ Hash Table
🔵 Current Probe
🟡 Collision
🟢 Found / Inserted
🔴 Deleted
```
📈 Live Statistics
Operation
-
h₁(k)
-
h₂(k)
-
Current Index
-
Collisions
0
Probes
0
Enter a value and select an operation.
```
```
```
📝 Step-by-Step Explanation
1
Double Hashing uses two hash functions.
The first function gives the starting position and
the second function determines the jump size after
a collision.
```
🧮 Double Hashing Formula
First Hash Function:
h₁(k) = k mod m
Second Hash Function:
h₂(k) = R − (k mod R)
Final Probe Formula:
h(k,i) = (h₁(k) + i × h₂(k)) mod m
where:
k = key m = table size R = smaller prime number
i = probe number
```
h₁(k) = k mod m
Second Hash Function:
h₂(k) = R − (k mod R)
Final Probe Formula:
h(k,i) = (h₁(k) + i × h₂(k)) mod m
where:
k = key m = table size R = smaller prime number
i = probe number
```
🔢 Complete Mathematical Example
Table Size:
m = 11
Choose: R = 7
Key: 27
First Hash:
h₁(27) = 27 mod 11 = 5
Second Hash:
h₂(27) = 7 − (27 mod 7)
= 7 − 6 = 1
Probe 0:
(5 + 0 × 1) mod 11 = 5
Suppose Index 5 is occupied.
⚠️ Collision!
Probe 1:
(5 + 1 × 1) mod 11 = 6
If Index 6 is occupied:
Probe 2:
(5 + 2 × 1) mod 11 = 7
Therefore:
Probe Sequence: 5 → 6 → 7 → ...
```
Choose: R = 7
Key: 27
First Hash:
h₁(27) = 27 mod 11 = 5
Second Hash:
h₂(27) = 7 − (27 mod 7)
= 7 − 6 = 1
Probe 0:
(5 + 0 × 1) mod 11 = 5
Suppose Index 5 is occupied.
⚠️ Collision!
Probe 1:
(5 + 1 × 1) mod 11 = 6
If Index 6 is occupied:
Probe 2:
(5 + 2 × 1) mod 11 = 7
Therefore:
Probe Sequence: 5 → 6 → 7 → ...
```
```
💡 How Double Hashing Works
1
Calculate the first hash function
h₁(k).
2
Check the position returned by the first hash.
3
If the position is occupied, a
collision occurs.
4
Calculate the second hash function
h₂(k).
5
Use the second hash value as the
jump size.
6
Continue using
(h₁(k) + i × h₂(k)) mod m
until an appropriate position is found.
```
⚔️ Comparison with Other Probing Methods
Linear Probing
h(k,i) = (h(k) + i) mod m
Example: 5 → 6 → 7 → 8
Quadratic Probing
h(k,i) = (h(k) + i²) mod m
Example: 5 → 6 → 9 → 4
Double Hashing
h(k,i) = (h₁(k) + i × h₂(k)) mod m
Example: 5 → 8 → 0 → 3
Double hashing generally provides a more varied probe sequence and helps reduce clustering.
```
h(k,i) = (h(k) + i) mod m
Example: 5 → 6 → 7 → 8
Quadratic Probing
h(k,i) = (h(k) + i²) mod m
Example: 5 → 6 → 9 → 4
Double Hashing
h(k,i) = (h₁(k) + i × h₂(k)) mod m
Example: 5 → 8 → 0 → 3
Double hashing generally provides a more varied probe sequence and helps reduce clustering.
```
```
⚖️ Advantages & Disadvantages
+
Advantages
• Uses two hash functions.
• Provides a more distributed probe sequence.
• Reduces primary clustering.
• Usually performs better than simple linear probing when the hash functions and table size are chosen well.
• Uses two hash functions.
• Provides a more distributed probe sequence.
• Reduces primary clustering.
• Usually performs better than simple linear probing when the hash functions and table size are chosen well.
−
Disadvantages
• More complex than linear probing.
• Requires two suitable hash functions.
• The second hash function must not produce a zero step.
• Table size and hash-function choices affect performance.
• More complex than linear probing.
• Requires two suitable hash functions.
• The second hash function must not produce a zero step.
• Table size and hash-function choices affect performance.
```
```
⏱️ Complexity
Average Search
O(1)
Average Insert
O(1)
Worst Case
O(n)
No comments:
Post a Comment