Written by:
Tommy Pettersson, tommypet@kth.se
Helena Sjöberg, hsjob@kth.se

Effective implementation of hashtables

Abstract
This report is written in order to evaluate how efficient two different hashing schemes, Cuckoo Hashing and the fairly new Hopscotch Hashing, are in comparison to the native HashMap provided in java.util.hashmap. In order to investigate this, we implement the two hashing schemes in Java and measure the performance in respect to speed and memory usage. HashMap is found to be quicker for individual operations, but our implementations are quicker in the worst-case. These results are analyzed and discussed. We also discuss how the two schemes could be parallelised. Finally, we provide our implementation of CuckooHashMap and HopscotchHashMap.