[Haskell-cafe] Simple hash table creation

Bulat Ziganshin bulat.ziganshin at gmail.com
Tue Nov 17 16:38:16 EST 2009

Hello michael,

Wednesday, November 18, 2009, 12:00:58 AM, you wrote:

*Main>> toList ht
> [("miguel",3),("michael",2),("mike",1)] 
> It seems my dummy function is being ignored.

i wonder why you think so?

your ht has all 3 pairs you ever inserted

inside, they all are inside the same bucket since hash function
returns the same value for them

... hmm, i guess that you expect something like low-level hashtable
from other languages - i.e. it should have just one slot for all
values hashed to 7 and save here last value

it works other way - it has just one slot for all your values but it
stores here LIST of your pairs. so nothing is lost. if you want to
save only the last value, replace (==) to (\a b -> dummy a==dummy b)

the whole story is that hash function used to select slot, and then
key part of pair is compared using (==) with keys of all values in the
slot. it will replace existing pair if key1==key2, otherwise added to

so, hashing allows to quickly find pair by its key, but it still full
map as far as you pass a usual (==)

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

More information about the Haskell-Cafe mailing list