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
Item s
- 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
|