High load hash map searches: Hopscotch vs. Robin Hood

Sammanfattning

This thesis investigates the search time performance of the Robin Hood and Hopscotch hashing algorithms under high load factors. Prior analytical studies on time performance have shown Robin Hood to be highly effective, but a direct comparison with Hopscotch which is an algorithm composed of several well performing techniques has not been conducted. This work addresses that gap by evaluating search operations across high load factors ranging from 70% to 95%, with unsuccessful search ratios varying from 0% to 100%. Experimental results that are measured in nanoseconds indicate that Robin Hood consistently outperforms Hopscotch, particularly at almost full load factors and with greater proportions of unsuccessful searches. While Hopscotch maintains competitive performance at a load factor of 70-75% with primarily successful searches, its efficiency deteriorates significantly under stress from a weak hash function, which is found to be due to implementation challenges such as neighborhood overflow. The findings suggest Robin Hood as the more robust choice for high-load, read heavy (WORM-type), potentially collision rich workloads.