标签: load-factor

HashMap有两个重要的属性:size和load factor.我浏览了Java文档,它说的0.75f是初始加载因子.但我找不到它的实际用途.

有人可以描述我们需要设置负载因子的不同场景以及针对不同情况的一些样本理想值吗？

Java doc说 - 当哈希表中的条目数超过加载因子和当前容量的乘积时,哈希表被重新哈希

在以下程序中 -

HashMap<Integer, String> map = new HashMap<Integer, String>();
int i = 1;
while(i<16) {
    map.put(i, new Integer(i).toString());
    i++;
}

键是Integer类型,在插入第13到第15个元素时,HashMap容量保持为16,阈值保持与12相同,为什么？

在地图中添加第13个元素后调试屏幕截图 -

args                 String[0] (id=16)
map HashMap<K,V> (id=19)
 entrySet   null
 hashSeed   0
 KeySet     null
 loadFactor 0.75
 modCount   13
 size       13
 table      HashMap$Entry<K,V>[16] (id=25)
 threshold  12
 values     null
i   14

[null, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10, 11=11, 12=12, 13=13, null, null] 

具有String类型的键的HashMap - HashMap<String, String>或自定义类 - Map<Employee,Integer>显示第13次插入时的预期行为

我试图理解,当超过所占用的桶数或所有桶中的条目总数时,会发生散列图的重新发生.意思是,我们知道如果16个桶中的12个(每个桶中有一个条目)已满(考虑到默认的loadfactor和初始容量),那么我们就知道在下一个条目中将重新散列hashmap.但是假设只有3个桶被占用,每个4个条目(总共12个条目,但16个中只有3个桶在使用中)呢？

所以我尝试通过制作最差的哈希函数来复制它,这将把所有条目放在一个桶中.

这是我的代码.

class X {

    public Integer value;

    public X(Integer value) {
        super();
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        X a = (X) obj;
        if(this.value.equals(a.value)) {
            return true;
        }
        return false;
    }

}

现在我开始在hashmap中放置值.

HashMap<X, Integer> map = new HashMap<>();
    map.put(new X(1), 1);
    map.put(new X(2), 2);
    map.put(new X(3), 3);
    map.put(new X(4), 4);
    map.put(new X(5), 5);
    map.put(new X(6), 6);
    map.put(new X(7), 7);
    map.put(new X(8), 8);
    map.put(new X(9), 9); …

hashmap 的负载因子 os 的默认值是 0.75f，即一旦 hasmap 容量的 75% 被填满，它将重新散列哈希图。如果我将负载因子的值设置为大于 1，例如让我们说 2 (super(capacity+1, 2.0f, true);)

它将如何在 sch 情况下工作以及散列将如何在这里工作？

为什么建议在单独链接中将负载因子设为 1？

我看到很多人说它是推荐的，但没有给出明确的解释原因。

在开放寻址中，我知道负载因子应该在 0.5 到 0.7 之间，因为在处理冲突时找到未占用的索引应该是一个快速的操作。但我不明白为什么在单独链接中负载因子为 1 应该更好。我的意思是，如果我有一个大小为 100 的表，是否还有机会将所有 100 个元素散列到相同的索引并放在同一个列表中？天啊，我真的无法理解为什么这个单独链接的特定负载因子应该是 1。

在算法类和授权书籍中，负载因子小于 1，就像 Java 一样，默认值为 0.75。但在redis源代码中，负载因子是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 …

我试图找出 Python 集的内部负载因子是多少。对于使用负载因子为 0.66 (2/3) 的哈希表的字典来说。存储桶的数量从 8 开始，当插入第 6 个键时，存储桶的数量增加到 16 下表显示了存储桶的变化。

这可以通过以下 Python 代码看出，其中字典和集合的大小通过 getsizeof 方法显示：

import sys
d = {}
s = set()

for x in range(25):
    d[x] = 1
    s.add(x)
    print(len(d), sys.getsizeof(d), sys.getsizeof(s))

我正在使用大型(数百万)hashmap实现Java,实际上构建的容量为10.000.000,加载因子为.75,它用于缓存一些值

因为缓存的值随着时间的推移变得无用(不再被访问)但是我无法删除无用的值,而我想在它的性能开始降低时完全清空缓存.我该怎么决定什么时候做好呢？

例如,当它达到750万个元素时,我应该清空它的1000万容量和.75 因为我尝试了各种阈值,但我希望有一个分析值.

我已经测试了这样一个事实:当它非常饱满时将它移除是对性能的提升(擦除之后的前2-3次算法迭代只是填充它,然后它开始比擦除之前更快地运行)

编辑:附加信息

hashmap长按键并浮动为值.它包含内容的缓存关联,因为它是我想缓存它们的标记向量的点积(以提高性能).

所以基本上我所做的是long使用2个内容的哈希码计算密钥:

static private long computeKey(Object o1, Object o2)
{
    int h1 = o1.hashCode();
    int h2 = o2.hashCode();

    if (h1 < h2)
    {
        int swap = h1;
        h1 = h2;
        h2 = swap;
    }

    return ((long)h1) << 32 | h2;
}

并使用它来检索存储的值.会发生的是,因为它是一个层次化的聚类内容被合并,并且不再需要它们与其他内容的相关值..这就是为什么我想不时擦除哈希映射,以避免由于其中无用的值而导致的降级.

WeakHashMap当仍然需要时,使用遗嘱会无法预测地删除数据.我无法控制它.

谢谢

我正在使用使用单独链接作为冲突解决技术的哈希表。

我确实知道一般公式是 N/table_length，其中 N 是表中当前项目的数量。

我对分母有点困惑。它是数组的大小+链式元素的数量，还是只是数组的大小？