## Perfect Hash[Back] A perfect hash creates a mathematical function which avoids collisions: |

## Outline

Let's say I have a number of values:

(0, 3, 6, 7 ,11, 14, 18, 19, 20, 25, 27, 28, 30, 35, 40, 44,55)

and I want to create a minimum size hash value for these value - with no collisions - with the fastest method I can use. How do I do that?

Well, we have 17 values, so we want to create a value from 0 to 16, and have no repeating value. The mathematical function I will use is:

def hashme(i,r,t): x = i % t y = int (math.floor(i/t)) return (x + r[y])

and where we will create a value for t and for an array of r. The code I'll use is:

import perfection import math l = (0, 3, 6, 7 ,11, 14, 18, 19, 20, 25, 27, 28, 30, 35, 40, 44,55) def hashme(i,r,t): x = i % t y = i//t return (x + r[y]) params = perfection.hash_parameters(l) print 'Params (r)',params.r print 'Params (t)',params.t print count = 0 print 'Value\tHash' for ll in l: print l[count],'\t',hashme(ll,params.r,params.t) count=count+1

and the result becomes:

C:\> python perfect_hash.py Params (r) (0, -2, 12, 7, -1, 5, 5, None) Params (t) 8 Value Hash 0 0 3 3 6 6 7 7 11 1 14 4 18 14 19 15 20 16 25 8 27 10 28 11 30 13 35 2 40 5 44 9 55 12

So we now have a little hash function, which takes the values of t and r, and then we can take our input values and find a hash value the relates to it, and without collisions. With this type of method, we can create optimized hash tables for values, and where we perform a fast lookup.