[Haskell-cafe] Simple hash table creation

[michael rice]

Hi Bulat,

I was just looking for a simple hashing function. I was going to use the length function but a constant int is even simpler.  I'm supposing that had I used the length function "mike" and "fred" would end up in the same bucket.

This is the first time I've tried to do anything in Haskell with data structures other than lists, so I needed to see how things work.

Thanks, everyone, for the help.

Michael

--- On Tue, 11/17/09, Bulat Ziganshin <bulat.ziganshin at gmail.com> wrote:

From: Bulat Ziganshin <bulat.ziganshin at gmail.com>
Subject: Re[2]: [Haskell-cafe] Simple hash table creation
To: "michael rice" <nowgate at yahoo.com>
Cc: "Gregory Crosswhite" <gcross at phys.washington.edu>, haskell-cafe at haskell.org
Date: Tuesday, November 17, 2009, 4:38 PM

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
list

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




      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091117/b5137322/attachment.html