## Abstract

The power of two choices is a classic paradigm for load balancing when assigning m balls to n bins. When placing a ball, we pick two bins according to two hash functions h_{o} and h_{1}, and place the ball in the least loaded bin. Assuming fully random hash functions, when m = O(n), Azar et al. [STOC'94] proved that the maximum load is lglgn + 0(1) with high probability. No such bound was known with a hash function implementable in constant time. In this paper, we investigate the power of two choices when the hash functions h_{o} and h_{1} are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], PǍtraşcu and Thorup claimed that the expected maximum load with simple tabulation is O(lglgn). This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is O(lglgn) with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by lglgn + 0(l), or even (1 + o(l)) lglgn with high probability. Finally, we show that the expected maximum load is lglgn + 0(1), just like with fully random hashing.

Original language | English |
---|---|

Title of host publication | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |

Number of pages | 12 |

Volume | 3 |

Publisher | Association for Computing Machinery |

Publication date | 2016 |

Pages | 1631-1642 |

ISBN (Electronic) | 9781510819672 |

DOIs | |

Publication status | Published - 2016 |

Event | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States Duration: 10 Jan 2016 → 12 Jan 2016 |

### Conference

Conference | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |
---|---|

Country/Territory | United States |

City | Arlington |

Period | 10/01/2016 → 12/01/2016 |