The Power of Two-Choice Linear Probing
There is a surprisingly strong ``power of two choices''phenomenon for linear-probing hash tables, allowing for a two-choice hash table to achieve significantly better bounds than what might at first seem to be possible.