Optimizing Open Addressing

> (that is actually the worst thing you could possibly do)

Nonsense, there are many worse things you could do. For example, you could allocate nodes with mmap, at 4KB per node. (Which is a thing I've actually done in the context of cursed bootstrap code where malloc isn't available and having more than a handful of (in that case doubly-linked-list) nodes means the environment is deranged anyway.)

Chaning still requires a flat table, which can change in size, and is proportional to the number of entries in the table (to keep the average chain length ("load factor") bounded). Thus, this can still cause memory fragmentation, even though the hash table chain nodes can all be the same size and so reduce fragmentation.

In terms of absolute bytes, ignoring fragmentation, it depends on the load factors.

In chaining, you need at least a singly linked list. Let's assume that our nodes store the hash value, as well as the key, value and a next pointer: so four pointer-sized words. (You don't have to store the hash code, but you'd be foolish not to, because it can reject mismatches in a single one-word comparison, avoiding the need to do a full key comparison.)

In addition, each chain needs a pointer-sized word which points to it from the table. (We ignore remaining overheads, like the small data structure which keeps the table and other bookkeeping info.)

Let's assume we keep the load factor (maximum average chain length) to 4. Beyond that we will increase the table size. So the chained table is considered 100% full with 4 nodes per chain on average. In this situation, the root table is amortized as 1/4 word overhead per node: so each node effectively 4.25 nodes.

An open-addressed table stores keys and values. To make the comparison fair, it should also store the hash codes; they are needed for the same reason: as we probe over collisions, we can use them to reject non-matching keys.

So, when it's 100% full, it needs 3 words per entry. In this situation, it's beating the 4.24 value of chained hashing. However, we would never want an open-addressed table to get 100% full, because the performance degrades, regardless of the collision resolution strategy. Say we allow up to 80%. 20% (0.2 x 3 words = 0.6 words per entry) of the table is wasted space, so 3.75. Still beating chained.

Now let's look at the half full situation. Below half full we might reorganize either table to be smaller, so that's our worst case.

When the chained table is half full, the average chain length is 2, and so each node needs 4.5 words: the table part represents more overhead, but the value doesn't change much from the maximum load case.

The half-full open-addressed table basically wastes 60% of the table: it's as if each item requires 7.5 words rather than 3. In this minimum load case, it is losing to chained hashing. (Remember, full is 80%, so half of that is 40%).

Summary:

   Words per entry*:
    
       \ Method
   Load \          Chained      Open Addressing
         +---------------------------------------
   half  |         4.5          7.5
         |
   full  |         4.25         3.75
         

   * Words are pointer-sized scalar values
   * For chained: full means load factor of 4; half means load factor of 2.
   * For open addressing: full means 80% of the table, half is 40% of the table
   * Assuming entries store hash code, key and value.

There is no clear winner in terms of memory, but it's looking as if the improvement from open addressing may not be that great, if at all realized. Of course, the values are debatable; why should the max load factor for chaining be 4? Or may be more than 80% can be crammed into an open-adressed table. I'm kind of surprised; according to the parameters I chose, I thought that open addressing would hit a better density.

What points in favor of the open addressing is caching behavior: avoiding the dependent loads of pointer chasing. For Open-Addressing, cache-friendly collision strategies can be chosen so when multiple entries are probed, they tend to be cached close together in the same block.

To be fair, that’s been true of the past 20 years if not more.

> In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself.

Or you could just write the open-addressing HashMap, which is easier than implementing your own custom small allocation malloc()/free()?

That's the thing. To make chaining competitive against open-addressing HashMaps, you've got to bend-over backwards and its suddenly not easy anymore. Though you're right in that different versions of malloc/free could be more efficient. Ex: tcmalloc() has small allocations built in already like you mention.

But even if you erase those 8-bytes from the glibc chunk implementation of malloc, you're _still_ 8-bytes over the open-addressing implementation (you can't get rid of the 8-byte "next" pointer). So all that work and you're still worse off than the other methodology.

I was actually wondering about that - it appears a (i+i^2)/2 sequence makes insertions (and by extension erases with rehashing) 7-10% faster, which is pretty significant. Lookups and probe lengths are about the same, so I think the conclusions stand.