More analysis of double hashing
George S. Lueker, Mariko Molodowitch · 1988
In [GS78] a deep and elegant analysis showed that double hashing was equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we give an analysis which extends this to load factors arbitrarily close to 1. We understand from [Ko86, Gu87] that Ajtai, Guibas, Komlós, and Szemerédi obtained this result in the first part of 1986; the analysis in this paper is of interest nonetheless because we demonstrate how a resampling technique can be used to obtain a remarkably simple proof.