JAVA8中HashMap的性能 [英] The performance of the HashMap in JAVA8

问题描述

当我在java8中学习HashMap源代码时，我有一个问题。

I had a question when I learned the HashMap source code in java8。

源代码是如此复杂，效率是多少？

Source code is so complicated, how much efficiency?

所以我写了一个关于哈希冲突的代码。

So I wrote a code about the hash conflict。

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中显示结果。
在此输入图片说明

I show the results in Excel。 enter image description here

我正在使用java6u45 java7u80 java8u131。

I am using java6u45 java7u80 java8u131。

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

I do not understand why the performance of java8 will be so bad

我正在尝试编写自己的HashMap。

I'm trying to write my own HashMap.

我想在java8中学习HashMap哪个更好，但是我找不到它。

I would like to learn HashMap in java8 which is better, but I did not find it.

推荐答案

对于Java 8 HashMap ，您的测试场景不是最佳的。 Java 8中的 HashMap 通过对任何超过给定阈值的哈希链使用二叉树来优化冲突。但是，这仅在密钥类型具有可比性时才有效。如果不是那么测试的开销实际上使得Java 8 HashMap 更慢。 （减速比我预期的要多......但那是另一个话题。）

Your test scenario is non-optimal for Java 8 HashMap. HashMap in Java 8 optimizes collisions by using binary trees for any hash chains longer than a given threshold. However, this only works if the key type is comparable. If it isn't then the overhead of testing to see if the optimization is possible actually makes Java 8 HashMap slower. (The slow-down is more than I expected ... but that's another topic.)

更改测试要实现 Comparable< Test> 的类，你应该看到当哈希冲突的比例足够大时，Java 8的性能优于其他的。

Change your Test class to implement Comparable<Test> ... and you should see that Java 8 performs better than the others when the proportion of hash collisions is large enough.

请注意，树优化应被视为散列函数不执行的情况下的防御措施。优化将 O（N）最坏情况性能转换为 O（logN）最坏情况。

Note that the tree optimization should be considered as a defensive measure for the case where the hash function doesn't perform. The optimization turns O(N) worst-case performance to O(logN) worst-case.

如果您希望 HashMap 实例拥有 O（1）查找，你应该确保你为密钥类型使用一个好的哈希函数。如果碰撞概率最小化，优化就没有实际意义。

If you want your HashMap instances to have O(1) lookup, you should make sure that you use a good hash function for the key type. If the probability of collision is minimized, the optimization is moot.

源代码是这样的复杂，多少效率？

Source code is so complicated, how much efficiency?

源代码中的注释对此进行了解释。也许Google可以为您找到的其他地方： - ）

It is explained in the comments in the source code. And probably other places that Google can find for you :-)

这篇关于JAVA8中HashMap的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！