Thanks for pointing this out. I made an attempt at a bug fix without resorting to a deletedKey and wrote a better unit test. It seems to work properly now.
- Maxime
Marc Feeley wrote:
There is a bug in the algorithm for deleting a key from a hash map (method remItem).
Imagine the scenario where the keys are added in turn A, B, C where A and C hash to the index 1 and B hashes to the index 2. The array containing the elements will be:
0 1 2 3 4+---+---+---+---+---+ | | A | B | C | | +---+---+---+---+---+
If the key A is removed, it will be replaced by "freeKey" and B and C will not move. But if C is then looked up in the hash map it will not be found.
You really need 2 code:
freeKey = this element has never contained a key (since the hash table was created or resized)
deletedKey = this element used to contain a key which has since been deleted.
It is possible to do away with the "deletedKey" code, but it requires (in general) rehashing the table, which is a very high price to pay.
Check the Gambit sources for the algorithms in Scheme and C, or an algorithms textbook.
Marc
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list