Balanced allocation and dictionaries with tightly packed constant size bins

详细信息	查看全文 | 推荐本文 |

• 作者：Martin Dietzfelbinger ; Christoph Weidling
• 关键词：Randomized algorithms ; Data structures ; Dictionaries ; Hashing ; Random graphs ; Balanced allocation ; Storage space
• 刊名：Theoretical Computer Science
• 出版年：2007
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：21 June 2007
• 卷：380
• 期：1-2
• 页码：47-68
• 文件大小：815 K

摘要

We study a particular aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”): constant sized bins, packed as tightly as possible. Let d≥1 be fixed, and assume there are m bins of capacity d each. To each of n≤dm balls two possible bins are assigned at random. How close can dm/n=1+ε be to 1 so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? We show that ε>(2/e)^d−1 is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for ε>β^d, for some constant β<1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing [R. Pagh, F.F. Rodler, Cuckoo hashing, J. Algorithms 51 (2004) 122–144], we consider a hash table with m positions, each representing a bucket of capacity d≥1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h₁(x) or to bin h₂(x)? We obtain an implementation of a dictionary that accommodates n keys in m=(1+ε)n/d buckets of size d=O(log(1/ε)), so that key x resides in bucket h₁(x) or h₂(x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d≥1+3.26ln(1/ε), a static arrangement exists with high probability. If d≥16ln(1/ε), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/ε)^{O(loglog(1/ε))}.