Линейная сложность хеширования

Question

Я просматривал статью о линейном хешировании в Wiki. Одна строчка озадачила меня и вот она: «Стоимость расширения хеш-таблицы распределяется по каждой операции вставки хеш-таблицы, а не происходит сразу. [2]»

В случае линейного хеширования, если значение хэша вставляемого элемента меньше, чем переменная разбиения, то создается новый узел (или сегмент), и в него вставляется значение. И согласно вышеприведенной строке (сложность времени измеряется для каждого «операция вставки», которая по сравнению с реализацией «динамического массива», где мы выполняем амортизированный анализ, вставка в линейном хешировании должна занять O (n) времени. Пожалуйста, исправьте меня, если я ошибаюсь. Еще одна вещь: вторая строка в вики гласит: «Поэтому линейное хеширование хорошо подходит для интерактивных приложений».

Могу ли я сравнить дерево B + с линейным хешированием в «интерактивных случаях» (поскольку оба метода являются расширяемыми методами поиска)?

Answer 1

Реализация LH может гарантировать строго ограниченное время вставки. Нет смысла связывать местоположение разделения и местоположение ключевого хэша, если коллизии обрабатываются переполнением. Хитрость заключается в том, чтобы связать создание слотов переполнения с операцией разделения.

Например, если каждый N-й слот всегда зарезервирован для слота переполнения, вам нужно сделать не более N-1 разбиений, чтобы создать новый слот переполнения. На практике это меньше, чем (N-1) / 2 разбиений, потому что разделение одного слота может освободить слот переполнения.

http://goo.gl/6dbuH для описания, https://github.com/mischasan/hx для исходного кода.

Answer 2

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

Согласно википедии дерево b плюс имеет следующие временные сложности.

Для вставки записи требуется O (logbn) операций Поиск записи требует O (logbn) операций