[prev] [index] [next]

Hashing (cont)

Consider a hash table with N slots ...

When using chaining

  • can store > N items in table
  • h(x) == h(y) means add x and y into same list
When using a fixed-size array
  • can store ≤ N items in table   (typically ≤ 2N/3)
  • h(x) == h(y) handled by probing (table scan)