2009/10/22 Andres Valloud <[email protected]>: > 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. >
err.. i'm not sure i understood, if you having 1000 objects, which answering an unique hash values, which can be represented by: element hash == 7i and as you stating that 1 <= 7i <= 1000 , then there can't be 1000 unique hash values in this range for 1000 objects. Obviously you can have only 1000/7 unique hash values meeting such criteria. But if you read carefully, i'm not adressing the problem of duplicating hash values in input set, and presuming they are all unique. I'm not addressing the quality of hash function for object(s), i'm just illustrating a hash function which could be employed by set(s), which could work perfectly, once all objects having unique hash values. Surely, despite how good the hash function used by set, if hashes of its elements clashing, you will have a performance degradation. > 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 > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
