[Haskell-cafe] Pure hashtable library

[Richard A. O'Keefe]

Someone wrote:
>>
>> trie: O(len)*O(width)
>> hashed trie: O(len)
>> hash: O(len)

If "width" here refers to the branching factor of the trie,
it's actually O(len.lg(width)), and the width that matters
is not the *possible* number of choices but the *actual*
number.

The great problem with hash tables is devising good hash
functions.  There is a vast literature about hash tables,
but there is very little about how to design good hash
functions for anything other than numbers and maybe strings.
It would be nice to think that _had__ there been plenty of
good advice about constructing good hash functions the Java
library implementors would have taken it.  As it is, their
hashing functions for collections leave much to be desired.