Efficient hashing with lookups in two memory accesses

ABSTRACT

The study of hashing is closely related to the analysis of balls and bins. Azar et. al. [1] showed that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. This leads to the concept of two-way hashing where the largest bucket contains O(log log n) balls with high probability. The hash look up will now search in both the buckets an item hashes to. Since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. Using this fact, we present a simple, practical hashing scheme that maintains a maximum load of 2, with high probability, while achieving high memory utilization. In fact, with n buckets, even if the space for two items are pre-allocated per bucket, as may be desirable in hardware implementations, more than n items can be stored giving a high memory utilization. Assuming truly random hash functions, we prove the following properties for our hashing scheme.• Each lookup takes two random memory accesses, and reads at most two items per access.• Each insert takes O(log n) time and up to log log n+O(1) moves, with high probability, and constant time in expectation.• Maintains 83.75% memory utilization, without requiring dynamic allocation during inserts.We also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. By performing at most h moves, we can maintain a maximum load of O(log log n/h log (log log n/h)). So, even by performing one move, we achieve a better bound than by performing no moves at all.

REFERENCES

• 1: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
• 2: Micah Adler , Soumen Chakrabarti , Michael Mitzenmacher , Lars Rasmussen, Parallel randomized load balancing, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.238-247, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225131]
• 3: A. Broder and M. Mitzenmacher Using Multiple Hash Functions to Improve IP Lookups Proceedings of IEEE INFOCOM 2001, pp. 1454--1463, 2001.
• 4: Richard Cole , Alan M. Frieze , Bruce M. Maggs , Michael Mitzenmacher , Andréa W. Richa , Ramesh K. Sitaraman , Eli Upfal, On Balls and Bins with Deletions, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.145-158, October 08-10, 1998
• 5: Artur Czumaj , Friedhelm Meyer auf der Heide , Volker Stemann, Shared Memory Simulations with Triple-Logarithmic Delay, Proceedings of the Third Annual European Symposium on Algorithms, p.46-59, September 25-27, 1995
• 6: Artur Czumaj , Volker Stemann, Randomized Allocation Processes, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.194, October 19-22, 1997
• 7: A. Czumaj, C. Riley, and C. Scheideler. Perfectly Balanced Allocation In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'03), pages 240--251.
• 8: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 9: Luc Devroye , Pat Morin, Cuckoo hashing: further analysis, Information Processing Letters, v.86 n.4, p.215-219, 31 May 2003 [doi>10.1016/S0020-0190(02)00500-8]
• 10: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, A New Universal Class of Hash Functions and Dynamic Hashing in Real Time, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.6-19, July 16-20, 1990
• 11: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 12: Martin Dietzfelbinger , Philipp Woelfel, Almost random graphs with simple hash functions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780634]
• 13: Martin Dietzfelbinger and Christoph Weidling. Cache-friendly dictionary implementations with constant lookup time and small space overhead. Submitted to STACS 2005. Also part of Christoph Weidling's PhD thesis, to be published, Technical University of Ilmenau.
• 14: Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993--3002.
• 15: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 16: Dimitris Fotakis , Rasmus Pagh , Peter Sanders , Paul G. Spirakis, Space Efficient Hash Tables with Worst Case Constant Access Time, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.271-282, February 27-March 01, 2003
• 17: M. Mitzenmacher, A. Richa, and R. Sitaraman The Power of Two Random Choices: A Survey of Techniques and Results Book chapter, in Handbook of Randomized Computing: volume 1, edited by P. Pardalos, S. Rajasekaran, and J. Rolim, pp. 255--312.
• 18: Friedhelm Meyer auf der Heide , Christian Scheideler , Volker Stemann, Exploiting storage redundancy to speed up randomized shared memory simulations, Theoretical Computer Science, v.162 n.2, p.245-281, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00032-1]
• 19: Anna Ostlin , Rasmus Pagh, Uniform hashing in constant time and linear space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780633]
• 20: Rasmus Pagh , Flemming Friche Rodler, Cuckoo Hashing, Proceedings of the 9th Annual European Symposium on Algorithms, p.121-133, August 28-31, 2001
• 21: Boris Pittel , Joel Spencer , Nicholas Wormald, Sudden emergence of a giant k-core in a random graph, Journal of Combinatorial Theory Series B, v.67 n.1, p.111-151, May 1996 [doi>10.1006/jctb.1996.0036]
• 22: Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States