HashMap performance in JAVA8
I had a question when I found out the source code for HashMap in java8.
Is the source code as complex as it is efficient?
So I wrote some code about 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 am showing results in Excel. enter image description here
I am using java6u45 java7u80 java8u131.
I don't understand why java8 performance would be so bad
I am trying to write my own HashMap.
I would like to know the HashMap in java8 which is better, but I have not found it.
source to share
The test case is not optimal for Java 8 HashMap
. HashMap
in Java 8 optimizes conflicts by using binary trees for any hash chain that exceeds a given threshold. However, this only works if the key type is comparable. If not, the overhead of testing to see if optimization is possible makes Java 8 HashMap
slower. (The slowdown is more than I expected ... but that's a different topic.)
Modify the class Test
to implement Comparable<Test>
... and you will see Java 8 performs better than others when the hash collision rate is high.
Note that tree optimization should be viewed as a protective measure for the case where the hash function fails. Optimization turns O(N)
worst case performance O(logN)
into worst case.
If you want your instances to HashMap
be searchable O(1)
, you must make sure to use an appropriate hash function for the key type. If the likelihood of collision is minimized, optimization is moot.
Is the source code as complex as it is efficient?
This is explained in the comments in the source code. And maybe in other places that Google can find for you :-)
source to share