[Haskell-cafe] Very imperfect hash function

John Lato jwlato at gmail.com
Sun Jan 31 14:07:28 EST 2010

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.


More information about the Haskell-Cafe mailing list