Perfect HashA 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.