hash - 为什么 Redis dict 中的负载因子设置为 1

Question

众所周知，在哈希表中，负载因子对于控制冲突很重要。

在 Java/HashMap 中，默认加载因子为0.75，而在 CPython/dict 中，加载因子设置为2 / 3

但是，在 Redis/dict 中是1.0（启用 dict_can_resize 时），为什么？

/* If we reached the 1:1 ratio, and we are allowed to resize the hash
 * table (global setting) or we should avoid it but the ratio between
 * elements/buckets is over the "safe" threshold, we resize doubling
 * the number of buckets. */
if (d->ht[0].used >= d->ht[0].size &&
    (dict_can_resize ||
     d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

在我看来，负载因子应该小于1。由于可能的高冲突率，高负载因子可能会增加查找成本。

标签： hashredishashmap

Answer 1

高负载因子也更节省内存。Redis 是一个内存数据库，它需要内存高效。我认为 Redis 的作者做了一些基准测试来平衡内存使用和性能。