ПостCuckoo hashing даёт O(1) lookup в худшем случае

Cuckoo hashing даёт O(1) lookup в худшем случае Не амортизированно. Не «в среднем». А именно worst case. Идея красивая: у каждого ключа есть ровно две возможные позиции в таблице. Поэтому поиск тупо проверяет оба места и заканчивается. return table1[h1(key)] == key || table2[h2(key)] == key; Вставка работает интереснее: если место занято, новый ключ «выталкивает» старый в его альтернативную позицию. Отсюда и название: как кукушка, которая выкидывает чужие яйца из гнезда. Если начинается цикл, таблицу перестраивают с новыми хеш-функциями. Алгоритм предложили Rasmus Pagh и Flemming Rodler в 2001 году. И это не просто академическая штука: Linux kernel использует cuckoo hashing в connection tracking table. Один из тех случаев, когда простая идея даёт очень сильную гарантию по lookup.