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)
|