[prev] [index] [next]

Hashing (cont)

To use arbitrary values as keys, we need three things:
  • set of Key values,   each key identifies one Item
  • an array (of size N) to store Items
  • a hash function h() of type Key→[0..N-1]
    • requirement: if (x == y) then h(x) == h(y)
    • requirement: h(x) always returns same value for given x
  • a collision resolution method
    • collision = (x != y && h(x) == h(y))
    • collisions are inevitable when dom(Key) >> N