[Haskell-cafe] Very imperfect hash function

[John Lato]

On Fri, Jan 29, 2010 at 12:46 PM, Hans Aberg <haberg at math.su.se> wrote:
> On 29 Jan 2010, at 12:52, John Lato wrote:
>
>>> There are minimal perfect hash functions; there are some libraries
>>> mentioned here, though they are not in Haskell code:
>>>  http://en.wikipedia.org/wiki/Perfect_hash_function
>>>
>>> This is suitable when you do a lot of lookups with few key updates. An
>>> alternative might be Data.Map, where lookups have time complexity
>>> O(log n), n = size of map.
>>
>> The minimal perfect hash function looks like the real algorithmic
>> solution, but I would just use Data.IntMap for this.
>
> 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?  Are you
basically just suggesting to stick everything in an array with the key
as an index?  Or are you suggesting an actual hash table?  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.

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

Cheers,
John