Separate Chaining (cont)
Cost analysis:
- N array entries (slots), M stored items
- average list length L = M/N
- best case: all lists are same length L
- worst case: h(k)=0, one list of length M
- searching within a list of length n:
- best: 1, worst: n, average: n/2
- if good hash and M≤N, cost is 1
- if good hash and M>N, cost is (M/N)/2
Ratio of items/slots is called load α = M/N
|