JAVA8中HashMap的性能表现

Question

在学习Java8中HashMap的源代码过程中，我有一个问题。

源代码非常复杂，效率有多高？

因此，我编写了一个关于哈希冲突的代码。

public class Test {             
    final int i;            

    public Test(int i) {            
        this.i = i;     
    }           

    public static void main(String[] args) {            
        java.util.HashMap<Test, Test> set = new java.util.HashMap<Test, Test>();        
        long time;      
        Test last;      
        Random random = new Random(0);      
        int i = 0;      
        for (int max = 1; max < 200000; max <<= 1) {        
            long c1 = 0, c2 = 0;    
            int t = 0;  
            for (; i < max; i++, t++) { 
                last = new Test(random.nextInt());
                time = System.nanoTime();
                set.put(last, last);
                c1 += (System.nanoTime() - time);
                last = new Test(random.nextInt());
                time = System.nanoTime();
                set.get(last);
                c2 += (System.nanoTime() - time);
            }   
            System.out.format("%d\t%d\t%d\n", max, (c1 / t), (c2 / t)); 
        }       
    }           

    public int hashCode() {         
        return 0;       
    }           

    public boolean equals(Object obj) {         
        if (obj == null)        
            return false;   
        if (!(obj instanceof Test))     
            return false;   
        Test t = (Test) obj;        
        return t.i == this.i;       
    }           
}

我在Excel中展示结果。 点击此处查看图片描述

我正在使用java6u45，java7u80和java8u131。

我不明白为什么java8的性能会如此糟糕。

我试着写自己的HashMap。

我想学习java8中更好的HashMap，但是我没有找到它。

- zzjbook

---

直接返回一个静态值的hashCode()实现方式是非常糟糕的。不要这样做。使用return Integer.hashCode(i);，你应该会看到性能更好。 - Elliott Frisch

@ElliottFrisch 我正在测试哈希冲突。 - zzjbook

HashMap 的性能取决于你放入其中的键的 hashCode() 方法实现得有多好。如果你有一个糟糕的 hashCode() 方法，不要指望它能表现出色。这就像你有一台闪亮新引擎，然后你往里面扔沙子，然后抱怨它表现不佳... - Jesper

@Jesper，我只是比较Java6、Java7和Java8的HashMap，而不是如何使HashMap更有效率。我正在尝试编写自己的HashMap。我想学习Java8中更好的HashMap，但我没有找到它。 - zzjbook

你的基准测试看起来不对 - 使用jmh。另请参阅https://dev59.com/hHRB5IYBdhLWcg3wz6UK - assylias

Answer 1

你的测试方案对于Java 8的HashMap不是最优的。在Java 8中，如果哈希链超过给定阈值，则使用二叉树来优化碰撞。但是，只有在键类型可比较时才有效。如果无法比较，则测试是否可以进行优化的开销实际上会使Java 8的HashMap变得更慢。（这种减速比我预期的要严重...但这是另一个话题。）

将你的Test类更改为实现Comparable ...然后你应该能看到当哈希冲突比例足够大时，Java 8的表现比其他版本更好。

请注意，树形优化应被视为一种防御性措施，用于情况哈希函数不起作用的情况下。优化将O(N)最坏情况性能转换为O(logN)最坏情况性能。

如果你想让你的HashMap实例具有O(1)查找，请确保使用适合键类型的良好哈希函数。如果碰撞的概率被最小化，那么优化就毫无意义。

源代码非常复杂，效率如何？

在源代码的注释中已经解释了这一点。可能还有其他Google可以找到的地方 :-)

- Stephen C

---

HashMap中的二叉树也会比较哈希值。 为什么不使用2次选择哈希？ - zzjbook

HashMap（Java 8）中的二叉树不使用哈希值，而是比较实际键。请再次阅读代码。 - Stephen C

@Stephen C：实际上，OP是正确的，二叉树确实使用哈希码来解决桶碰撞问题。只有在真正的哈希冲突的情况下，它才尝试使用可比较的键，然后使用标识哈希码。我也问过自己，为什么它不使用2选择哈希或类似的东西，但是，在OP的情况下，那也没有帮助。 - Holger