Хеш-таблица

Ассоциативный массив для хранения пар ключ-значение

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

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

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

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

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

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

История

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

Первая опубликованная работа по хешированию с цепочкой принадлежит Арнольду Дюми , который обсуждал идею использования остатка по модулю простого числа в качестве хеш-функции. ^{[7] : 15} Слово «хеширование» впервые было опубликовано в статье Роберта Морриса. ^{[8] : 126} Теоретический анализ линейного зондирования первоначально был представлен Конхеймом и Вайсом. ^{[7] : 15}

Обзор

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

Хэш-таблицы также часто используются для реализации наборов, опуская сохраненное значение для каждого ключа и просто отслеживая, присутствует ли ключ. ^{[7] : 1}

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

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

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

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

Производительность хеш-таблицы ухудшается в зависимости от коэффициента загрузки . ^{[7] : 2} ${\displaystyle \alpha }$

Для поддержания хорошей производительности программное обеспечение следит за тем, чтобы коэффициент загрузки никогда не превышал некоторой константы . ^[9] ${\displaystyle \alpha }$ ${\displaystyle \alpha _{\max }}$

Поэтому размер хеш-таблицы изменяется или перехешируется всякий раз, когда коэффициент загрузки достигает . ^[9] ${\displaystyle \alpha }$ ${\displaystyle \alpha _{\max }}$

Размер таблицы также изменяется, если коэффициент загрузки падает ниже . ^[9] ${\displaystyle \alpha _{\max }/4}$

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

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

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

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

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

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

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

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

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

Хэш-функция

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

Идеальная хэш-функция определяется как инъективная функция , в которой каждый элемент сопоставляется с уникальным значением в . ^{[13] [14]} Идеальную хэш-функцию можно создать, если все ключи известны заранее. ^[13] ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle {0,...,m-1}}$

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

Схемы хеширования, используемые в предположении целочисленной вселенной, включают хеширование делением, хеширование умножением, универсальное хеширование , динамическое идеальное хеширование и статическое идеальное хеширование . ^{[7] : 2} Однако широко используемой схемой является хеширование делением. ^{[15] : 264  [12] : 110}

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

Схема хеширования делением следующая: ^{[7] : 2}

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

${\displaystyle M}$ ${\displaystyle x\in S}$ ${\displaystyle m}$

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

Схема хеширования умножением следующая: ^{[7] : 2–3.}

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

действительная константа^{[7] : 2–3}Дональд Кнутзолотое сечение^{[7] : 3} ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle A}$

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

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

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

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

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

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

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

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

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

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

При раздельной цепочке процесс включает в себя создание связанного списка с парой ключ-значение для каждого индекса массива поиска. Конфликтующие элементы объединяются в единый связанный список, по которому можно получить доступ к элементу с помощью уникального ключа поиска. ^{[6] : 464} Разрешение коллизий посредством связывания со связанным списком — распространенный метод реализации хеш-таблиц. Пусть и — хеш-таблица и узел соответственно, операция включает в себя следующее: ^{[15] : 258} ${\displaystyle T}$ ${\displaystyle x}$

Chained-Hash-Insert( T , k ) вставляет  x  в начало связанного списка  T [ h ( k )]Chained-Hash-Search( T , k ) поиск элемента с ключом  k  в связанном списке  T [ h ( k )]Chained-Hash-Delete( T , k ) удалить  x  из связанного списка  T [ h ( k )]

Если элемент сопоставим численно или лексически и вставлен в список с сохранением общего порядка , это приводит к более быстрому прекращению безуспешных поисков. ^{[20] : 520–521.}

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

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

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

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

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

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

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

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

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

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

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

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

• Линейное зондирование , при котором интервал между зондами фиксирован (обычно 1). ^[28]
• Квадратичное зондирование , при котором интервал между зондированием увеличивается путем добавления последовательных выходных данных квадратичного полинома к значению, полученному в результате исходного вычисления хеш-функции. ^{[29] : 272}
• Двойное хеширование , при котором интервал между проверками вычисляется с помощью вторичной хеш-функции. ^{[29] : 272–273.}

Производительность открытой адресации может быть медленнее по сравнению с раздельной цепочкой, поскольку последовательность проверки увеличивается, когда коэффициент нагрузки приближается к 1. ^{[9] [22] : 93} Зондирование приводит к бесконечному циклу , если коэффициент загрузки достигает 1, в случае полностью заполненный стол. ^{[6] : 471} Средняя стоимость линейного зондирования зависит от способности хэш-функции равномерно распределять элементы по таблице, чтобы избежать кластеризации , поскольку формирование кластеров приведет к увеличению времени поиска. ^{[6] : 472} ${\displaystyle \alpha }$

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

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

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

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

Объединенное хеширование — это гибрид отдельной цепочки и открытой адресации, при которой сегменты или узлы связаны внутри таблицы. ^{[30] : 6–8} Алгоритм идеально подходит для фиксированного выделения памяти . ^{[30] : 4} Коллизия при объединенном хешировании разрешается путем идентификации пустого слота с наибольшим индексом в хеш-таблице, затем в этот слот вставляется конфликтующее значение. Бакет также связан со слотом вставленного узла, который содержит его конфликтующий хеш-адрес. ^{[30] : 8}

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

Хеширование с кукушкой — это форма метода разрешения коллизий открытой адресации, которая гарантирует сложность поиска в наихудшем случае и постоянное амортизированное время для вставок. Конфликт разрешается путем поддержки двух хеш-таблиц, каждая из которых имеет свою собственную хеш-функцию, при этом конфликтующий слот заменяется заданным элементом, а занятый элемент слота перемещается в другую хеш-таблицу. Процесс продолжается до тех пор, пока каждый ключ не займет свое место в пустых ячейках таблиц; если процедура входит в бесконечный цикл , который определяется посредством поддержания счетчика порогового цикла, обе хеш-таблицы перехэшируются с использованием новых хэш-функций, и процедура продолжается. ^{[31] : 124–125} ${\displaystyle O(1)}$

Классическое хеширование

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

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

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

Хеширование Робин Гуда — это алгоритм разрешения коллизий на основе открытой адресации; коллизии разрешаются за счет смещения самого дальнего элемента (или самой длинной пробной последовательности (PSL)) от его «исходного местоположения», т. е. корзины, в которую элемент был хеширован. ^{[33] : 12} Хотя хеширование Робин Гуда не меняет теоретическую стоимость поиска , оно существенно влияет на дисперсию распределения элементов по корзинам, ^[34] : ² т.е. имеет дело с формированием кластеров в хеш-таблице. ^[35] Каждый узел в хеш-таблице, использующий хеширование Робин Гуда, должен быть дополнен для хранения дополнительного значения PSL. ^[36] Пусть — вставляемый ключ, — (инкрементная) длина PSL , — хеш-таблица, а — индекс, процедура вставки следующая: ^{[33] : 12–13  [37] : 5} ${\displaystyle x}$ ${\displaystyle x.psl}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle j}$

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

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

Повторные вставки приводят к увеличению количества записей в хеш-таблице, что, следовательно, увеличивает коэффициент загрузки; Чтобы сохранить амортизированную производительность операций поиска и вставки, размер хеш-таблицы динамически изменяется, а элементы таблиц повторно хэшируются в сегменты новой хеш-таблицы, ^[9] поскольку элементы не могут быть скопированы в результате изменения размеров таблицы. в другом значении хеш-функции из-за операции по модулю . ^[38] Если хеш-таблица становится «слишком пустой» после удаления некоторых элементов, можно выполнить изменение размера, чтобы избежать чрезмерного использования памяти . ^[39] ${\displaystyle O(1)}$

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

Как правило, новая хеш-таблица, размер которой вдвое превышает размер исходной хеш-таблицы, выделяется в частном порядке, и каждый элемент исходной хеш-таблицы перемещается во вновь выделенную путем вычисления хэш-значений элементов с последующей операцией вставки. Перефразирование — это просто, но вычислительно дорого. ^{[40] : 478–479.}

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

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

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

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

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

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

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

Приложения

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

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

Индексирование базы данных

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

Тайники

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

Наборы

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

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

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

Реализации

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

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

C++11 включает unordered_mapв свою стандартную библиотеку для хранения ключей и значений произвольных типов . ^[51]

Встроенная функция Gomap реализует хэш-таблицу в виде типа . ^[52]

Язык программирования Java включает коллекции HashSet, HashMap, LinkedHashSetи LinkedHashMap generic . ^[53]

Встроенная функция Pythondict реализует хэш-таблицу в виде типа . ^[54]

Встроенная система RubyHash использует модель открытой адресации, начиная с Ruby 2.4. ^[55]

Язык программирования RustHashMap включает в себя HashSetкак часть стандартной библиотеки Rust. ^[56]

Стандартная библиотека .NETHashSet включает в себя и Dictionary, ^{[57] [58],} поэтому ее можно использовать из таких языков, как C# и VB.NET . ^[59]

Смотрите также

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

Рекомендации

1. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Массачусетский Институт Технологий. стр. 253–280. ISBN  978-0-262-03384-8.
2. Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 81–98.
3. Лейзерсон, Чарльз Э. (осень 2005 г.). «Лекция 13: Амортизированные алгоритмы, удвоение таблиц, потенциальный метод». курс MIT 6.046J/18.410J «Введение в алгоритмы» . Архивировано из оригинала 7 августа 2009 года.
4. Кнут, Дональд (1998). Искусство компьютерного программирования . Том. 3: Сортировка и поиск (2-е изд.). Аддисон-Уэсли. стр. 513–558. ISBN 978-0-201-89685-5.
5. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 11: Хэш-таблицы». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 221–252. ISBN 978-0-262-53196-2.
6. Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы. Том. 1 (4-е изд.). Addison-Wesley Professional – через Принстонский университет , факультет компьютерных наук.
7. Мехта, Динеш П.; Сахни, Сартадж (28 октября 2004 г.). «9: Хэш-таблицы». В Мехте, Динеш П.; Мехта, Динеш П.; Сахни, Сартадж (ред.). Справочник по структурам данных и приложениям (1-е изд.). Тейлор и Фрэнсис . дои : 10.1201/9781420035179. ISBN 978-1-58488-435-4.
8. Konheim, Алан Г. (21 июня 2010 г.). Хеширование в информатике: пятьдесят лет нарезки и нарезки кубиками. John Wiley & Sons, Inc., номер документа : 10.1002/9780470630617. ISBN  9780470630617.
9. Майерс, Эндрю (2008). «CS 312: Хэш-таблицы и амортизированный анализ». Корнелльский университет , факультет компьютерных наук. Архивировано из оригинала 26 апреля 2021 года . Проверено 26 октября 2021 г. - через cs.cornell.edu.
10. Джеймс С. Планк и Брэд Вандер Занден. «Конспекты лекций CS140 — Хеширование».
11. Маурер, В.Д.; Льюис, Т.Г. (1 марта 1975 г.). «Методы хеш-таблиц». Обзоры вычислительной техники ACM . Журнал АКМ . 1 (1): 14. дои : 10,1145/356643,356645. S2CID  17874775.
12. Оволаби, Олумид (1 февраля 2003 г.). «Эмпирические исследования некоторых хэш-функций». Информационные и программные технологии . Кафедра математики и информатики Университета Порт-Харкорта. 45 (2): 109–112. doi : 10.1016/S0950-5849(02)00174-X – через ScienceDirect .
13. Лу, Йи; Прабхакар, Баладжи; Бономи, Флавио (2006). Идеальное хеширование для сетевых приложений . 2006 Международный симпозиум IEEE по теории информации. стр. 2774–2778. дои : 10.1109/ISIT.2006.261567. ISBN 1-4244-0505-Х. S2CID  1494710.
14. Белазуги, Джамаль; Ботельо, Фабиано К.; Дитцфельбингер, Мартин (2009). «Хэш, перемещение и сжатие» (PDF) . Алгоритмы - ESA 2009: 17-й ежегодный европейский симпозиум, Копенгаген, Дания, 7-9 сентября 2009 г., Материалы . Конспекты лекций по информатике . Том. 5757. Берлин: Шпрингер. стр. 682–693. CiteSeerX 10.1.1.568.130 . дои : 10.1007/978-3-642-04128-0_61. МР  2557794. 
15. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 11: Хэш-таблицы». Введение в алгоритмы (2-е изд.). Массачусетский Институт Технологий . ISBN 978-0-262-53196-2.
16. Пирсон, Карл (1900). «О том критерии, что данная система отклонений от вероятного в случае коррелированной системы переменных такова, что можно разумно предположить, что она возникла в результате случайной выборки». Философский журнал . Серия 5. 50 (302): 157–175. дои : 10.1080/14786440009463897.
17. Плакетт, Робин (1983). «Карл Пирсон и тест хи-квадрат». Международный статистический обзор . 51 (1): 59–72. дои : 10.2307/1402731. JSTOR  1402731.
18. Ван, Томас (март 1997 г.). «Таблица простых двойных хэшей». Архивировано из оригинала 3 сентября 1999 года . Проверено 10 мая 2015 г.
19. Вегман, Марк Н .; Картер, Дж. Лоуренс (1981). «Новые хеш-функции и их использование при аутентификации и установлении равенства» (PDF) . Журнал компьютерных и системных наук . 22 (3): 265–279. дои : 10.1016/0022-0000(81)90033-7 . Версия конференции в FOCS'79 . Проверено 9 февраля 2011 г.
20. Дональд Э. Кнут (24 апреля 1998 г.). Искусство компьютерного программирования: Том 3: Сортировка и поиск. Аддисон-Уэсли Профессионал. ISBN 978-0-201-89685-5.
21. Демейн, Эрик; Линд, Джефф (весна 2003 г.). «Лекция 2» (PDF) . 6.897: Расширенные структуры данных. Лаборатория компьютерных наук и искусственного интеллекта Массачусетского технологического института . Архивировано (PDF) из оригинала 15 июня 2010 г. Проверено 30 июня 2008 г.
22. Аскитис, Николас; Зобель, Джастин (2005). Разрешение конфликтов с учетом кэша в строковых хеш-таблицах. Международный симпозиум по обработке строк и поиску информации. Springer Science+Business Media . стр. 91–102. дои : 10.1007/11575832_1. ISBN 978-3-540-29740-6.
23. Уиллард, Дэн Э. (2000). «Изучение вычислительной геометрии, деревьев Ван Эмде Боаса и хеширования с точки зрения дерева слияния». SIAM Journal по вычислительной технике . 29 (3): 1030–1049. дои : 10.1137/S0097539797322425. МР  1740562..
24. Аскитис, Николас; Синха, Ранджан (2010). «Разработка масштабируемых, кэш- и компактных попыток для строк». Журнал ВЛДБ . 17 (5): 634. doi :10.1007/s00778-010-0183-9. ISSN  1066-8888. S2CID  432572.
25. Аскитис, Николас; Зобель, Джастин (октябрь 2005 г.). «Разрешение конфликтов с учетом кэша в строковых хеш-таблицах». Материалы 12-й Международной конференции по обработке строк и поиску информации (SPIRE 2005) . Том. 3772/2005. стр. 91–102. дои : 10.1007/11575832_11. ISBN 978-3-540-29740-6.
26. Аскитис, Николас (2009). «Быстрые и компактные хеш-таблицы для целочисленных ключей» (PDF) . Материалы 32-й Австралазийской конференции по информатике (ACSC 2009) . Том. 91. стр. 113–122. ISBN 978-1-920682-72-9. Архивировано из оригинала (PDF) 16 февраля 2011 года . Проверено 13 июня 2010 г.
27. Тененбаум, Аарон М.; Лангсам, Едидия; Аугенштейн, Моше Дж. (1990). Структуры данных с использованием C . Прентис Холл. стр. 456–461, с. 472. ИСБН 978-0-13-199746-2.
28. Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка Хашинг». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. стр. 121–133. CiteSeerX 10.1.1.25.4189 . дои : 10.1007/3-540-44676-1_10. ISBN  978-3-540-42493-2.
29. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «11 хэш-таблиц», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 221–252, ISBN 0-262-03293-7.
30. Виттер, Джеффри С.; Чен, Вэнь-Чин (1987). Проектирование и анализ объединенного хеширования . Нью-Йорк, США: Издательство Оксфордского университета . ISBN 978-0-19-504182-8– через Archive.org .
31. Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка Хашинг». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. стр. 121–133. CiteSeerX 10.1.1.25.4189 . дои : 10.1007/3-540-44676-1_10. ISBN  978-3-540-42493-2.
32. Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). Классическое перемешивание. Международный симпозиум по распределенным вычислениям. Распределенных вычислений. Том. 5218. Берлин, Гейдельберг: Springer Publishing . стр. 350–364. дои : 10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3– через Springer Link.
33. Селис, Педро (1986). Робин Гуд Хэшинг (PDF) . Онтарио, Канада: Университет Ватерлоо , факультет компьютерных наук. ISBN 031529700X. OCLC  14083698. Архивировано (PDF) из оригинала 1 ноября 2021 года . Проверено 2 ноября 2021 г.
34. Поблете, ПВ; Виола А. (14 августа 2018 г.). «Анализ Робин Гуда и других алгоритмов хеширования в рамках модели случайного зондирования с удалениями и без них». Комбинаторика, теория вероятностей и вычисления . Издательство Кембриджского университета . 28 (4): 600–617. дои : 10.1017/S0963548318000408. ISSN  1469-2163. S2CID  125374363 . Получено 1 ноября 2021 г. - через Cambridge Core.
35. Кларксон, Майкл (2014). «Лекция 13: Хэш-таблицы». Корнелльский университет , факультет компьютерных наук. Архивировано из оригинала 7 октября 2021 года . Получено 1 ноября 2021 г. через cs.cornell.edu.
36. Грис, Дэвид (2017). «JavaHyperText и структура данных: хеширование Робин Гуда» (PDF) . Корнелльский университет , факультет компьютерных наук. Архивировано (PDF) из оригинала 26 апреля 2021 г. Получено 2 ноября 2021 г. через cs.cornell.edu.
37. Селис, Педро (28 марта 1988 г.). Внешнее хеширование Робин Гуда (PDF) (Технический отчет). Блумингтон, Индиана: Университет Индианы , факультет компьютерных наук. 246. Архивировано (PDF) из оригинала 3 ноября 2021 г. . Проверено 2 ноября 2021 г.
38. Годдард, Уэйн (2021). «Глава C5: Хэш-таблицы» (PDF) . Клемсонский университет . стр. 15–16 . Проверено 4 декабря 2023 г.
39. Девадас, Шрини; Демейн, Эрик (25 февраля 2011 г.). «Введение в алгоритмы: изменение размера хэш-таблиц» (PDF) . Массачусетский технологический институт , факультет компьютерных наук. Архивировано (PDF) из оригинала 7 мая 2021 г. Проверено 9 ноября 2021 г. - через MIT OpenCourseWare .
40. Тареджа, Рима (13 октября 2018 г.). «Хеширование и столкновение». Структуры данных с использованием C (2-е изд.). Издательство Оксфордского университета . ISBN 9780198099307.
41. Фридман, Скотт; Кришнан, Ананд; Лейдефрост, Николас (18 марта 2003 г.). «Хеш-таблицы для встраиваемых систем и систем реального времени» (PDF) . Все компьютерные науки и инженерные исследования . Вашингтонский университет в Сент-Луисе . дои : 10.7936/K7WD3XXV. Архивировано (PDF) оригинала 9 июня 2021 г. Получено 9 ноября 2021 г. - через факультет компьютерных наук Северо-Западного университета .
42. Литвин, Витольд (1980). «Линейное хеширование: новый инструмент для адресации файлов и таблиц» (PDF) . Учеб. 6-я конференция по очень большим базам данных . Университет Карнеги Меллон . стр. 212–223. Архивировано (PDF) оригинала 6 мая 2021 г. Получено 10 ноября 2021 г. через cs.cmu.edu.
43. Дейк, Том Ван (2010). «Анализ и улучшение производительности хеш-таблицы» (PDF) . Нидерланды : Университет Твенте . Архивировано (PDF) оригинала 6 ноября 2021 г. Проверено 31 декабря 2021 г.
44. Лех Банаховский. «Индексы и внешняя сортировка». pl:Польско-Японская академия компьютерных технологий. Архивировано из оригинала 26 марта 2022 года . Проверено 26 марта 2022 г.
45. Чжун, Лян; Чжэн, Сюэцянь; Лю, Юн; Ван, Мэнтин; Цао, Ян (февраль 2020 г.). «Максимизация коэффициента попадания в кэш при передаче данных между устройствами через сотовые сети». Китайские коммуникации . 17 (2): 232–238. doi : 10.23919/jcc.2020.02.018. ISSN  1673-5447. S2CID  212649328.
46. Боттомли, Джеймс (1 января 2004 г.). «Понимание кэширования». Linux-журнал . Архивировано из оригинала 4 декабря 2020 года . Проверено 16 апреля 2022 г.
47. Джилл Симан (2014). «Таблицы набора и хеширования» (PDF) . Техасский государственный университет . Архивировано из оригинала 1 апреля 2022 года . Проверено 26 марта 2022 г.{{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
48. "Таблица транспозиции - вики по шахматному программированию" . www.chessprogramming.org . Архивировано из оригинала 14 февраля 2021 года . Проверено 1 мая 2020 г.
49. «Типы данных и структуры данных JavaScript — JavaScript | MDN» . http://developer.mozilla.org . Проверено 24 июля 2022 г.
50. «Карта — JavaScript | MDN» . http://developer.mozilla.org . 20 июня 2023 г. . Проверено 15 июля 2023 г.
51. «Язык программирования C++ — Техническая спецификация» (PDF) . Международная Организация Стандартизации . стр. 812–813. Архивировано из оригинала (PDF) 21 января 2022 года . Проверено 8 февраля 2022 г.
52. «Спецификация языка программирования Go» . go.dev . Проверено 1 января 2023 г.
53. «Урок: Реализации (Учебные пособия по Java™> Коллекции)» . docs.oracle.com . Архивировано из оригинала 18 января 2017 года . Проверено 27 апреля 2018 г.
54. Чжан, Хуан; Цзя, Юнвэй (2020). «Оптимизация перефразирования Redis на основе машинного обучения». Физический журнал: серия конференций . 1453 (1): 3. Бибкод : 2020JPhCS1453a2048Z. дои : 10.1088/1742-6596/1453/1/012048 . S2CID  215943738.
55. Джонан Шеффлер (25 декабря 2016 г.). «Выпущен Ruby 2.4: более быстрые хэши, унифицированные целые числа и лучшее округление». геройку.com . Архивировано из оригинала 3 июля 2019 года . Проверено 3 июля 2019 г.
56. "doc.rust-lang.org". Архивировано из оригинала 8 декабря 2022 года . Проверено 14 декабря 2022 г.тест
57. «Класс HashSet (System.Collections.Generic)» . Learn.microsoft.com . Проверено 1 июля 2023 г.
58. дотнет-бот. «Класс словаря (System.Collections.Generic)». Learn.microsoft.com . Проверено 16 января 2024 г.
59. «Пример VB.NET HashSet» . Дот Нет Перлз .

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

• Тамассия, Роберто; Гудрич, Майкл Т. (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