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哪个更好,但是我找不到它.

Answer 1

您的测试场景对于Java 8来说不是最佳的HashMap. HashMap在Java 8中,对于长于给定阈值的任何哈希链,使用二叉树来优化冲突.但是,这仅在密钥类型具有可比性时才有效.如果不是那么测试以确定优化是否可能实际上使Java 8 HashMap变慢.(减速比我预期的要多......但这是另一个话题.)

更改您的Test类以实现Comparable<Test>...并且您应该看到当哈希冲突的比例足够大时,Java 8的性能优于其他Java.

请注意,树优化应被视为散列函数不执行的情况下的防御措施.优化将O(N)最坏情况的性能变为O(logN)最坏情况.

如果您希望HashMap实例具有O(1)查找功能,则应确保为密钥类型使用良好的哈希函数.如果碰撞概率最小化,则优化没有实际意义.

源代码是如此复杂,效率有多大？

它在源代码的注释中进行了解释.也许Google可以为您找到的其他地方:-)