Two-Way Chaining with Reassignment
Authors:
- Ketan DalalKDKetan Dalal
- Luc DevroyeLDLuc Devroye
- Ebrahim MalallaEMEbrahim Malalla
- Erin McLeishEMErin McLeish
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (2) , 327-340
Abstract
We present an algorithm for hashing $\lfloor \alpha n \rfloor$ elements into a table with n separate chains that requires O(1) deterministic worst-case insert time and O(1) expected worst-case search time for constant $\alpha$. We exploit the connection between two-way chaining and random graph theory in our techniques.
Keywords
This publication has 18 references indexed in Scilit:
- Cuckoo hashing: Further analysisInformation Processing Letters, 2003
- Randomized allocation processesRandom Structures & Algorithms, 2001
- The Probabilistic Method2000
- Contention Resolution in Hashing Based Shared Memory SimulationsSIAM Journal on Computing, 2000
- Balanced AllocationsSIAM Journal on Computing, 1999
- Dynamic Perfect Hashing: Upper and Lower BoundsSIAM Journal on Computing, 1994
- Deques with heap orderInformation Processing Letters, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- Some remarks on the theory of graphsBulletin of the American Mathematical Society, 1947