CPSC 2120 - DAY 12
MAY 31, 2016

================================================================================

Hashing Continued...

The size of a hash table should be a prime number.  You will encounter 
collisions more often than if you choose a prime.

     0   1   2   3   4   5   6   7   8   9  10   11  12  13  14
     _   _  47   _   _  35  36   _   _ 129  25 2501   _   _   _


Seperate Chaining - Let each array element be the head of a chain.

We insert it at head

Linear Probing

If the hash table is not full, attempt to store key in array elements
(t+1)%N, (t+2)%N, (t+3)%N

Linear Probing leads to the problem of clustering.  Elements tend to cluster
in dense intervals in the array

As clusters get longer, higher probability of making cluster even longer

(t+1^2)%N, (t+2^2)%N, (t+3^2)%N


Double Hashing

requires two hash functions

Typical second hash function

f(x) = R - (x%R)
where R is a prime number, R < N

Rehash when load factor between 0.5 to 0.7

Approximately double the size of hash table, N = nearest prime
redefine hash functions
rehash keys into a new table

PRIORITY QUEUES
---------------