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