FWIW, here's a link to the original c code: http://www.burtleburtle.net/bob/hash/evahash.html -- Dr Thomas Conway drtomc@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

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

Thomas Conway wrote:

On 6/18/07, apfelmus 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.)

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.

Trie it is, not balanced tree. A logarithm in this would be new to me. :) As a side node, Mr. Exp says: 64 is large enough for the size needs of any logarithm.

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

Don't you want a TArray Int [(k,v)]? In any case, you could be able to set up an infinite trie and have lazy evaluation allocate space as needed: type Trie a = Branch (TVar a) (Trie a) (Trie a) -- an infinite tree with different TVars at every branch {-# NOINLINE tree -#} tree :: a -> Trie a tree x = Binary (unsafePerformIO $ newTVarIO x) (tree x) (tree x) The intention is that the different threads concurrently evaluate the suspension as far as they need to lookup/insert a key. The associated value can be put into the fresh TVar they find there. The tree structure itself is left untouched. Of course, it is imperative that all threads see the same TVars. I don't know how thunk updates are handled in a concurrent setting, but as they are write-once only and referentially transparent, i see no major problem with them. Regards, apfelmus PS: Hm, it's probably safer to code the lazy evaluation in the trie manually. As a side effect, you are then able to garbage collect unused but expanded parts of the trie from time to time.

Thomas Conway wrote:

On 6/19/07, apfelmus wrote:

...

Trie it is, not balanced tree. A logarithm in this would be new to me. :)

True enough, my braino.

So, accessing a key in a trie is O(key size in bits), not much different from a hash table.

...

As a side node, Mr. Exp says: 64 is large enough for the size needs of any logarithm.

Que?

A pun(y) formulation of the fact that (log n <= 64) for (almost) any finite map situation you'll ever encounter because 2^64 = 16 Exabyte.

...

In any case, you could be able to set up an infinite trie and have lazy evaluation allocate space as needed:

type Trie a = Branch (TVar a) (Trie a) (Trie a)

Tree-like structure's are quite hostile to highly concurrent manipulation.

It helps to introduce TVar indirections at each level:

data Trie a = Branch (TVar a) (TVar (Trie a)) (TVar (Trie a))

Then you can update a subtree without having to modify the spine of the tree.

What I wanted to point out is that the spine simply doesn't need to be modified at all. In other words, you have an infinite tree residing in memory and insertion/deletion happens by updating the TVars that hold the values (and probably should be of type TVar (Maybe a) then). Of course, there can't be infinite trees in memory :) but lazy evaluation makes it appear as if. In fact, every branch will be modified at most once before the first read and subsequent accesses are read-only. I don't know whether or how this is implemented in concurrent GHC at the moment, but I think that this can safely be implemented with a lock whereas dead-lock means that the program denotes _|_ anyway. Regard, apfelmus

Hello Jan-Willem, Tuesday, June 19, 2007, 1:17:25 AM, you wrote:

table is the right structure to begin with? I fell back on much- simpler multiplicative hashing schemes for Data.HashTable. A

btw, are you seen http://isthe.com/chongo/tech/comp/fnv/ ? he suggest to use non-zero value as starting hash value and provides concrete constants for base and multiplier -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com