Re:Optimizing Open Addressing
by kazinator on Sunday April 02, 2023 @03:27PM
(#35414173)
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.
Now let's look at the 50% situation. Below 50% we might reorganize either table to be smaller, so that's our worst case.
When the chained table is 50% 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 50% full open-addressed table basically wastes half the table: it's as if each item requires 6 words rather than 3. In this minimum load case, it is losing to chained hashing.
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.
Now let's look at the 50% situation. Below 50% we might reorganize either table to be smaller, so that's our worst case.
When the chained table is 50% 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 50% full open-addressed table basically wastes half the table: it's as if each item requires 6 words rather than 3. In this minimum load case, it is losing to chained hashing.