Modelling performance impact of caches on hash table performance

Several recent papers have analysed the connection between the major characteristics of hashing algorithms (like probe length) and their performance. Their results indicate that, depending on the parameters of the experimental setup, the cache friendly behaviour of algorithms can have significant effect on the performance ranking of these algorithms. In this paper, we examine this effect through the comparison of hashing with simple linear probing and more complex collision avoidance mechanisms. A multi-parametric model will be presented, which links these previously mentioned experimental results. Among sophisticated collision avoidance algorithms, we will consider the linear double hashing and the quadratic quotient methods. A mathematical model will be presented for estimating probe lengths and number of cache misses of the different approaches. We will show how cache friendliness is related to probe lengths of the considered hashing algorithms and how it affects their performance. Our results will be supported by experiments, and previous results of other authors will be interpreted through our model.