Hash table optimized for full iteration + key replacement

Question

I have a hash table where the vast majority of accesses at run-time follow one of the following patterns:

• Iterate through all key/value pairs. (The speed of this operation is critical.)
• Modify keys (i.e. remove a key/value pair & add another with the same value but a different key. Detect duplicate keys & combine values if necessary.) This is done in a loop, affecting many thousands of keys, but with no other operations intervening.

I would also like it to consume as little memory as possible.

Other standard operations must be available, though they are used less frequently, e.g.

• Insert a new key/value pair
• Given a key, look up the corresponding value
• Change the value associated with an existing key

Of course all "standard" hash table implementations, including standard libraries of most high-level-languages, have all of these capabilities. What I am looking for is an implementation that is optimized for the operations in the first list.

Issues with common implementations:

• Most hash table implementations use separate chaining (i.e. a linked list for each bucket.) This works but I am hoping for something that occupies less memory with better locality of reference. Note: my keys are small (13 bytes each, padded to 16 bytes.)
• Most open addressing schemes have a major disadvantage for my application: Keys are removed and replaced in large groups. That leaves deletion markers that increase the load factor, requiring the table to be re-built frequently.

Schemes that work, but are less than ideal:

• Separate chaining with an array (instead of a linked list) per bucket:
  Poor locality of reference, resulting from memory fragmentation as small arrays are reallocated many times
• Linear probing/quadratic hashing/double hashing (with or without Brent's Variation):
  Table quickly fills up with deletion markers
• Cuckoo hashing
  Only works for <50% load factor, and I want a high LF to save memory and speed up iteration.

Is there a specialized hashing scheme that would work well for this case?

---

Note: I have a good hash function that works well with both power-of-2 and prime table sizes, and can be used for double hashing, so this shouldn't be an issue.

Answer 1

Would Extendable Hashing help? Iterating though the keys by walking the 'directory' should be fast. Not sure if the "modify key for value" operation is any better with this scheme or not.