Каковы преимущества хеширования кукушки перед динамическим хэшированием?

12

Динамические совершенные хеш-таблицы и кукуш-хеш-таблицы - это две разные структуры данных, которые поддерживают O (1) поиск в худшем случае и ожидаемые O (1) вставки и удаления во время. Оба требуют O (n) вспомогательного пространства и доступа к семействам хеш-функций для своих операций.

Я думаю, что обе эти структуры данных сами по себе прекрасны и великолепны, но я не уверен, что вижу, как и когда одна из них будет предпочтительнее другой.

Существуют ли конкретные ситуации, в которых одна из этих структур данных имеет явное преимущество перед другой? Или они в основном взаимозаменяемы?

data-structures hash-tables templatetypedef
источник
Я не уверен, действительно ли какой-либо из этих методов используется на практике. Обычно такие типы структур данных, которые предлагают наилучшие асимптотические границы, в основном представляют интерес для исследований, поскольку они обычно имеют большую константу, скрытую в нотации. На практике вы можете предпочесть более простую и понятную технику O ( log n ) с действительно маленькой константой, а не более сложной O ( 1 ) с действительно большой константой. OO(log⁡n)O(1)
Том ван дер Занден
@TomvanderZanden Это определенно правда. Меня также интересуют теоретические преимущества одного подхода перед другим - есть ли какие-то хорошие теоретические свойства, которые каждый подход может предложить по сравнению с другим?
templatetypedef
@templatetypedef, тогда я призываю вас добавить это к вопросу. Люди не должны читать комментарии, чтобы понять ваш вопрос - комментарии временны и могут исчезнуть в любое время.
DW
Да, эти методы на самом деле используются на практике, обычно в нишевых областях.
псевдоним
1
Одно из преимуществ хеширования кукушки заключается в том, что его легко понять и реализовать. Кроме того, имхо, анализировать намного проще, чем динамическое идеальное хеширование.
А.Шульц

Ответы:

3

Динамическое совершенное хеширование в смысле Dietzfelbinger et al. нужно только 2-х независимое хеширование . В то время как есть некоторые результаты по простому хешированию для хеш-таблиц с кукушкой, такие как хеширование по искривленным таблицам и «Достаточное количество явных и эффективных хеш-семейств для хеширования с кукушкой с помощью тайника», оригинальное динамическое идеальное хеширование в некотором смысле более надежно.

jbapple
источник
См. Поясняющий комментарий от OP: «Меня также интересуют теоретические преимущества одного подхода над другим - есть ли какие-то хорошие теоретические свойства, которые каждый подход может предложить по сравнению с другим?»
Jbapple
3

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

jbapple
источник
1

Относительно легко увеличить эффективность использования хеша с кукушкой, позволяя каждому слоту хранить более одного предмета. Для слотов размера 4 эффективность пространства составляет около 95%. То есть предметы можно вставлять до тех пор, пока 95% пространства в таблице не будет использовано для хранения предметов, а не только в местах, где предметы могут находиться.

С другой стороны, границы в Dietzfelbinger et al. бумага о динамическом совершенном хешировании только доказывает, что операции вставки могут продолжаться до тех пор, пока таблица заполнена не более чем на 3%.

jbapple
источник
Возможно, вы захотите объединить ваши два ответа вместе. :-)
templatetypedef