[Haskell-cafe] Very imperfect hash function

[John Lato]

On Fri, Jan 29, 2010 at 9:26 AM, Hans Aberg <haberg at math.su.se> wrote:
> On 29 Jan 2010, at 15:57, John Lato wrote:
>
>> Are you
>> basically just suggesting to stick everything in an array with the key
>> as an index?
>
> You still need to fold the key values onto some interval.

Not with a suitably large array ;-)

>
>> Or are you suggesting an actual hash table?
>
> The hash function folds the keys onto an interval. Since you have Int values
> k, you might just use a mod k n function for that.
>
>> If it's the
>> latter, I'm not certain where the array fits into the picture.  I'm
>> pretty sure I'm missing something here.
>
> There is a module Data.HashTable. The array is just to make lookup fast.
> Like in:
>  ST s (STArray s HashKey (Map Key Value))

I was misunderstanding your intention here.  This is an interesting
approach, but I would still try an IntMap first.

Cheers,
John