Data.HashTable weirdness

[Simon Marlow]

> I have some code that uses the Data.HashTable module (passing 
> around a 
> hash table as part of the state in a state monad). I had a 
> function which
> took a key and value and added it to the hash table, using 
> the HashTable.insert
> function. When I changed this function to delete the key from 
> the table first,
> using HashTable.delete, the behavior of the function changed. 
> That is, at
> first, looking up a key in the table gave a wrong result 
> (seemingly, a "stale"
> value), but after changing the function to delete the key 
> before adding it,
> my program behaved correctly.
> 
> This seems strange to me. According to my understanding of 
> how a hash table
> should work, inserting a key in the table should overwrite 
> the previous value
> for that key, so inserting a key should be equivalent to 
> deleting it and then
> inserting it. But clearly that's not the case here. Can 
> anyone explain this?

Inserting doesn't actually delete other entries with the same key (for
speed), but as far as I can tell that shouldn't make any difference to
the semantics.  If you insert then lookup the same key, you should
always get the most recently inserted value back.

That is, unless the compare and hash functions passed to
Data.HashTable.new are wrong.  The docs should probably say that, for
'new eq hash', the following implication should hold:

   eq A B  =>  hash A == hash B

Assuming this isn't your problem, you may have found a bug.  Can you put
together a repeatable test case?

Cheers,
	Simon