Asymmetric balanced allocation with simple hash functions
Philipp Woelfel · Symposium on Discrete Algorithms · 2006
We show that for the asymmetric sequential allocation scheme of Vocking (2003) one can use very simple hash functions. The hash functions we use are a straightforward extension of the hash functions introduced by Dietzfelbinger and Woelfel (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).