Igor et al,
Let me simplify the goal of perfect hashing: - suppose you having N unique integer numbers, without strictly specified range (any number could lie in range 0..infinity). - now we need to find a function such that, for each element 'x' in the above finite set, following conditions met:
0 <= f(x) < k*N
and for each pair of two different elements x , y in original set f(x) <> f(y)
and k < infinity
As you can see , this function maps an arbitrary integer values without specific range, to an integer values in range [0..k*N], (k>=1). Given that we need to deal with a limited number of elemens for each particular set of numbers, such function can be found. We just need to search for an optimal (minimal) k, which is < 2 and in perfect case == 1.
I thought I'd point out a subtle potential problem. Assume N = 1000, f(x_j) = j-1, and so k = 1 because 0 <= f(x_j) < N because 0 < j <= 1000. Now, store x_{7i} in a Set, for all i such that 1 <= 7i <= 1000. Clearly, f(x) is a perfect hash function as defined above. However, if the size of the table used by the set is a multiple of 7, performance will be terrible. By the way, you may want to check out the Hash Analysis Tool I wrote for VisualWorks. It's in the public Store repository (bundle name "Hash Analysis Tool", there's also an extensions bundle with more hash functions and data sets). My blog has a (somewhat passable excuse for a) manual here: http://blogten.blogspot.com/2008/02/hash-analysis-tool-manual.html. Andres.