Linear probing

Linear probing is the hashing strategy. Insert an element x, compute h(x) and try to place x. All hash table address the collisions.

All elements with hash collisions are stored. Choose hash functions to avoid collisions, and rehash or move elements when they do. When removing an element, mark that the cell is empty.

Memory in your devices is not exhausted because of the hash function.

K-independent hashing is randomized algorithms for this efficiency.

H={h:U→［ｍ］}

Hashing maps keys from some large domain (universe) U into a smaller range m.

［m］={0,1,2・・・,m-1}

X1,X2・・,Xk ∊ U^k

k is distinct keys.

Y1,Y2・・,Yk ∊ ［m］^k

The expected cost of a lookup in chained hashing with 2-independent hash functions is O(1 + α) because of collisions. O(1) is the ideal.