Cuckoo hashing обеспечивает O(1) поиск в худшем случае — не амортизированно и не в сред...
Cuckoo hashing обеспечивает O(1) поиск в худшем случае — не амортизированно и не в среднем. У каждого ключа есть всего две возможные позиции в таблице, поэтому поиск просто проверяет оба места. При вставке, если ячейка занята, новый ключ «выталкивает» старый на его альтернативную позицию — отсюда название, как у кукушки, которая выкидывает чужие яйца. Если возникает цикл, таблицу перестраивают с новыми хеш-функциями. Алгоритм был предложен Rasmus Pagh и Flemming Rodler в 2001 году. Эта идея не просто теоретическая: Cuckoo hashing используется в таблице отслеживания соединений ядра Linux. Простой подход дает мощные гарантии на поиск.
3 850 просмотров
Канал в каталоге MAXimeter
12 972 подписчиков · IT и технологии