Cuckoo hashing обеспечивает O(1) поиск в худшем случае — не амортизированно и не в среднем. У каждого ключа есть всего две возможные позиции в таблице, поэтому поиск просто проверяет оба места.

При вставке, если ячейка занята, новый ключ «выталкивает» старый на его альтернативную позицию — отсюда название, как у кукушки, которая выкидывает чужие яйца. Если возникает цикл, таблицу перестраивают с новыми хеш-функциями.

Алгоритм был предложен Rasmus Pagh и Flemming Rodler в 2001 году. Эта идея не просто теоретическая: Cuckoo hashing используется в таблице отслеживания соединений ядра Linux. Простой подход дает мощные гарантии на поиск.