CITS2200 - Lecture 11

← Back to Home

CITS2200 - Lecture 10
Hash Tables - Slides
Recap: CITS2200 - Lecture 9

Issue with Lists

• Lists can be used to implement various data structures
  • e.g. maps and sets
• However, they take $O(n)$ to search:
  • The item you search for may or may not exist
  • Thus, we must check every entry in the list
  • Worst case → $n$ time to find object
• Sorting a list may make searching more efficient, but:
  • Inserting an object takes $O(n)$ time
  • Which makes things equally as inefficient

Hash Functions and Hash Tables

• Hash function h maps keys to integers in a fixed range [0, N-1], where N is the size of the table (array)
  • Goal: store item (k, v) at index h(k) in the array
  • Example: h(x) = x mod N for integer keys
• Hash table for a given key type consists of:
  • Hash function h
  • Array (called table) of size N

Hash function is typically composed of two steps:

1. Hash code $h_1$: keys → integers
2. Compression function $h_2$: integers → [0, N-1]

Goal of hash function → “disperse” keys in an apparently random way

Compression Functions

Two common approaches:

• Division: $h_2(y)=$ y mod N
  • N → size of hash table, usually prime
• MAD (Multiply, Add and Divide): $h_2(y)=$ (ay + b) mod N
  • a and b are non-negative integers
  • a mod N $\ne 0$
    • Otherwise, everything would map to the same value b

Collisions Handling

mod ensures for any input, output is between 0 and N-1

• x mod y is equal to the remainder of $\frac{x}{y}$

Using mod, or even other functions, it becomes inevitable that some values would give the same output

• These are known as collisions

Collisions can be handled in several ways:

Separate Chaining

• Each cell in table points to a linked list of all entries that map there
• If a collision occurs, the new item is just appended to that cell’s list

Index 1 → [025-612-0001]
Index 4 → [451-229-0004] → [981-101-0004]

Operations just delegate to the list at A[h(k)]:

• get(k): return A[h(k)].get(k)
• put(k,v): call A[h(k)].put(k,v), increment count if new key
• remove(k): call A[h(k)].remove(k), decrement count if found

Downside: Requires extra memory outside the table for the linked lists

Open Addressing (Linear Probing)

• No chaining, keep everything inside table
• On collision, find next available cell

Each position checked = a probe

• Colliding items lump together, causing future collisions to cause a longer sequence of probes known as primary clustering

Searching with Linear Probing (get(k))

• Start at h(k), probe consecutively until:
  • Item with key k is found → return it
  • Empty cell found → key not in table
  • All N cells probed → key not in table

Deleting items from Table:

• We cannot just delete an item from the table
  • Would break the probe chain for future searches
  • Instead, replace deleted items with a special AVAILABLE object
• remove(k): find k, replace with AVAILABLE, return value
• put(k,v): treat AVAILABLE cells as valid insertion spots

Double Hashing

• Use secondary hash function d(k) to determine step size:
  • Probe sequence: (h(k) + j·d(k)) mod N for j = 0, 1, 2, ...
    • N must be prime to allow probing of all cells
  • Common secondary function: d(k) = q - (k mod q)
    • q < N and q is prime
    • d(k) must never be zero (infinite loop)
• @ Spreads items more evenly than linear probing since the step size varies per key

Performance of Hashing

Scenario	Complexity
Worst case (all keys collide)	$O(n)$
Expected case (good hash fn)	$O(1)$

The load factor α = n/N affects performance of a hash table

• Expected probes for open addressing = 1 / (1 - α)
• α is usually well below 100%
  • Hashing is very fast in practice

---

CITS2200 - Lecture 12