Skriven av:
Tommy Pettersson, tommypet@kth.se
Helena Sjöberg, hsjob@kth.se
Effektiv implementation av hashtabeller
Sammanfattning
Denna rapport syftar till att undersöka effektiviten hos de två
hashningsmetoderna Cuckoohashning och den relativt nya Hopscotchhashning
jämfört med Javas inbyggda java.util.hashmap. För att utföra detta
implementerar vi två hashtabeller som använder sig av de respektive metoderna i
Java och mäter deras prestanda med hänsyn till snabbhet och minnesåtgång.
HashMap visar sig vara snabbare på enskilda operationer överlag, men våra
implementationer är snabbare i värsta fallet. De resultaten analyseras och diskuteras.
Vi diskuterar också hur de två hashtabellerna skulle kunna parallelliseras. I
slutet av rapporten bifogar vi våra implementationer i helhet.