Java HashMap performance optimization / alternative

by

As many people pointed out the hashCode() method was to blame. It was only generating around 20,000 codes for 26 million distinct objects. That is an average of 1,300 objects per hash bucket = very very bad. However if I turn the two arrays into a number in base 52 I am guaranteed to get a unique hash code for every object:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

The arrays are sorted to ensure this methods fulfills the hashCode() contract that equal objects have the same hash code. Using the old method the average number of puts per second over blocks of 100,000 puts, 100,000 to 2,000,000 was:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

Using the new method gives:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

Much much better. The old method tailed off very quickly while the new one keeps up a good throughput.

More Related Contents:

  1. Hashmap vs Array performance
  2. Java Reflection Performance
  3. Swing animation running extremely slow
  4. Does Java have a HashMap with reverse lookup?
  5. Efficiently compute Intersection of two Sets in Java?
  6. “Cannot create generic array of ..” – how to create an Array of Map?
  7. Java local vs instance variable access speed
  8. How does Java order items in a HashMap or a HashTable?
  9. Is the ternary operator faster than an “if” condition in Java [duplicate]
  10. What is the time complexity of HashMap.containsKey() in java?
  11. Most efficient way of converting String to Integer in java
  12. What’s wrong with using associativity by compilers?
  13. How can I iterate over a map of ?
  14. Loading a map using Properties class
  15. Why defining class as final improves JVM performance?
  16. Fastest way to strip all non-printable characters from a Java String
  17. Java split String performances
  18. Is there a memory-efficient replacement of java.lang.String?
  19. Theoretical limit for number of keys (objects) that can be stored in a HashMap?
  20. Why are immutable objects in hashmaps so effective?
  21. Sorting HashMap by values [duplicate]
  22. Size of a byte in memory – Java
  23. How can I avoid garbage collection delays in Java games? (Best Practices) [closed]
  24. Java benchmarking – why is the second loop faster?
  25. Fast transcendent / trigonometric functions for Java
  26. Support for Compressed Strings being Dropped in HotSpot JVM?
  27. What are the cases in which it is better to use unconditional AND (& instead of &&)
  28. In JNI, how do I cache the class, methodID, and fieldIDs per IBM’s performance recommendations?
  29. Integer.parseInt(scanner.nextLine()) vs scanner.nextInt()
  30. What is the Java equivalent of Objective-C’s NSDictionary?

Leave a Comment