*cough* I can remember sitting at a client (rather late at night) under intense pressure looking at the performance curve that when straight up, because well some dictionary when over N elements and the hash target then resolved to a *very* long chain on an insert.
Sadly mmm 12 years later we not been able to provide a decent hash logic for Smalltalk (aka Pharo) that removes the hassle of having to consider some specialized form of dictionary if the experienced programmer in the room twigs to the fact why that could be the problem... On 2009-10-21, at 7:54 PM, Martin McClure wrote: > 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 > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project -- = = = ======================================================================== John M. McIntosh <[email protected]> Twitter: squeaker68882 Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com = = = ======================================================================== _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
