There are other problems with the hash map implementation:
1)
// Initial hash map size HASH_MAP_INIT_SIZE = 89;
By starting the hash table at this size, the minimal object size (on a 32 bit machine) is 89 * 2 * 4 bytes = 712 bytes (plus some overhead for headers, etc). This is an immense waste for objects with few properties. For reference, by default the Gambit hash tables are allocated with space for 5 elements. As more keys are added the hash table will grow, and as keys are deleted the hash table will shrink to maintain the load factor within a certain range. The current load factor should count deleted keys as part of the "load". That way, a table that gets filled with deleted keys will eventually be rehashed and the deleted keys will be purged from the table.
2) Table contraction should also be implemented by the remItem method. For this it is necessary to give a minimum and maximum load factor.
3) Growing the table by a factor of 2 is too much. When a load factor range is defined, it is possible to compute the new size so that it falls somewhere in the middle of the load factor range (more precisely the square root of the product of the minimum and maximum load factors). That way, it will take a substantial number of key inserts/deletes before the table needs to be resized.
4) The table should only expand when a key is actually added and the load factor maximim is exceeded. Currently, if a key is in the table and the load is at maximum, the table is resized anyway.
Marc
On 2010-06-27, at 11:54 PM, 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