[Haskell-cafe] Pure hashtable library

[Bulat Ziganshin]

Hello Jules,

Wednesday, August 27, 2008, 7:21:46 PM, you wrote:

>> given these constraints, it should be just a 10-20 lines of code, and provide much better efficiency than any tree/trie implementations

> Prove it.

> To get "much better efficient" than a trie, the hash function has to be
> so fast that it is faster than following (log n) pointers

afaiu, trie search follows n pointers - i.e. every char in string
forms a new trie level. add to this that every search need to scan a
list of all possible chars - or you need to use the same hashing. so,
we have the following lookup times:

trie: O(len)*O(width)
hashed trie: O(len)
hash: O(len)

where len is length of string searched and width is average amount of
chars at each trie level



-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com