Asymmetric Balanced Allocation with Simple Hash Functions

Philipp Woelfel

Abstract. We show that for the asymmetric sequential allocation scheme of Vöcking (1999) one can use very simple hash functions. The hash functions we use are a straight forward extension of the hash functions introduced by Dietzfelbinger and Woelfel in 2003. In order to evaluate a hash function a few arithmetic operations and table lookups suffice. Moreover, we show that the scheme has essentially the same behavior if the same balls are allowed to be inserted multiple times (i.e. they may be deleted and reinserted afterwards).


Notes