In algorithm classes and authorized books, load-factor is smaller than 1 as it is with Java the default is 0.75. But in redis source code, the load factor is 5.
54 /* Using dictEnableResize() / dictDisableResize() we make possible to
55 * enable/disable resizing of the hash table as needed. This is very important
56 * for Redis, as we use copy-on-write and don't want to move too much memory
57 * around when there is a child performing saving operations.
58 *
59 * Note that even when dict_can_resize is set to 0, not all resizes are
60 * prevented: a hash table is still allowed to grow if the ratio between
61 * the number of elements and the buckets > dict_force_resize_ratio. */
62 static int dict_can_resize = 1;
63 static unsigned int dict_force_resize_ratio = 5;
Why is it?
2
Answers
The load factor to start rehashing is ~1. The
dict_force_resize_ratio
value is a safety measure such that even if rehashing is disabled, once it gets to that load factor it will force it.You can see this in
_dictExpandIfNeeded(dict *d)
indict.c
Redis allows ~1 to start rehashing since the rehashing is not done all at once. It is progressively done by maintaining two hash tables.
See
dict.h
:And in
dict.c
:And there is some additional insight in
redis.conf
, for theactiverehashing
setting.Because in Redis, load_factor is calculated by:
ht[0].used/d->ht[0].size
,used
means the count of elements in the hash table,size
means only the size of the underlying array, so if hash conflict happens, elements will be stored in a linked list, the size of which is not included inht[0].size
.