Data Structures & Algorithms

  Traditional Search:
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
  │ 5 │ 8 │ 2 │ 9 │ 1 │ 7 │ 3 │ 6 │  → Search for 7: check each → O(n)
  └───┴───┴───┴───┴───┴───┴───┴───┘

  Hashing:
  Key 7 → h(7) = 7 mod 10 = 7 → Go directly to index 7 → O(1)!

  Hash Function:  h(k) → index

  Key k ──→ [ Hash Function h(k) ] ──→ Index in array
                                          ↓
                                    ┌───┬───┬───┬───┬───┬───┬───┐
                                    │   │   │   │ k │   │   │   │
                                    └───┴───┴───┴───┴───┴───┴───┘
                                     0   1   2   3   4   5   6

  Access time ≈ O(1) average case

  h(25) = 25 mod 10 = 5
  h(35) = 35 mod 10 = 5   ← SAME INDEX!

  Two keys → same slot = COLLISION

  Index:  0   1   2   3   4   5   6   7   8   9
        [   |   |   |   |   | ? |   |   |   |   ]
                                  ↑
                         Both 25 and 35 want this slot!

  Hash Table with Chaining (m = 7):

  Insert keys: 50, 700, 76, 85, 92, 73, 101

  h(k) = k mod 7

  h(50)  = 50 mod 7  = 1
  h(700) = 700 mod 7 = 0
  h(76)  = 76 mod 7  = 6
  h(85)  = 85 mod 7  = 1   ← collision with 50!
  h(92)  = 92 mod 7  = 1   ← collision with 50, 85!
  h(73)  = 73 mod 7  = 3
  h(101) = 101 mod 7 = 3   ← collision with 73!

  Result:
  ┌───┐
  │ 0 │ → [700] → NULL
  ├───┤
  │ 1 │ → [50] → [85] → [92] → NULL    ← chain of 3!
  ├───┤
  │ 2 │ → NULL
  ├───┤
  │ 3 │ → [73] → [101] → NULL
  ├───┤
  │ 4 │ → NULL
  ├───┤
  │ 5 │ → NULL
  ├───┤
  │ 6 │ → [76] → NULL
  └───┘

  Load Factor:  α = n / m

  Where:
    n = number of keys stored
    m = number of slots (table size)

  Example above: α = 7 / 7 = 1.0

  Average search time in chaining: O(1 + α)

  If α is small → fast (short chains)
  If α is large → slow (long chains)

# Chaining Implementation
class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]   # Array of empty lists

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash(key)
        self.table[index].append(key)            # Append to chain

    def search(self, key):
        index = self.hash(key)
        return key in self.table[index]          # Search in chain

    def delete(self, key):
        index = self.hash(key)
        if key in self.table[index]:
            self.table[index].remove(key)

# Usage
ht = HashTableChaining(7)
for k in [50, 700, 76, 85, 92, 73, 101]:
    ht.insert(k)

print(ht.search(85))   # True
print(ht.search(99))   # False

  Key Rule: Load factor α CANNOT exceed 1

  Because every element must fit inside the array itself.
  No external storage allowed!

  If table has m slots → can store at most m elements.

  h(k, i) = (h'(k) + i) mod m

  Where:
    h'(k) = initial hash value (e.g., k mod m)
    i     = probe number (0, 1, 2, 3, ...)
    m     = table size

  Example: m = 10, h(k) = k mod 10
  Insert: 25, 35, 45, 15

  Insert 25: h(25) = 5         → slot 5 ✓
  Insert 35: h(35) = 5 (taken!)
             try i=1: (5+1) mod 10 = 6 → slot 6 ✓
  Insert 45: h(45) = 5 (taken!)
             try i=1: 6 (taken!)
             try i=2: (5+2) mod 10 = 7 → slot 7 ✓
  Insert 15: h(15) = 5 (taken!)
             try i=1: 6 (taken!)
             try i=2: 7 (taken!)
             try i=3: (5+3) mod 10 = 8 → slot 8 ✓

  Table:
  Index: 0   1   2   3   4   5   6   7   8   9
       [   |   |   |   |   |25 |35 |45 |15 |   ]
                               ↑───────────↑
                               PRIMARY CLUSTER!

  Cluster:  [__|__|__|__|25|35|45|15|__|__]
                         ↑──────────↑
                         Once a cluster forms,
                         NEW keys that hash to
                         ANY slot in this range
                         must probe through the
                         ENTIRE cluster!

  Cluster grows → more collisions → cluster grows more!
  This is PRIMARY CLUSTERING.

  h(k, i) = (h'(k) + c₁·i + c₂·i²) mod m

  Common simplified form (c₁ = 0, c₂ = 1):
  h(k, i) = (h'(k) + i²) mod m

  Probe sequence: +0, +1, +4, +9, +16, +25, ...

  Example: m = 10, h(k) = k mod 10
  Insert: 25, 35, 45

  Insert 25: h(25,0) = 5         → slot 5 ✓
  Insert 35: h(35,0) = 5 (taken!)
             h(35,1) = (5 + 1²) mod 10 = 6 → slot 6 ✓
  Insert 45: h(45,0) = 5 (taken!)
             h(45,1) = (5 + 1²) = 6 (taken!)
             h(45,2) = (5 + 2²) mod 10 = 9 → slot 9 ✓  ← JUMPED!

  Table:
  Index: 0   1   2   3   4   5   6   7   8   9
       [   |   |   |   |   |25 |35 |   |   |45 ]
                                               ↑
                                  Quadratic jump avoids clustering!

  Compare with linear: 25 at 5, 35 at 6, 45 at 7 (cluster!)
  Quadratic:           25 at 5, 35 at 6, 45 at 9 (spread out!)

  h(k, i) = (h₁(k) + i · h₂(k)) mod m

  Where:
    h₁(k) = primary hash function (e.g., k mod m)
    h₂(k) = secondary hash function (e.g., 1 + (k mod (m-1)))

  The step size VARIES based on the key!
  Different keys that collide will probe DIFFERENTLY.

  Example: m = 7
  h₁(k) = k mod 7
  h₂(k) = 1 + (k mod 5)

  Insert 10: h₁(10) = 3                         → slot 3 ✓
  Insert 17: h₁(17) = 3 (taken!)
             h₂(17) = 1 + (17 mod 5) = 1 + 2 = 3
             i=1: (3 + 1×3) mod 7 = 6           → slot 6 ✓
  Insert 24: h₁(24) = 3 (taken!)
             h₂(24) = 1 + (24 mod 5) = 1 + 4 = 5
             i=1: (3 + 1×5) mod 7 = 1           → slot 1 ✓

  Table:
  Index: 0   1   2   3   4   5   6
       [   |24 |   |10 |   |   |17 ]

  Notice: 10, 17, 24 all hash to 3 but end up at 3, 6, 1
  Each uses a DIFFERENT step size! Much better distribution.

# Double Hashing Implementation
class HashTableDoubleHashing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def h1(self, key):
        return key % self.size

    def h2(self, key):
        return 1 + (key % (self.size - 1))

    def insert(self, key):
        index = self.h1(key)
        if self.table[index] is None:
            self.table[index] = key
            return

        # Collision! Use double hashing
        step = self.h2(key)
        for i in range(1, self.size):
            new_index = (index + i * step) % self.size
            if self.table[new_index] is None:
                self.table[new_index] = key
                return

        print("Table is full!")

    def search(self, key):
        index = self.h1(key)
        step = self.h2(key)
        for i in range(self.size):
            probe = (index + i * step) % self.size
            if self.table[probe] is None:
                return False
            if self.table[probe] == key:
                return True
        return False

# Usage
ht = HashTableDoubleHashing(7)
for k in [10, 17, 24]:
    ht.insert(k)

print(ht.search(17))  # True
print(ht.search(5))   # False

  Open Addressing average probes:

  Unsuccessful search: ≈ 1 / (1 − α)
  Successful search:   ≈ (1/α) × ln(1 / (1 − α))

  Example with α = 0.5 (half full):
    Unsuccessful: 1 / (1 - 0.5) = 2 probes
    Successful:   (1/0.5) × ln(2) ≈ 1.39 probes

  Example with α = 0.9 (90% full):
    Unsuccessful: 1 / (1 - 0.9) = 10 probes!
    Successful:   ≈ 2.56 probes

  Lesson: Keep α low. α > 0.7 → performance degrades rapidly.

  Load Factor:        α = n / m

  Linear Probing:     h(k, i) = (h'(k) + i) mod m
  Quadratic Probing:  h(k, i) = (h'(k) + c₁·i + c₂·i²) mod m
  Double Hashing:     h(k, i) = (h₁(k) + i·h₂(k)) mod m

  Chaining avg search:   O(1 + α)
  Open Addr avg search:  O(1 / (1 − α))