CODEWITHSUNDEEP
javajava-8
zzjbook
zzjbook

Reputation: 97

The performance of the HashMap in JAVA8

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;       
    }           
}

I show the results in Excel。 enter image description here

I am using java6u45 java7u80 java8u131。

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

I'm trying to write my own HashMap.

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

Upvotes: 5

Views: 3172

Answers (1)

Stephen C
Stephen C

Reputation: 718668

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.)

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.

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.

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?

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

Upvotes: 7

Related Questions