Incongruent hash
Christopher Oliver
oliver at fritz.co.traverse.com
Mon Feb 9 19:40:31 UTC 1998
> Most hash algorithms are way too simple. Take, for example, the hash for
> strings in Squeak:
[Snip]
> So, basically it looks at most at two characters. This makes for quick
> hashes, but poor hashing.
> I think this whole problem needs a fresh look. Anyone have any thoughts on
> how to have reasonably fast yet reasonably good hashes? Should 'the rule'
> be changed? How?
If one's willing to put the hash into the VM as primitive in C, could
PJW hash (dragon book p. 436) with the upper two bits folded in be used
for strings?
Finite objects are somewhat nastier.
It's story time with IEEE 754:
| i j |
i _ 2.0.
10 timesRepeat: [ i _ i * i ].
j _ 2 raisedToInteger: 1024.
{ i = j. i hash = j hash }
--
Christopher Oliver Traverse Communications
Systems Coordinator 223 Grandview Pkwy, Suite 108
oliver at traverse.com Traverse City, Michigan, 49684
(define magic (lambda (f) (lambda (x) x)))
(define (more-magic n) (lambda (f) (lambda (x) (f ((n f) x)))))
More information about the Squeak-dev
mailing list
|