Key: A value in large universe U

Hash Table: Array T of size m, each position is a “bucket”

Hash Function: $h:U\to\{0,1,\dots,m-1\}$

• h(k) is “home bucket”

Hash vs AVL: Hash table cannot process items in order.

Hash Map (Dictionary)

Operations:

• SEARCH: $O(1)$ Access index in T[h(k)]
• INSERT: $O(1)$ Set T[h(k)] = x
• DELETE: $O(1)$ Set T[h(k)] = null

Anti-Collision Models

Collisions: When $k_1\ne k_2$ but $h(k_1)=h(k_2)$. Unavoidable when $m<|U|$

Direct-Access Table: For small universe, set $m=\text{len(T)}=|U|$ (Each key has an unique index)

• SEARCH, INSERT, DELETE: Worst case O(1)
• Issue: Use a lot of memory if U is large

Closed Addressing

Closed Addressing: Store a linked list in each bucket Key k is always in T[h(k)]

• SEARCH, INSERT, DELETE: Worst case O(n), Avg case O(n/m)

Average Case Analysis of Closed Addressing

Assumption: Hash function produces $i\in [0, m-1]$ with equal probability (spread out)