Igor Stasenko wrote:
Err, your thoughts went in wrong direction. 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.
Hi Igor, Yes, you have defined a perfect hash function nicely, and that is the definition I was assuming in my previous comments. And even if you find a perfect hash function for a given set of objects, the situations in which the resulting collection is useful are quite limited, which was the main idea behind my comments. Unless I've missed something? Regards, -Martin