[Haskell-cafe] Pure hashtable library

[Bulat Ziganshin]

Hello Richard,

Thursday, August 28, 2008, 5:28:46 AM, you wrote:

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

> If "width" here refers to the branching factor of the trie,
> it's actually O(len.lg(width)), and the width that matters
> is not the *possible* number of choices but the *actual*
> number.

i thought about using list to hold all variations at the trie node. with
a (balanced) tree at each node we will have even more overheads


> The great problem with hash tables is devising good hash
> functions.  There is a vast literature about hash tables,
> but there is very little about how to design good hash
> functions for anything other than numbers and maybe strings.

1. tries also work only for strings and other lists
2. i don't want to go into discussing well-known pluses and minuses of
data structures. my point was just that we have great alternative to
trees/tries which should be implemented many years ago. i've used a
lots of assoclists in my program, sometimes this really degraded
performance (although it's yet another question - why tree/trie
structures doesn't provide simple List.lookup replacement function and
why i'm so lazy to still not learning their APIs)



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