Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01202791 | Combinatorica |
Keywords | DocType | Volume |
68 Q 25, 68 P 10, 11 B 25 | Journal | 13 |
Issue | ISSN | ISBN |
1 | 1439-6912 | 0-89791-264-0 |
Citations | PageRank | References |
18 | 1.90 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| George S. Lueker | 1 | 1786 | 464.52 |
| Mariko Molodowitch | 2 | 18 | 1.90 |