The hash table size is increased slightly (up to 5 times before roughly doubling the size) when an overly long chain (between 1 and 63 items depending on table size) is detected.
|
linked list. The hash table size is increased slightly (up to 5 times |
If I understand the code correctly, in order to get these "slight" table size increases, the prime_index should only be increased by one in this case:
|
uint new_prime_index = self->prime_index + GROWTH_FACTOR; |
Increasing the prime index by GROWTH_FACTOR effectively always doubles the size.
Whether the described "slight increase" behavior would be desirable or not is another question. I guess the intent is to attempt to "rebalance" the table for a more uniform hash distribution, but rehashing is an expensive operation at scale. Ultimately, though, the current implementation doesn't seem to match the design intent per the description and the prime table design itself (if the prime index always grows by 5, most of the entries in the table will never be used).
If I understand the code correctly, in order to get these "slight" table size increases, the prime_index should only be increased by one in this case:
czmq/src/zhashx.c
Line 254 in b669c7e
Increasing the prime index by GROWTH_FACTOR effectively always doubles the size.
Whether the described "slight increase" behavior would be desirable or not is another question. I guess the intent is to attempt to "rebalance" the table for a more uniform hash distribution, but rehashing is an expensive operation at scale. Ultimately, though, the current implementation doesn't seem to match the design intent per the description and the prime table design itself (if the prime index always grows by 5, most of the entries in the table will never be used).