An empirical study on the performance of hash table
Dapeng Liu, Zengdi “Cindy” Cui, Shaochun Xu, Huafu Liu · 2014
Hash table is a valuable data structure that is expected to provide constant amortized access time. Although there are a lot of researches on hashing, it seems there is no enough practical study on its stability with large data set. In this paper, we conducted a few experiments to study the performance of hashing with a large set of data and compared the results of different collision approaches. Our experiments revealed a few new phenomena. The experiment results leans to close addressing than open addressing by a huge edge and deem linear probing impractical due to its low performance. When items are randomly distributed with keys in a large space, different hash algorithms might produce similar performance. Increasing randomness in keys does not help hash table performance either. These discoveries might be able to provide heuristics to programmers on how to design software products using hash tables.