Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins

We study an aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”). Assume there are n balls and m =(1+e) n /d bins of capacity d each, for a fixed d≥1. To each of the balls two possible bins are assigned at random. We show that e> (2/e)d−−1 is sufficient to guarantee that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing. Further, it takes constant time on average for changing the arrangement to accommodate a new ball, if e>γ·βd, for some constants γ>0, β 0, we obtain an implementation of a dynamic dictionary that accommodates n keys in m =(1+e)n /d buckets of size d = O(log(1/e)). For a lookup operation only two hash functions have to be evaluated and two contiguous segments of d memory cells have to be inspected. The expected time for inserting a new key is constant.