Принцип хеш-таблицы

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

Независимо от языка процесс реализации HashMap можно разделить на три этапа:

Реализовать хэш-функцию
Разумное разрешение хеш-конфликтов
Реализуйте метод работы HASHMAP

Хеш-функции

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

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

Помимо самой хеш-функции, важной причиной, влияющей на возникновение хеш-коллизий (конфликтов), также является емкость базового массива. Очевидно, что в крайних случаях, если емкость массива равна 1, обязательно произойдет коллизия, а если емкость массива бесконечна, то вероятность коллизии очень мала. Таким образом, коллизия хешей также зависит от коэффициента загрузки. Коэффициент загрузки — это отношение количества хранимых пар "ключ-значение" к емкости массива. Например, емкость массива равна 100, а в данный момент хранится 90 пар "ключ-значение", а коэффициент загрузки равен 0,9. Коэффициент загрузки определяет, когда хеш-таблица будет расширяться. Если значение коэффициента загрузки слишком велико, это означает, что сохраненные пары "ключ-значение" близки к емкости, что увеличивает риск коллизии. Если значение слишком мало, это будет тратить место.

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

Несколько способов разрешения конфликтов

Существует четыре основных типа методов разрешения конфликтов:

Метод внешней молнии (обычно используется)
Открытый метод адресации (обычно используется)
Общая область перелива (не часто используется)
Метод Re-Hash (обычно не используется)

Метод внешней молнии

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

Синонимы: Два элемента получают один и тот же адрес индекса через хеш-функцию, и эти два элемента называются синонимами.

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

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

Основная идея состоит в том, чтобы при возникновении конфликта перейти непосредственно к следующему пустому адресу.Пока базовая таблица достаточно велика, пустой адрес всегда можно найти. Этот акт нахождения следующего адреса называется зондированием. ${hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}， i=1,2...k\,(k\leq m-1)$ `, гдеэто хэш-функция,длина хеш-таблицы, $d_{i}$ Приращение последовательности,количество конфликтов, которые произошли. Существуют различные методы обнаружения в соответствии с различными методами сбора инкрементной последовательности:

$d_{i}=1,2,3...(m-1)$ называется линейным зондированием, т. $d_{i}=i$ , или другие линейные функции. Это эквивалентно обнаружению таблицы адресов хранения по одному, пока не будет найден пустой блок, и хэш-адрес будет сохранен в пустом блоке.
$d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)$ Это называется квадратичным зондированием. Относительно линейное обнаружение, эквивалентное интервалу обнаружения при столкновении $d_{i}=i^{2}$ Пусто ли местонахождение блока, если оно пусто, сохраните в нем адрес.
$d_{i}=伪随机数序列$ , известное как псевдослучайное обнаружение.

На следующем рисунке показано линейное обнаружение:

общественная зона разлива

Основная идея — создать отдельную публичную область, куда будут помещаться конфликтующие пары ключ-значение. Он не используется повсеместно и не будет здесь подробно описываться.

Повторный хэш

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

Как реализовать хэш-таблицу

в основном:

insert
remove
get
contains_key
......и т.д......

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

Справочная документацияHash table

Обратите внимание на общедоступную учетную запись WeChat, продвигайте общие структуры данных, TCP/IP, распределенные технологии, внутреннюю разработку и другие технологии, чтобы делиться ими, учиться и развиваться вместе!