2009/10/22 Martin McClure <[email protected]>: > 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? > Limited, why?
As i said, suppose you have a collection which is modified rarely. As an example: MethodDictionary, Smalltalk as well as any collections which you using in your code as an immutable storage, once populated. This can be done easily with few modifications to current classes. Consider: Set>>scanFor: anObject - start := (anObject hash \\ finish) + 1. + start := hashFunction ifNil: [ (anObject hash \\ finish) + 1 ] ifNotNil: [ hashFunction value: anObject hash on: array ]. now you can tell set to use custom hash function, by using a new method: Set>>rehashUsing: newHashFunction hashFunction := newHashFunction. hashFunction ifNil: [ self rehashUsingOldWay ] ifNotNil: [ array := hashFunction rehash: array filler: nil ]. oh, and btw, such modifications don't assume what hash function will be used , so you can forget about perfect hashing, if you don't like it :) Mainly, what it does, just replacing a hardcoded hash function , which is '(anObject hash \\ finish) + 1' by one, provided by you. -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
