Use open address for collision resolution in OrderedHashMap

ftanuma commented 2 months ago

Summary: Change the way OrderedHashMap handles collision; Use linear probing instead of chaining.

Couple of things are also modified to make it work.

In case for erasing an entry, mark the bucket as deleted and remove it during rehash. We cannot simply make the bucket empty because it will cause "find" to fail when there was collision and do linear probing.
rehashIfNecessary is changed to rehash, which now always run rehash even if the new capacity ends up the same size. This is necessary to wipe the deleted buckets. And so, we also use the deleted count to decide whether to rehash or not.
Instead, introduce shouldShrink, shouldRehash to decide whether to invoke rehash.
In insert(), run rehash before actually inserting the new entry. This is necessary to make sure that there is a room for insert.
The inner loop of rehash function iterates on the linked list instead of the hash array. This not only is necessary for reusing the same hash array when the size is the same, but also reduces the iteration count. This can reduce the memory access locality during rehash, but still faster than accessing the entire array.

Reviewed By: avp

Differential Revision: D53447832