2009/10/22 Martin McClure <martin@hand2mouse.com>:
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.