Самая быстрая хэш функция javascript

Обновлено: 05.07.2024

Мне нужно преобразовать строки в некоторую форму хэша. Возможно ли это в JavaScript?

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

FNV-1a имеет лучшее распределение, чем DJB2, но медленнее
DJB2 быстрее, чем FNV-1a, но имеет тенденцию давать больше столкновений
MurmurHash3 лучше и быстрее, чем DJB2 и FNV-1a (но оптимизированная имплемтация требует больше строк кода, чем FNV и DJB2)

на основе принято отвечать в ES6. Меньше, ремонтопригоден и работает в современных браузерах.

Если это кому-то поможет, я объединил два верхних ответа в более старую версию браузера, которая использует быструю версию if reduce доступно и возвращается к решению esmiralha, если это не так.

использование как:

Это изысканный и более эффективный вариант:

это соответствует реализации Java стандарта object.hashCode()

вот также один, который возвращает только положительные хэш-коды:

и вот это для Java, который возвращает только положительные хэш-кодов:

наслаждайтесь!

Я немного удивлена, что никто не говорил о новом SubtleCrypto API еще.

чтобы получить хэш из строки, вы можете использовать subtle.digest способ :

быстрый и краткий, который был адаптирован из здесь:

мой быстрый (очень длинный) один лайнер на основе FNV Multiply+Xor способ:

Я объединил два решения (пользователи esmiralha и lordvlad), чтобы получить функцию, которая должна быть быстрее для браузеров, поддерживающих функцию js уменьшить() и все еще совместима со старыми браузерами:

пример:

Я пошел на простую конкатенацию кодов символов, преобразованных в шестнадцатеричные строки. Это служит относительно узкой цели, а именно просто нужно хэш-представление короткой строки (например, заголовки, теги) для обмена с серверной стороной, которая по не соответствующим причинам не может легко реализовать принятый порт Java хэш-кода. Очевидно, что здесь нет приложения безопасности.

Это может быть сделано более лаконичным и браузерным с подчеркиванием. Пример:

I предположим, что если вы хотите хэшировать большие строки аналогичным образом, вы можете просто уменьшить коды символов и шестнадцатерить полученную сумму, а не объединять отдельные символы вместе:

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

немного упрощенная версия ответа @esmiralha.

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

вот простой, хорошо распределенный 53-битный хэш. Это довольно быстро и имеет низкую скорость столкновения.

он достигает лавины (нестрогой), поэтому небольшие изменения имеют большие изменения в выходе, что делает его случайным:

53-бит является пределом целых чисел JS и имеет значительно меньшую вероятность столкновения, чем 32-битные хэши. Но если 53 бита недостаточно для вас, вы все равно можете использовать все 64 бита, построив шестнадцатеричную строку или массив:

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

С помощью этого решения мы можем указать набор символов, чтобы избежать некоторых проблем, когда значения хранятся или отправляются между слоями приложений, например: когда результирующая строка (хэш) производит процентное кодирование, и эта строка отправляется контроллеру с помощью метода GET из слоя представления.

Я немного опоздала на вечеринку, но вы можете использовать этот модуль: крипто:

результатом этой функции всегда является 64 строка символов; что-то вроде этого: "aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"

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

Больше полезной информации вы можете получить на наших телеграм-каналах «Библиотека программиста» и «Библиотека фронтендера».

Хеш-таблицы

Однако у ассоциативных массивов есть своя слабость – их нельзя положить в память компьютера как есть, в отличие от обычного индексированного массива. Для хранения ассоциативных массивов используется специальная структура – хеш-таблица (hash map).

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

Ассоциативные массивы – это в некотором смысле синтаксический сахар, более удобная надстройка над хеш-таблицей.

Принципиальная схема работы хеш-таблицы

Хеширование

Чтобы превратить ключ ассоциативного массива в индекс обычного, нужно проделать 2 операции:

Найти хеш (хешировать ключ);
Привести найденный хеш к индексу результирующего массива.

То есть конечная задача – преобразовать ключ в числовой индекс, но она обычно выполняется в два этапа.

Вычисление хеша

Хеш-функция получает входные данные и преобразует их в хеш – строку или число фиксированной длины. Вы точно слышали о некоторых алгоритмах хеширования: CRC32 , MD5 и SHA . Ключ при этом может быть представлен любым типом данных, с которым умеет работать хеш-функция.

Пример хеша – идентификатор коммита в git. Когда вы сохраняете изменения, они хешируются и получается что-то вроде 0481e0692e2501192d67d7da506c6e70ba41e913 . Это хеш, вычисленный для ваших изменений.

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

Если в качестве ключей выступают строки, можно вычислять сумму кодов всех символов:

Например, для ключа name хешем будет число 417, а для ключа age – число 301.

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

Важно: для одного и того же входного значения хеш-функция всегда возвращает одинаковый результат.

Приведение к индексу

Обычно размер результирующего массива определяется сразу, следовательно, индекс должен находиться в установленных пределах. Хеш обычно больше индекса, так что его нужно дополнительно преобразовать.

Для вычисления индекса можно использовать остаток от деления хеша на размер массива:

Важно помнить, что чем больше длина массива, тем больше места он занимает в памяти.

Воспользуемся нашей хеш-функцией и преобразуем ассоциативный массив в обычный:

Ключу name соответствует индекс 2, а ключу age – 1.

Мы храним в результирующем массиве не только значения, но и исходные ключи. Зачем это нужно, узнаем очень скоро.

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

Коллизии

Вы уже видите слабое место подобных преобразований?

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

Есть два распространенных варианта решения коллизий.

Открытая адресация

Предположим, что мы передали хеш-функции какой-то ключ ассоциативного массива ( key1 ) и получили от нее 2 – индекс обычного массива, который соответствует этому ключу.

Затем мы передаем ей другой ключ – key2 – и вновь получаем 2 – произошла коллизия. Мы не можем записать новые данные под тем же индексом, поэтому мы просто начинаем искать первое свободное место в массиве. Это называется линейное пробирование. Следующий после 2 индекс – 3 – свободен, записываем новые данные в него:

Для третьего ключа key3 хеш-функция возвращает индекс 3 – но он уже занят ключом key2 , поэтому нам приходится снова искать свободное место.

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

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

Метод цепочек

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

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

Такая реализация позволяет с легкостью удалять элементы из таблицы, ведь в связном списке операция удаления занимает константное время.

Реализация хеш-таблицы на JavaScript

Хеш-таблица должна реализовывать интерфейс ассоциативного массива, то есть предоставлять три основных метода:

добавление новой пары ключ-значение;
поиск значения по ключу;
удаление пары по ключу.

Чем меньше размер хеш-таблицы (длина массива), тем чаще будут происходить коллизии. Мы возьмем для примера небольшое число – 32. На практике для размера хеш-таблицы часто используются простые числа (которые делятся только на единицу и на себя). Считается, что при этом возникает меньше коллизий.

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

Эффективность основных операций в хеш-таблице

Основные операции в хеш-таблице состоят из двух этапов:

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

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

Эффективность хеш-таблицы зависит от трех основных факторов:

Хеш-функция, которая вычисляет индексы для ключей. В идеале она должна распределять индексы равномерно по массиву;
Размер самой таблицы – чем он больше, тем меньше коллизий;
Метод разрешения коллизий. Например, метод цепочек позволяет свести операцию добавления нового элемента к константному времени.

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

Использование хеш-таблиц

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

В JavaScript хеш-таблицы в чистом виде используются довольно редко. Обычно всю их работу успешно выполняют обычные объекты (ассоциативные массивы) или более сложные Map. При этом на более низком уровне(интерпретация программы) для представления объектов как раз используются хеш-таблицы.

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

Хеширование, кодирование и шифрование

Хеширование – это алгоритм, работающий только в одну сторону. Из хеша невозможно получить исходное значение – да и практической необходимости в этом нет, ведь главная задача хеширования – различать входные данные, а не сохранять их. Вы преобразуете исходный текст в какую-то другую последовательность символов с помощью шифра. Такая последовательность либо абсолютно нечитаема (просто набор букв), либо имеет совершенно другой смысл. Если кто-нибудь перехватит это письмо, то просто не поймет, что вы хотели сказать. Ваш друг знает, что послание зашифровано, и знает, как его расшифровать. Таким образом, главная цель шифрования – скрыть информацию от посторонних лиц. Для этого используется секретный ключ или даже два ключа – один для шифрования, второй для расшифровки.

Заключение

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

В последней статье цикла мы разберем еще несколько полезных прикладных алгоритмов для веб-разработки.

Мне нужно преобразовать строки в какую-то форму хэша. Это возможно в JavaScript?

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

@henrikstroem Зависит от того, что вы хэшируете; нет ничего плохого в использовании md5 для создания хэша в целях безопасности. @BradKoch Зависит от того, что вы делаете; нет ничего плохого в использовании md5 в целях безопасности. Конечно, есть лучшие методы для хеширования паролей, но md5 отлично подходит для таких вещей, как подпись URL. Я нахожу забавным то, что в то время как MD5 подвергается критике в комментариях здесь, почти все ответы рекомендуют гораздо худшие алгоритмы хеширования и получают много голосов. Использование MD5 для проверки того, что загрузка не была повреждена, не означает, что ваши пароли будут отправлены по электронной почте вашим паролям. Это тот же, который используется в Java. То hash << 5 - hash же самое, hash * 31 + char но намного быстрее. Это приятно, потому что это так быстро, а 31 - это простое число. Выиграй, выиграй там. @PeterAronZentai Почему это «непригодно»? Вывод, полученный с помощью кода на основе чисел, (hash * 31) + char идентичен выводу, сгенерированному кодом на основе сдвига ((hash<<5)-hash)+char , даже для очень длинных строк (я тестировал его со строками, содержащими более миллиона символов), поэтому он не является «непригодным» в терминах точности. Сложность составляет O (n) для версий на основе числа и на основе сдвига, поэтому она не является «непригодной» с точки зрения сложности. Кто-нибудь может прокомментировать уникальность (или нет) вывода? В частности, если я использую этот хэш только для строк с длиной меньше n , что является самым большим, n для которого я не могу иметь коллизию? Есть ли какая-то причина, по которой это должно (или должно) быть в прототипе String? Будет ли какой-нибудь менее эффективным / действенным просто иметь, например; var hashCode = function hashCode (str) ? А потом использовать как hashCode("mystring") ?

РЕДАКТИРОВАТЬ

ОРИГИНАЛ

Если кому-то интересно, вот улучшенная (более быстрая) версия, которая выйдет из строя на старых браузерах, в которых отсутствует reduce функция массива.

версия со стрелкой в одну строку:

Есть ли способ получить хеш, который является только положительным числом? Хороший парень @lordvlad, на самом деле проверяет свой ответ, а затем сообщает, когда он был медленнее. Я только что понял: вполне понятно, что принятый ответ быстрее, потому что моя версия должна сначала превратить строку в массив, выделить новую память и скопировать каждый символ .

Примечание: Даже с лучшим 32-битным кешем, столкновение будет рано или поздно произойдет.

Вероятность коллизии хеша может быть рассчитана как , приблизительно, как ( см. Здесь ). Это может быть выше, чем предполагает интуиция:
если принять 32-битный хэш и k = 10000 элементов, произойдет столкновение с вероятностью 1,2%. Для 77 163 выборок вероятность становится 50%! ( калькулятор ).
Я предлагаю обходной путь внизу.

В ответ на этот вопрос Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Ян Бойд опубликовал хороший углубленный анализ . Короче говоря (насколько я понимаю), он приходит к выводу, что Murmur лучше, а затем FNV-1a.
Алгоритм Java String.hashCode (), предложенный Эсмиралхой, кажется вариантом DJB2.

FNV-1a имеет лучшее распределение, чем DJB2, но медленнее
DJB2 быстрее, чем FNV-1a, но имеет тенденцию давать больше столкновений
MurmurHash3 лучше и быстрее, чем DJB2 и FNV-1a (но оптимизированная реализация требует больше строк кода, чем FNV и DJB2)

Если входные строки короткие и производительность важнее качества распространения, используйте DJB2 (как предложено в принятом ответе esmiralha).

Если качество и небольшой размер кода важнее скорости, я использую эту реализацию FNV-1a (на основе этого кода ).

Улучшить вероятность столкновения

Как объяснено здесь , мы можем расширить размер хеш-бита, используя этот трюк:

Используйте это с осторожностью и не ожидайте слишком многого все же.

Почему ты это делаешь ("0000000" + (hval >>> 0).toString(16)).substr(-8); ? Разве это не то же самое, что и (hval >>> 0).toString(16) ? это добавляет начальные 0, чтобы результирующий хеш всегда имел длину 8 символов. Легче читать и распознавать в выходных данных, но это мое личное мнение Ах, хорошо, я понял. Для маленьких hval , (hval >>> 0).toString(16) может быть менее 8 символов, поэтому вы дополняете его нулями. Я был просто сбит с толку, потому что (hval >>> 0).toString(16) всегда приводил к строке из 8 символов. Мне нравится этот ответ, потому что он создает намного лучше распределенный хеш: другие функции, предлагаемые здесь, будут иметь последующие значения хеша. Например, hash ("example1") - hash ("example2") == 1 ", тогда как этот гораздо более непредсказуем. В ответ на «FNV-1a имеет лучшее распределение, чем DJB2, но медленнее» - я думаю, следует сказать, что FNV1a может быть очень быстрым при реализации с использованием Math.imul функции ES6 . Это само по себе делает его высшим ориентиром и, в конечном счете, лучшим выбором, чем DJB2 в долгосрочной перспективе.

На основании принятого ответа в ES6. Меньше, удобнее в обслуживании и работает в современных браузерах.

РЕДАКТИРОВАТЬ (2019-11-04) :

версия со стрелкой в одну строку:

Спасибо за совместное использование, которое я добавил str += "" перед хэшированием, чтобы избежать исключения, str.split is not a function Я также только что заметил, что самое быстрое «ретро» решение на самом деле меньше, если вы уберете переводы строки так, что оно будет всего 3 строки. Есть ли способ, чтобы это дало только положительные, но все же уникальные результаты? @deekshith Принятый ответ используется hash |= 0 для преобразования в 32-битное целое число. Эта реализация не делает. Это ошибка?

С этим из пути, вот что лучше - cyrb53 , простой, но высококачественный 53-битный хеш. Он довольно быстрый, обеспечивает очень хорошее распределение хешей и имеет значительно более низкую частоту коллизий по сравнению с любыми 32-битными хешами.

Подобно хорошо известным алгоритмам MurmurHash / xxHash, он использует комбинацию умножения и Xorshift для генерации хэша, но не так тщательно. В результате это быстрее, чем в JavaScript, и значительно проще в реализации.

Достигается лавина (не строгая), что в основном означает, что небольшие изменения во входных данных имеют большие изменения в выходных данных, в результате чего результирующий хэш выглядит случайным:

Вы также можете предоставить начальное число для альтернативных потоков с одним и тем же входом:

Технически это 64-битный хэш (два некоррелированных 32-битных хэша параллельно), но JavaScript ограничен 53-битными целыми числами. При необходимости можно использовать полный 64-битный выход , изменив строку возврата для шестнадцатеричной строки или массива.

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

И просто для удовольствия, вот минимальный 32-битный хэш в 89 символов с более высоким качеством, чем даже FNV или DJB2:

Изучение

В компьютерном программировании структуры данных используются для организации данных и применения алгоритмов (или команд) к коду. Хорошее понимание структур данных и алгоритмов полезно для эффективного решения проблем и важно для взлома собеседований по кодированию.

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

Что такое хеш-таблица?

Хэш — таблица (часто называемый хэш — карта ) представляет собой структуру данных, которая отображает ключи на значения. Хеш-таблицы эффективно объединяют операции поиска, вставки и удаления. Ключ отправляется в хеш-функцию, которая выполняет над ним арифметические операции. Результат (называемый хеш-значением или хешем) — это индекс пары «ключ-значение».

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

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

Производительность хеш-таблицы зависит от трех фундаментальных факторов: хеш-функции, размера хеш-таблицы и метода обработки конфликтов.

Хеш-таблицы состоят из двух частей:

Объект: объект с таблицей, в которой хранятся данные. В массиве хранятся все записи «ключ-значение» в таблице. Размер массива должен быть установлен в соответствии с ожидаемым объемом данных.
Хеш-функция (или функция сопоставления): эта функция определяет индекс нашей пары ключ-значение. Это должна быть односторонняя функция и создавать разные хеш-коды для каждого ключа.

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

Использование хеш-таблиц

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

По временной сложности операция 0 (1)0 ( 1 ). В среднем поиск в хэш-таблице более эффективен, чем поиск в других структурах данных. Некоторые распространенные применения хеш-таблиц:

Индексирование базы данных
Кеши
Уникальное представление данных
Поиск в несортированном массиве
Поиск в отсортированном массиве с использованием двоичного поиска

Хеш-таблицы против деревьев

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

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

Хеш-таблицы могут работать в постоянное время, в то время как деревья обычно работают в O (журнал n)O ( l o g n ). В худшем случае производительность хеш-таблиц может быть нижеНа)О ( п ). Однако дерево AVL будет поддерживатьO (журнал n)O ( l o g n ) в худшем случае.

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

Что такое хеш-функция?

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

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

Общие хеш-функции

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

Арифметика Modular: При таком подходе мы берем модульным ключа с размером списка / массива: index=key MOD tableSize. Таким образом, indexвсегда будет оставаться между 0и tableSize — 1.

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

Сворачивание: этот подход включает в себя разделение ключа на небольшие части и применение другой арифметической стратегии к каждому фрагменту.

Коллизии хеш-таблиц

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

Конфликты хэша обычно обрабатываются с использованием четырех общих стратегий.

1. Линейное зондирование: при линейном зондировании пропускается уже заполненный индекс. Этого можно добиться, добавив значение смещения к уже вычисленному индексу. Если этот индекс также заполнен, добавьте его снова и так далее.

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

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

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

3. Изменение размера массива или списка: Еще один способ уменьшить коллизии — изменить размер списка или массива. Мы можем установить порог, и как только он будет превышен, мы можем создать новую таблицу, которая будет вдвое больше оригинальной. Все, что нам нужно сделать, это скопировать элементы из предыдущей таблицы.

Изменение размера списка или массива значительно снижает количество столкновений, но сама функция требует больших затрат. Следовательно, нам нужно быть осторожными с порогом, который мы устанавливаем. Типичным соглашением является установка порога на 0,6, что означает, что при заполнении 60% таблицы необходимо выполнить операцию изменения размера.

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

Читайте также: