Хеш-таблица

Не путать со списком хешей или деревом хэшей .

«Перефраз» перенаправляется сюда. Чтобы узнать об эпизоде ​​Южного парка , см. Рехаш (Южный парк) .

Хеш-таблица
Тип	Неупорядоченный ассоциативный массив
Изобретенный	1953
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск Я(1) На ​ ) Вставлять Я(1) На ​ ) Удалить Я(1) На ​ ) Пространственная сложность Космос Θ( п ) На ​ )

Небольшая телефонная книга в виде хеш-таблицы

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

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

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

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

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

История

Идея хеширования возникла независимо в разных местах. В январе 1953 года Ханс Петер Лун написал внутренний меморандум IBM , в котором использовалось хеширование с цепочкой. Первый пример открытой адресации был предложен А.Д. Линем на основе меморандума Луна. Примерно в то же время Джин Амдал , Элейн М. МакГроу , Натаниэль Рочестер и Артур Сэмюэл из IBM Research реализовали хеширование для IBM 701 ассемблера . Открытую адресацию с линейным зондированием приписывают Амдалу, хотя Андрей Ершов . ту же идею выдвинул независимо Термин «открытая адресация» был придуман У. Уэсли Петерсоном в его статье, в которой обсуждается проблема поиска в больших файлах.

Первая опубликованная работа по хешированию с цепочкой принадлежит Арнольду Дюми , который обсуждал идею использования остатка по модулю простого числа в качестве хэш-функции. Слово «хеширование» впервые было опубликовано в статье Роберта Морриса. Теоретический анализ линейного зондирования первоначально был представлен Конхеймом и Вайсом.

Обзор

Ассоциативный массив хранит набор пар (ключ, значение) и допускает вставку, удаление и поиск (поиск) с ограничением уникальных ключей . В реализации ассоциативных массивов в виде хэш-таблицы массив $A$ длины $m$ частично заполнен $n$ элементы, где $m\geq n$. Ценность $x$ сохраняется в индексном месте $A[h(x)]$, где $h$ является хеш-функцией, и $h(x)<m$. При разумных предположениях хеш-таблицы имеют лучшие ограничения по временной сложности операций поиска, удаления и вставки по сравнению с самобалансирующимися двоичными деревьями поиска .

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

Коэффициент загрузки

Коэффициент нагрузки $\alpha$ является критической статистикой хеш-таблицы и определяется следующим образом:

$${\text{load factor}}\ (\alpha )={\frac {n}{m}},$$

где

• $n$ — количество записей, занятых в хеш-таблице.
• $m$ это количество ведер.

Производительность хеш-таблицы ухудшается в зависимости от коэффициента загрузки. $\alpha$.

Программное обеспечение обычно гарантирует, что коэффициент загрузки $\alpha$ остается ниже определенной константы, $\alpha _{\max }$. Это помогает поддерживать хорошую производительность. Поэтому общий подход заключается в изменении размера или «перехешировании» хеш-таблицы всякий раз, когда коэффициент загрузки $\alpha$ достигает $\alpha _{\max }$. Аналогичным образом можно изменить размер таблицы, если коэффициент загрузки упадет ниже $\alpha _{\max }/4$.

Коэффициент нагрузки для отдельной цепочки

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

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

При раздельной цепочке значение $\alpha _{\max }$ который обеспечивает наилучшую производительность, обычно находится в диапазоне от 1 до 3.

Коэффициент загрузки для открытой адресации

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

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

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

При открытой адресации приемлемые показатели максимального коэффициента загрузки. $\alpha _{\max }$ должно находиться в пределах от 0,6 до 0,75.

Хэш-функция

Хэш -функция $h:U\rightarrow \{0,...,m-1\}$ отображает вселенную $U$ ключей к индексам или слотам внутри таблицы, то есть $h(x)\in {0,...,m-1}$ для $x\in U$. Обычные реализации хэш-функций основаны на предположении целочисленной вселенной , что все элементы таблицы происходят из юниверса. $U=\{0,...,u-1\}$, где длина битовая $u$ ограничен размером слова компьютерной архитектуры .

Хэш-функция $h$ говорят, что он идеален для данного набора $S$ оно инъективно если $S$, то есть если каждый элемент $x\in S$ отображает другое значение в ${0,...,m-1}$. Идеальную хэш-функцию можно создать, если все ключи известны заранее.

Предположение о целочисленной вселенной

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

Хеширование по делению

Схема хеширования делением следующая:

$$h(x)\ =\ x\,{\bmod {\,}}m$$

Где $M$ это хеш-дайджест $x\in S$ и $m$ это размер стола.

Хеширование путем умножения

Схема хеширования умножением следующая:

$$h(x)=\lfloor m{\bigl (}(MA){\bmod {1}}{\bigr )}\rfloor$$

Где $A$ является вещественной константой и $m$это размер стола. Преимущество хеширования путем умножения состоит в том, что $m$ не критично. Хотя любое значение $A$ производит хэш-функцию, Дональд Кнут предлагает использовать золотое сечение .

Выбор хеш-функции

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

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

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

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

Разрешение столкновений

См. также: хеширование с двумя вариантами

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

Отдельная цепочка

Коллизия хэшей разрешена путем отдельной цепочки

Коллизия хэшей путем отдельной цепочки с головными записями в массиве сегментов.

При раздельной цепочке процесс включает в себя создание связанного списка с парой ключ-значение для каждого индекса массива поиска. Конфликтующие элементы объединяются в единый связанный список, по которому можно получить доступ к элементу с помощью уникального ключа поиска. Разрешение коллизий посредством связывания со связанным списком — распространенный метод реализации хеш-таблиц. Позволять $T$ и $x$ быть хеш-таблицей и узлом соответственно, операция включает в себя следующее:

Цепная хеш-вставка(  T  ,  k  ) 
    вставьте   x   в начало связанного списка   T  [  h  (  k  )] 

  Поиск по цепочке хэшей(  T  ,  k  ) 
    найти элемент с ключом   k   в связанном списке   T  [  h  (  k  )] 

  Связанное хэш-удаление(  T  ,  k  ) 
    удалить   x   из связанного списка   T  [  h  (  k  )] 
 

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

Другие структуры данных для отдельной цепочки

Если ключи упорядочены , было бы эффективно использовать концепции « самоорганизации », такие как использование самобалансирующегося бинарного дерева поиска , с помощью которого теоретический худший случай можно свести к $O(\log {n})$, хотя это и вносит дополнительные сложности.

В динамическом идеальном хешировании используются двухуровневые хеш-таблицы, чтобы уменьшить сложность поиска и гарантировать гарантированное получение результата. $O(1)$в худшем случае. В этой технике ведра $k$ записи организованы как идеальные хэш-таблицы с $k^{2}$ слоты, обеспечивающие постоянное время поиска в худшем случае и малое амортизируемое время для вставки. Исследование показывает, что раздельная цепочка на основе массива на 97% более производительна по сравнению со стандартным методом связанного списка при большой нагрузке.

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

Кэширование и локальность ссылки

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

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

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

Основная статья: Открытая адресация

Коллизия хешей разрешена путем открытой адресации с линейным зондированием (интервал = 1). Обратите внимание, что «Тед Бейкер» имеет уникальный хеш, но тем не менее столкнулся с «Сандрой Ди», которая ранее сталкивалась с «Джоном Смитом».

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

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

Хорошо известные последовательности зондов включают:

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

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

Кэширование и локальность ссылки

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

Другие методы разрешения коллизий, основанные

Объединенное хеширование

Основная статья: Объединенное хеширование

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

Хеширование с кукушкой

Основная статья: Хеширование с кукушкой

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

Хопскотч-хеширование

Основная статья: Хопскотч-хеширование

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

Каждый сегмент в хэш-таблице включает дополнительную «информацию о переходе» — H -бит битовый массив для указания относительного расстояния до элемента, который изначально был хеширован в текущем виртуальном сегменте в пределах H -1. записей Позволять $k$ и $Bk$быть ключом, который нужно вставить, и сегментом, в который хешируется ключ соответственно; В процедуре вставки задействовано несколько случаев, так что свойство соседства алгоритма гарантировано: если $Bk$пуст, элемент вставлен, а самый левый бит растрового изображения установлен в 1; если он не пуст, для поиска пустого слота в таблице используется линейное зондирование, растровое изображение сегмента обновляется с последующей вставкой; если пустой слот не находится в пределах диапазона окрестности , т.е. H -1, последующая манипуляция массивом битов обмена и информации о переходе для каждого сегмента выполняется в соответствии с его инвариантными свойствами окрестности .

Робин Гуд хэширует

Хеширование Робин Гуда — это алгоритм разрешения коллизий на основе открытой адресации; коллизии разрешаются за счет смещения самого дальнего элемента (или самой длинной пробной последовательности (PSL)) от его «исходного местоположения», т. е. корзины, в которую элемент был хеширован. Хотя хеширование Робин Гуда не меняет теоретическую стоимость поиска , оно существенно влияет на элементов по дисперсию распределения корзинам. т.е. речь идет о формировании кластера в хеш-таблице. Каждый узел в хеш-таблице, использующий хеширование Робин Гуда, должен быть дополнен для хранения дополнительного значения PSL. Позволять $x$ быть ключом для вставки, $x.psl$ быть (дополнительной) длиной PSL $x$, $T$ быть хеш-таблицей и $j$ быть индексом, процедура вставки следующая:

• Если $x.psl\ \leq \ T[j].psl$: итерация переходит к следующему сегменту без попытки внешнего зондирования.
• Если $x.psl\ >\ T[j].psl$: вставить элемент $x$ в ведро $j$; менять $x$ с $T[j]$-будь как будет $x'$; продолжить исследование с $j+1$ведро для вставки $x'$; повторяйте процедуру, пока каждый элемент не будет вставлен.

Динамическое изменение размера

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

Изменение размера путем перемещения всех записей

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

Альтернативы перефразированию «все сразу»

Некоторые реализации хэш-таблиц, особенно в системах реального времени , не могут заплатить цену за увеличение хеш-таблицы сразу, поскольку это может прервать критичные по времени операции. Если невозможно избежать динамического изменения размера, решение состоит в том, чтобы выполнять изменение размера постепенно, чтобы избежать провалов в памяти (обычно на 50 % от размера новой таблицы) во время перехеширования и во избежание фрагментации памяти , которая вызывает уплотнение кучи из-за освобождения больших блоков памяти , вызванных старая хэш-таблица. В таком случае операция повторного хеширования выполняется постепенно путем расширения предыдущего блока памяти, выделенного для старой хеш-таблицы, так что сегменты хеш-таблицы остаются неизменными. Общий подход к амортизированному перефразированию предполагает сохранение двух хэш-функций. $h_{\text{old}}$ и $h_{\text{new}}$. Процесс повторного хэширования элементов корзины в соответствии с новой хэш-функцией называется очисткой и реализуется с помощью шаблона команды путем инкапсуляции таких операций, как $\mathrm {Add} (\mathrm {key} )$, $\mathrm {Get} (\mathrm {key} )$ и $\mathrm {Delete} (\mathrm {key} )$ через $\mathrm {Lookup} (\mathrm {key} ,{\text{command}})$ обертку , в которой каждый элемент в корзине перехешируется, а его процедура выглядит следующим образом:

• Чистый $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ ведро.
• Чистый $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ ведро.
• Команда выполняется .

Линейное хеширование

Основная статья: Линейное хеширование

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

Производительность

Производительность хеш-таблицы зависит от способности хеш-функции генерировать квазислучайные числа ( $\sigma$) для записей в хэш-таблице, где $K$, $n$ и $h(x)$ обозначает ключ, количество сегментов и хэш-функцию такие, что $\sigma \ =\ h(K)\ \%\ n$. Если хэш-функция генерирует то же самое $\sigma$ для разных ключей ( $K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$), это приводит к столкновению , которое решается различными способами. Постоянная временная сложность ( $O(1)$) операции в хеш-таблице предполагается при условии, что хеш-функция не генерирует конфликтующих индексов; таким образом, производительность хеш-таблицы прямо пропорциональна способности выбранной хеш-функции распределять индексы . Однако построение такой хеш-функции практически невозможно , поэтому реализация зависит от в конкретных случаях методов разрешения коллизий для достижения более высокой производительности.

Приложения

Ассоциативные массивы

Основная статья: Ассоциативный массив

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

Индексация базы данных

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

Тайники

Основная статья: Кэш (вычисления)

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

Наборы

Основная статья: Установить структуру данных

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

Таблица транспонирования

Основная статья: Таблица транспонирования

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

Реализации

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

В JavaScript «объект» — это изменяемая коллекция пар ключ-значение (называемых «свойствами»), где каждый ключ представляет собой либо строку, либо гарантированно уникальный «символ»; любое другое значение, используемое в качестве ключа, сначала преобразуется в строку. За исключением семи «примитивных» типов данных, каждое значение в JavaScript является объектом. ECMAScript 2015 также добавил Map структура данных, которая принимает произвольные значения в качестве ключей.

С++ 11 включает в себя unordered_map в своей стандартной библиотеке для хранения ключей и значений произвольных типов .

Go встроен map реализует хеш-таблицу в виде типа .

Java включает в себя Язык программирования HashSet, HashMap, LinkedHashSet, и LinkedHashMap универсальные коллекции.

Python Встроенный dict реализует хеш-таблицу в виде типа .

Ruby встроенный в Hash использует модель открытой адресации, начиная с Ruby 2.4.

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

включает Стандартная библиотека .NET в себя HashSet и Dictionary, поэтому его можно использовать из таких языков, как C# и VB.NET .

См. также

• Фильтр Блума
• Согласованное хеширование
• Распределенная хеш-таблица
• Расширяемое хеширование
• Дерево, отображаемое хеш-массивом
• Ленивое удаление
• Пирсоновское хеширование
• ФотоДНК
• Алгоритм поиска строки Рабина – Карпа
• Структура данных поиска
• Стабильное хеширование
• Краткая хеш-таблица

Дальнейшее чтение

• Тамассия, Роберто; Гудрич, Майкл Т. (2006). «Глава девятая: Карты и словари». Структуры данных и алгоритмы в Java: [обновлено для Java 5.0] (4-е изд.). Хобокен, Нью-Джерси: Уайли. стр. 369–418 . ISBN  978-0-471-73884-8 .
• Маккензи, Би Джей; Харрис, Р.; Белл, Т. (февраль 1990 г.). «Выбор алгоритма хеширования». Программное обеспечение: практика и опыт . 20 (2): 209–224. дои : 10.1002/спе.4380200207 . hdl : 10092/9691 . S2CID   12854386 .

Внешние ссылки

• Запись NIST о хэш-таблицах
• Структуры открытых данных – Глава 5 – Хэш-таблицы , Пэт Морин
• Введение в алгоритмы MIT: хеширование 1 видео лекции MIT OCW
• Введение в алгоритмы MIT: хеширование 2 Видео лекции MIT OCW