[prev] [index] [next]

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