hashtable enhancements

[GoogleCodeExporter]

i) change the resizing policy according to the Java HashMap class. Table
shall be resized if and only if load factor of 0.75 is reached.
ii) change the algorithm that moves the items to head of the bucket.
Instead use an access count and let that access count guide us.

Original issue reported on code.google.com by oktaka...@gmail.com on 17 Nov 2009 at 8:16

[GoogleCodeExporter]

Original comment by sum...@gmail.com on 17 Nov 2009 at 8:17

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

Hopskotch hash is thought as an alternative but we do not have the needs of
concurrent access which that hash table implementation gives good performace. 
So we
stick with the following scheme for our hash table:
- Lazy deletion
- Separate chaining
- move-to-front heuristic
- special integer hash for better uniformity on pointer keys.
- load factor of 0.75 ( inspired from Java.HashMap)

move-to-front heuristic is typically based on strong access patterns of 
profilers.
Basic sanity is done, but more sanity testing should be performed. the tests
performed should be found in svn under test/testhtab.c.

Original comment by sum...@gmail.com on 17 Nov 2009 at 3:12

[GoogleCodeExporter]

Lazy deletion previously only marking item as free and returning. This is adding
extra overhead/complextity to the current code. And also, we cannot use free 
items
effectively in table resizing code. For all these factors, free items should be
recycled separately. We already have a "freelist" implementation. Will try to
integrate it to the hash table, or use a very simple approach like a simple 
linked
list structure per hash table. The second sounds better.

Original comment by oktaka...@gmail.com on 19 Nov 2009 at 3:08

[GoogleCodeExporter]

Original comment by sum...@gmail.com on 25 Nov 2009 at 8:07

• Changed state: Verified

[GoogleCodeExporter]

Issue 7 has been merged into this issue.

Original comment by sum...@gmail.com on 23 Feb 2010 at 7:12