The table starts as a standard table look-up and then gets divided into two table look-up tables with each of half the length. Then 4, 8, 16, 32, 64. By now the tables start to merge together and the cluster of entries get larger so that the gains of dividing by 2 are not as great but still much better than the standard table look-up.

The graph show the average length of search after each entry and the number gives the maximum length of any search so far.

E F Max Length = 1 Divide entries into 1 table(s) E F Max Length = 1 Divide entries into 2 table(s) E F Max Length = 1 Divide entries into 4 table(s) E F Max Length = 1 Divide entries into 8 table(s) E F Max Length = 1 Divide entries into 16 table(s) E F Max Length = 1 Divide entries into 32 table(s) E F Max Length = 1 ? Divide entries into 64 table(s) Table Look-up (1)i=0 (2)If entry i empty or contains KEY exit (3)Otherwise i = i + 1, goto (2) Sound Design by Paul Hopgood Hash Derivation Hash Derivation