Хеш-таблица с цепочкой (удвоение таблицы)

  1. Как исправить хеш-таблицу с цепочкой, когда все элементы хешируются в одном слоте (один гигантский LinkedList)?
  2. Использует ли хеш-таблица с цепочкой удвоение таблицы? Если да, то когда лучше удвоить размер стола?

algorithm chaining data-structures hashtable
person Jack    schedule 02.10.2015    source источник
comment
1. Вы не можете предотвратить это, но вы можете сделать это недоступным для использования с помощью криптографической хеш-функции (siphash). 2. Хеш-таблицы с цепочкой обычно используют коэффициент загрузки 1, поэтому вы должны удвоить, когда хеш-таблица полностью заполнена.   -  person NikiC    schedule 02.10.2015

Ответы (2)


arrow_upward
2
arrow_downward

Расширяя ответ из комментариев NikiC:

Что касается вашего первого вопроса, это, к сожалению, реальная возможность при реализации связанной хеш-таблицы. Предполагая, что у вас есть хорошая хеш-функция - или, еще лучше, выбирая хеш-функцию, которая включает в себя некоторый элемент случайности - это крайне маловероятно. К сожалению, Плохие люди иногда используют это, чтобы отключить веб-серверы. Не так давно была разработана атака под названием «Hash DoS», при которой кто-то создавал кучу специализированных запросов к веб-серверу, что заставляло все сохраняться в одном слоте в связанной хеш-таблице, что приводило к огромной производительности. падает и в конечном итоге отключил некоторые веб-сайты. Однако хорошей новостью является то, что многие реализации языков программирования были обновлены, поэтому их хэш-таблицы не уязвимы для подобных вещей.

На ваш второй вопрос ответ - «это зависит от обстоятельств». В большинстве хороших реализаций связанных хэш-таблиц происходит повторное хеширование и рост, когда коэффициент загрузки становится слишком высоким (обычно коэффициенты загрузки от 1 до 2 являются общими). Однако некоторые реализации этого не делают. Например, реализация ConcurrentHashMap на Java, как мне кажется, не выполняет никакого перехеширования, потому что это невозможно, когда одновременно выполняется много операций чтения и записи.

person templatetypedef    schedule 02.10.2015

arrow_upward
1
arrow_downward

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

Например, если несколько значений хешируются в одну и ту же позицию в первой хеш-таблице, то размещение их в двоичном дереве в этой позиции позволит вам выполнять поиск / вставку среди них за время O (lg n), а не за O (n) время со связанным списком.

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

person stackoverflowuser2010    schedule 02.10.2015