On 6/18/07, apfelmus
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@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.