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.
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
