Balanced allocation and dictionaries with tightly packed constant size bins
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 at each. To each of it   (21e)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 epsilon > beta(d), for some constant beta  = 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(1) (x) or to bin h(2) (x)? We obtain an implementation of a dictionary that accommodates it keys in in = (1 + epsilon)n/d buckets of size d = O (log(1/epsilon)), so that key x resides in bucket h(1) (x) or h(2) (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.26 center dot ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 center dot ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon) (O(log log(1/epsilon))). (C) 2007 Elsevier B. V. All rights reserved.
balanced allocation dictionaries hashing randomized algorithms data structures random graphs storage space