[Haskell-cafe] Very imperfect hash function

[Hans Aberg]

On 29 Jan 2010, at 15:57, John Lato wrote:

>> That looks interesting too. Yet another idea: use arrays
>>  http://haskell.org/haskellwiki/Arrays
>> Then build a hash table, say just taking mod k n, and have values  
>> in some
>> lookup map. If n > set of keys, average time complexity is O(1),  
>> and arrays
>> should be very fast.
>
> I just want to be sure I understand this.  For this plan, you aren't
> intending to use a perfect hash function at all, correct?

Yes, this is another idea. In a hash table, it is not important to  
have different indices, only that that table entries are as flat as  
possible.

> 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.

> 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))

> In either case, I don't think this would be as good as what I thought
> was your original suggestion, i.e. using a minimal perfect hash
> function mphf that hashes keys to a value 0..v-1.  With v=number of
> values, valArr = array of all values, then
>
> lookup k = valArr ! mphf k

Right, but you may have to avoid implementing the perfect hash  
function by yourself, if it is only available in C. :-) There is a  
FFI, though.

   Hans