From: Clifford Heath <no@...>
Date: 2005-05-11T08:30:27+09:00
Subject: Re: String Hashing Algorithms

Phrogz wrote:
> Summary

Good summary and test, Phrogz.

Don't forget that in many hashing algorithms, the cost of computing
the hash function far outweighs the occasional cost of traversing a
chain. If you need guaranteed lookup time, you need a "perfect hash"
(try Googling on that) but otherwise you just need a fast hash function
with an excellent spread and a low load factor. Neither of those is
hard to achieve.

We use linear hashing (note, this is not the same as linear open
addressing, a much older technique), which achieves excellent
performance with any size hash table. Unfortunately I have no
implementation I can publish.

Clifford Heath.