Hashing

Q1. (3 marks — 1 each)

• Deterministic: the same key always hashes to the same value (else lookups fail). (1)
• Uniform: distributes keys evenly across buckets to minimise collisions. (1)
• Fast: computable in $O(1)$ / constant time so operations stay efficient. (1)

Q2. (3 marks)

• Definition: $\alpha = \dfrac{n}{m}$. (2)
• Computation: $\alpha = \dfrac{30}{8} = 3.75$. (1)

Q3. (4 marks)

• Chaining: each bucket holds a linked list (or dynamic structure) of colliding entries; the table stores pointers to chains. (1)
• Open addressing: all entries stored directly in the table array; collisions resolved by probing for another slot. (1)
• Advantage of chaining: handles high load factors ($\alpha > 1$) gracefully; simple deletion. (1)
• Advantage of open addressing: better cache locality, no pointer/linked-list overhead. (1)

Q4. (6 marks) $h(k)=k\bmod 7$:

• $50 \bmod 7 = 1$ → slot 1
• $700 \bmod 7 = 0$ → slot 0
• $76 \bmod 7 = 6$ → slot 6
• $85 \bmod 7 = 1$ → occupied, probe 2 → slot 2
• $92 \bmod 7 = 1$ → occupied 1,2 probe 3 → slot 3
• $73 \bmod 7 = 3$ → occupied, probe 4 → slot 4

Final table (1 mark per correct slot placement, 6 total):

Q5. (5 marks)

• If we simply empty the slot, a later search that probed through that slot to reach a key beyond it would now terminate early (hit an empty slot) and wrongly report "not found". (2)
• Tombstone: mark the slot with a special DELETED marker rather than empty. (1)
• Search: treats a tombstone as "occupied, keep probing" — does not stop. (1)
• Insert: may reuse a tombstone slot (treats it as available). Note: many tombstones degrade performance → periodic rehashing clears them. (1)

Q6. (4 marks)

• $h_1(25) = 25 \bmod 11 = 3$. (1)
• $h_2(25) = 1 + (25 \bmod 10) = 1 + 5 = 6$. (1)
• Probe sequence: $(h_1 + i\cdot h_2)\bmod 11$:
  • $i=0$: $3$
  • $i=1$: $(3+6)\bmod 11 = 9$
  • $i=2$: $(3+12)\bmod 11 = 15\bmod 11 = 4$ (2 for correct first three: 3, 9, 4)

Q7. (4 marks)

• Amortized $O(1)$: the average cost per operation over a sequence of operations is constant, even if individual operations are occasionally expensive. (2)
• With doubling, resizing $n$ elements costs $O(n)$ but happens after $\sim n$ cheap inserts; the total cost of $n$ inserts is $O(n)$ (geometric series $1+2+4+\dots+n = O(n)$), so cost per insert $= O(1)$ amortized. (2)

Q8. (4 marks)

• Universal family: $H$ is universal if for any two distinct keys $x \neq y$, $\Pr_{h \in H}[h(x) = h(y)] \le \frac{1}{m}$ where $m$ is the table size and $h$ is chosen uniformly at random from $H$. (3)
• Guarantee: the probability that two distinct keys collide is at most $1/m$, independent of the input, giving expected $O(1)$ operations regardless of adversarial keys. (1)

Q9. (4 marks)

• Maintain a hash map from value → index. Iterate through the array; for each $a[i]$, check whether $T - a[i]$ is already in the map. (2)
• If found, return the stored index and $i$; otherwise insert $a[i]:i$ and continue. (1)
• Time complexity: $O(n)$ (each lookup/insert is expected $O(1)$). (1)

Q10. (3 marks)

• (i) CPython's dict uses open addressing (a perturbation-based probe sequence), not chaining. (2)
• (ii) A key must be hashable — implement __hash__ and be immutable/equality-consistent (equal keys must have equal hashes). (1)

[
  {"claim":"Load factor n=30, m=8 gives 3.75","code":"result = (Rational(30,8) == Rational(15,4)) and (float(Rational(30,8))==3.75)"},
  {"claim":"Linear probing final positions for keys 50,700,76,85,92,73 in m=7","code":"m=7\ntable=[None]*m\nfor k in [50,700,76,85,92,73]:\n    i=k%m\n    while table[i] is not None:\n        i=(i+1)%m\n    table[i]=k\nresult = table==[700,50,85,92,73,None,76]"},
  {"claim":"Double hashing probe sequence for k=25, m=11 is 3,9,4","code":"m=11\nk=25\nh1=k%m\nh2=1+(k%10)\nseq=[(h1+i*h2)%m for i in range(3)]\nresult = seq==[3,9,4]"},
  {"claim":"Geometric doubling sum 1+2+...+n is O(n): total < 2n","code":"n=1024\ntotal=0\ns=1\nwhile s<=n:\n    total+=s\n    s*=2\nresult = total < 2*n*2 and total==2047"}
]