[Haskell-cafe] Pure hashtable library

[Daniel Fischer]

Am Mittwoch, 27. August 2008 17:36 schrieb 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)

Wouldn't the hashtable have lookup time O(len+bucketsize)?

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