Hashing

Question 1 [12]

(a) [9] — 3 for structure/hash+resize trigger, 3 for put/get, 3 for delete + rehash correctness.

class HashMap:
    def __init__(self, cap=8):
        self.cap = cap
        self.size = 0
        self.buckets = [[] for _ in range(cap)]
 
    def _idx(self, key):
        return hash(key) % self.cap        # deterministic, fast
 
    def put(self, key, value):
        b = self.buckets[self._idx(key)]
        for i, (k, v) in enumerate(b):
            if k == key:
                b[i] = (key, value)         # update existing
                return
        b.append((key, value))
        self.size += 1
        if self.size / self.cap > 0.75:     # load factor check
            self._resize()
 
    def get(self, key):
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        raise KeyError(key)
 
    def delete(self, key):
        b = self.buckets[self._idx(key)]
        for i, (k, v) in enumerate(b):
            if k == key:
                b.pop(i)
                self.size -= 1
                return
        raise KeyError(key)
 
    def _resize(self):
        old = self.buckets
        self.cap *= 2
        self.buckets = [[] for _ in range(self.cap)]
        self.size = 0
        for b in old:
            for k, v in b:
                self.put(k, v)              # rehash into larger table

(b) [3]

• Load factor $\alpha = n/m$ (entries / buckets). [1]
• With chaining, expected chain length is $\alpha$; keeping $\alpha \le 0.75$ keeps chains short so each op is $O(1+\alpha)=O(1)$ expected. [1]
• Resizing is $O(n)$ but happens rarely (only after $n$ doublings), so its cost amortizes to $O(1)$ per insert. [1]

Question 2 [11]

(a) [4] $h(k)=k\bmod 7$:

• $10\bmod7=3$ → slot 3
• $17\bmod7=3$ → occupied, probe 4 → slot 4
• $24\bmod7=3$ → 3,4 occupied, probe 5 → slot 5
• $3\bmod7=3$ → 3,4,5 occupied, probe 6 → slot 6

(1 mark per correctly placed key.)

(b) [3] Blanking slot 4 would break the probe chain: a later search for 24 (which probed 3→4→5) would hit the empty slot 4 and stop early, wrongly concluding 24 is absent. [2] Instead mark slot 4 as a tombstone (DELETED): [1]

(c) [4] search(24): $h(24)=3$.

• Probe 3: key 10 ≠ 24, continue. [1]
• Probe 4: tombstone → do not stop, keep probing (a tombstone means "was occupied, may have kept a later key on the chain"). [1+1]
• Probe 5: key 24 → found. [1]

Question 3 [9]

(a) [4] Probe sequence for slot $i=0,1,2,\dots$:

• Linear: $h(k,i) = (h(k)+i)\bmod m$. [1]
• Quadratic: $h(k,i) = (h(k)+c_1 i + c_2 i^2)\bmod m$. [1.5]
• Double hashing: $h(k,i) = (h_1(k)+i\cdot h_2(k))\bmod m$. [1.5]

(b) [2] Primary clustering: contiguous runs of occupied slots grow and merge, so long runs get longer, degrading probes. Linear probing suffers from it. [2]

(c) [3] $h_1(27)=27\bmod13=1$; $h_2(27)=1+(27\bmod11)=1+5=6$.

• $i=0$: $1$
• $i=1$: $(1+6)\bmod13=7$
• $i=2$: $(1+12)\bmod13=0$

Probe indices: 1, 7, 0. [1 each]

Question 4 [10]

(a) [5] Doubling from capacity 1: rehashes occur at sizes $1,2,4,\dots,2^k \le n$. Cost of rehash at size $2^j$ is $\Theta(2^j)$. Total: $\sum_{j=0}^{\log_2 n} 2^j = 2^{\log_2 n +1}-1 = 2n-1 = O(n).$ [3] Dividing by $n$ inserts gives amortized $O(1)$ per insert. [2]

(b) [4]

• (i) Chaining: expected probes $= \alpha$ (must scan the whole chain). [2]
• (ii) Open addressing (uniform): $\dfrac{1}{1-\alpha}$. [2]

(c) [1] As $\alpha\to1$ in open addressing, $\frac{1}{1-\alpha}$ blows up (probes explode / table fills); keeping $\alpha$ low keeps probes bounded. [1]

Question 5 [8]

(a) [3] $\mathcal H$ is universal if for all distinct $x\neq y \in U$: $\Pr_{h\in\mathcal H}[h(x)=h(y)] \le \frac{1}{m}.$

(b) [3] Collision probability $\le 1/m$ regardless of which keys the adversary picks, because $h$ is chosen randomly after the keys are fixed. [2] So expected chain length / probe count stays $O(1+\alpha)$ in expectation over the choice of $h$ — no fixed input can force worst-case behaviour. [1]

(c) [2] Expected colliders with fixed $x$ among the other $n-1$ keys: $\sum_{y\neq x}\Pr[h(y)=h(x)] \le \frac{n-1}{m} = O(\alpha).$

Question 6 [10]

(a) [5]

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

(2 for single-pass structure, 2 for complement lookup, 1 for correct return.)

(b) [2] Time $O(n)$: one pass, each dict op $O(1)$ average. Space $O(n)$: up to $n$ entries stored. [2]

(c) [3] CPython's dict is an open-addressing hash table. The key's hash selects a slot; [1] on a collision it uses a perturbation-based probe sequence to find the next slot; [1] since $\alpha$ is kept below ~2/3 (it resizes/rehashes otherwise), probe chains stay short, giving average $O(1)$ lookup. [1]

[
  {"claim":"Q2a: linear probing places 10,17,24,3 at slots 3,4,5,6",
   "code":"m=7; slots=[None]*m\nfor k in [10,17,24,3]:\n    i=k%m\n    while slots[i] is not None: i=(i+1)%m\n    slots[i]=k\nresult = slots==[None,None,None,10,17,24,3]"},
  {"claim":"Q3c: double hashing probes for k=27 are 1,7,0",
   "code":"m=13; h1=27%13; h2=1+(27%11)\nprobes=[(h1+i*h2)%m for i in range(3)]\nresult = probes==[1,7,0]"},
  {"claim":"Q4a: geometric doubling total cost is 2n-1 for n a power of 2 (n=8)",
   "code":"n=8; total=sum(2**j for j in range(0, n.bit_length()))\nresult = total==2*n-1"},
  {"claim":"Q4b: open-addressing unsuccessful search probes 1/(1-alpha) at alpha=0.75 equals 4",
   "code":"from sympy import Rational\nalpha=Rational(3,4)\nresult = (1/(1-alpha))==4"}
]