[Haskell-cafe] Re: String Hashing

[Thomas Conway]

On 6/18/07, apfelmus <apfelmus at quantentunnel.de> wrote:
> Do you need the hash function for a hash table or for
> fingerprints/signatures? In the former case, Tries are a much better
> choice. For launching your own trie, see also

I'm actually using them for bucket addressing for external indexing
with a linear hash table. (Yes, the hashing does count, because
buckets are cached in memory.)

Actually, if one wants a concurrent dictionary, using something in the vein of

type HashTable k v = TVar (Array Int (TVar [(k,v)]))

has very good performance. It always seems something of a shame that
if you want all the benefits of lazy functional programming, you too
often have to settle for O(n log n) data structures.

<non-haskell-slight-rant>
Incidentally, while I've got your attention, I note that if you use a
good quality hash function like the one I ripped off, you don't need
to use [mostly] prime numbers for sizing your hash tables, and you can
use powers of two instead, which simplifies a bunch of things. This is
kind of obvious when you think about it, but every hash function I
came across as an undergraduate or even as a post-grad, with the
exception of md5 et al, was not good.  The dogma was that *good* hash
functions are too expensive for everyday use. So a word of advice to
all you worthy tertiary educators - this is not the 1970s any more -
good, cheap hash functions do exist, so update your course notes. :-)
</non-haskell-slight-rant>

We return you now to your normal haskell programming....

cheers,
T.
-- 
Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.