Igor Stasenko wrote: > 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. >
Ah, thanks. That does indeed make more sense than what I originally thought you meant, sorry for the confusion. Pluggable hashes could be useful, though I've been quite happy with using subclasses for that, which keeps the code of the general collection class cleaner. However, this approach does mean that for perfect hash (not just pluggable hash function) you have to find an actual function that is fast and compact that is a perfect hash, or you've lost the slight advantage that perfect hashes have over good but imperfect hashes. And I doubt this can be done for something like a MethodDictionary. Also, you'd have to add code to control the size of the hash table to be the right size for the perfect hash function. Regards, -Martin _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
