Хеш-таблица

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

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

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

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

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

Хеширование [ править ]

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

индекс = f (ключ, размер_массива)

Часто это делается в два этапа:

hash = hashfunc (ключ)index = hash% array_size

В этом методе хэш не зависит от размера массива, а затем он сокращается до индекса (числа между 0и array_size − 1) с помощью оператора по модулю ( %).

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

Выбор хэш-функции [ править ]

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

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

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

Считается, что криптографические хеш-функции обеспечивают хорошие хеш-функции для любого размера таблицы, либо за счет уменьшения по модулю, либо за счет битового маскирования ^{[ необходима цитата ]} . Они также могут быть уместны, если есть риск того, что злоумышленники попытаются саботировать сетевую службу, отправив запросы, предназначенные для создания большого количества конфликтов в хеш-таблицах сервера. Однако риска саботажа можно также избежать более дешевыми методами (такими как применение секретной соли к данным или использование универсальной хеш-функции ). Недостатком криптографических хеш-функций является то, что они часто медленнее вычисляются, что означает, что в случаях, когда единообразие длялюбой размер не требуется, предпочтительнее использовать некриптографическую хеш-функцию. ^{[ необходима цитата ]}

Идеальная хеш-функция [ править ]

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

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

Ключевая статистика [ править ]

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

${\ displaystyle {\ text {коэффициент нагрузки}} = {\ frac {n} {k}}}$,

куда

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

По мере увеличения коэффициента загрузки хеш-таблица становится медленнее и может даже не работать (в зависимости от используемого метода). Свойство ожидаемого постоянного времени хэш-таблицы предполагает, что коэффициент нагрузки не превышает некоторого предела. Для фиксированного количества сегментов время поиска растет с количеством записей, и поэтому желаемое постоянное время не достигается. В некоторых реализациях решение состоит в том, чтобы автоматически увеличивать (обычно вдвое) размер таблицы при достижении ограничения коэффициента загрузки, что вынуждает повторно хешировать все записи. В качестве реального примера, коэффициент загрузки по умолчанию для HashMap в Java 10 составляет 0,75, что «предлагает хороший компромисс между затратами времени и пространства». ^[9]

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

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

Разрешение столкновений [ править ]

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

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

Отдельная цепочка [ править ]

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

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

Есть несколько реализаций ^[11], которые обеспечивают отличную производительность как для времени, так и для пространства, при этом среднее количество элементов в ведре находится в диапазоне от 5 до 100.

Отдельная цепочка со связанными списками [ править ]

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

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

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

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

Цепочки сегментов часто просматриваются последовательно, используя порядок, в котором записи были добавлены в сегмент. Если коэффициент загрузки велик и некоторые ключи с большей вероятностью подойдут, чем другие, то переупорядочение цепочки с эвристикой перехода к началу может быть эффективным. Более сложные структуры данных, такие как сбалансированные деревья поиска, заслуживают рассмотрения только в том случае, если коэффициент загрузки велик (около 10 или более), или если распределение хэшей, вероятно, будет очень неравномерным, или если нужно даже гарантировать хорошую производительность. в худшем случае. Однако в этих случаях использование более крупной таблицы и / или лучшей хеш-функции может быть даже более эффективным. ^{[ необходима цитата ]}

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

Отдельная цепочка с ячейками заголовка списка [ править ]

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

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

Разделить цепочку с другими структурами [ править ]

Вместо списка можно использовать любую другую структуру данных, поддерживающую необходимые операции. Например, используя самобалансирующееся двоичное дерево поиска , теоретическое время наихудшего случая общих операций с хеш-таблицей (вставка, удаление, поиск) может быть уменьшено до O (log n ), а не до O ( n ). Однако это вносит дополнительную сложность в реализацию и может привести к еще худшей производительности для небольших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше, чем время, необходимое для выполнения линейного поиска по всем элементам списка. . ^{[3] [12]}Реальным примером хеш-таблицы, в которой используется самобалансирующееся двоичное дерево поиска для сегментов, является HashMapкласс в Java версии 8 . ^[13]

Вариант, называемый хеш-таблицей массива, использует динамический массив для хранения всех хешированных записей в одном слоте. ^{[14] [15] [16]} Каждая вновь вставленная запись добавляется в конец динамического массива, назначенного слоту. Размер динамического массива изменяется точно по размеру , то есть он увеличивается только на необходимое количество байтов. Было обнаружено, что альтернативные методы, такие как увеличение массива по размеру блока или страниц , улучшают производительность вставки, но за счет экономии места. Этот вариант позволяет более эффективно использовать кэширование ЦП и резервный буфер трансляции.(TLB), поскольку записи слотов хранятся в последовательных позициях памяти. Он также избавляется от nextуказателей, которые требуются для связанных списков, что экономит место. Несмотря на частое изменение размера массива, накладные расходы на пространство, понесенные операционной системой, такие как фрагментация памяти, оказались небольшими. ^{[ необходима цитата ]}

Разработка такого подхода является так называемым динамическими совершенным хеширования , ^[17] , где ведро , которое содержит К записи организован как идеальный хэш - таблица с K ² слотов. Хотя он использует больше памяти ( n ² слотов для n записей в худшем случае и n × k слотов в среднем), этот вариант гарантирует постоянное время поиска в худшем случае и низкое амортизированное время для вставки. Также можно использовать дерево слияния для каждого ведра, с высокой вероятностью обеспечивая постоянное время для всех операций. ^[18]

Открытая адресация [ править ]

В другой стратегии, называемой открытой адресацией, все записи записей хранятся в самом массиве корзины. Когда должна быть вставлена ​​новая запись, сегменты исследуются, начиная с хешированного слота и продолжаясь в некоторой тестовой последовательности , пока не будет найден незанятый слот. При поиске записи сегменты сканируются в той же последовательности, пока не будет найдена целевая запись или не будет найден неиспользуемый слот массива, что указывает на отсутствие такого ключа в таблице. ^[19] Название «открытая адресация» относится к тому факту, что местоположение («адрес») элемента не определяется его хеш-значением. (Этот метод также называется закрытым хешированием ; его не следует путать с «открытым хешированием» или «закрытой адресацией». это обычно означает отдельную цепочку.)

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

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

Недостатком всех этих схем открытой адресации является то, что количество сохраненных записей не может превышать количество слотов в массиве корзины. Фактически, даже с хорошими хэш-функциями их производительность резко ухудшается, когда коэффициент загрузки превышает 0,7 или около того. Для многих приложений эти ограничения требуют использования динамического изменения размера с соответствующими затратами. ^{[ необходима цитата ]}

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

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

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

С другой стороны, обычная открытая адресация - плохой выбор для больших элементов, потому что эти элементы заполняют целые строки кэша ЦП (сводя на нет преимущество кеширования), и большое количество места тратится впустую на большие пустые слоты таблиц. Если открытая таблица адресации хранит только ссылки на элементы (внешнее хранилище), она использует пространство, сопоставимое с цепочкой, даже для больших записей, но теряет преимущество в скорости. ^{[ необходима цитата ]}

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

Объединенное хеширование [ править ]

Гибрид цепочки и открытой адресации, объединенное хеширование связывает вместе цепочки узлов внутри самой таблицы. ^[19] Как и открытая адресация, она обеспечивает использование пространства и (несколько уменьшенное) преимущество кеширования по сравнению с цепочкой. Как и цепочка, он не проявляет эффектов кластеризации; Фактически, таблица может быть эффективно заполнена до высокой плотности. В отличие от цепочки, в нем не может быть больше элементов, чем слотов стола.

Хеширование с кукушкой [ править ]

Еще одно альтернативное решение для открытой адресации - хеширование с кукушкой., что обеспечивает постоянное время поиска и удаления в худшем случае и постоянное амортизированное время для вставок (с малой вероятностью, что произойдет худший случай). Он использует две или более хэш-функций, что означает, что любая пара ключ / значение может находиться в двух или более местах. Для поиска используется первая хеш-функция; если ключ / значение не найден, то используется вторая хеш-функция и так далее. Если во время вставки происходит коллизия, то ключ повторно хешируется с помощью второй хеш-функции, чтобы сопоставить его с другой корзиной. Если все хэш-функции используются и конфликт все еще существует, то ключ, с которым он столкнулся, удаляется, чтобы освободить место для нового ключа, а старый ключ повторно хешируется с одной из других хэш-функций, которая сопоставляет его с другой. ведро. Если это место также приводит к столкновению,затем процесс повторяется до тех пор, пока не исчезнет коллизия или пока не пройдут все сегменты, после чего размер таблицы будет изменен. Комбинируя несколько хэш-функций с несколькими ячейками на ведро, можно достичь очень высокого использования пространства.^{[ необходима цитата ]}

Хеширование в классическом стиле [ править ]

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

Алгоритм классического хеширования работает, определяя соседство сегментов рядом с исходным хешированным сегментом, где всегда находится данная запись. Таким образом, поиск ограничен числом записей в этой окрестности, которое в худшем случае является логарифмическим, в среднем - постоянным, а при правильном выравнивании окрестности обычно требуется один промах в кэше. При вставке записи сначала пытаются добавить ее в ведро по соседству. Однако, если все сегменты в этой окрестности заняты, алгоритм последовательно просматривает сегменты до тех пор, пока не будет найден открытый слот (незанятый сегмент) (как при линейном зондировании). В этот момент, поскольку пустое ведро находится за пределами соседства, элементы неоднократно перемещаются в последовательности переходов. (Это похоже на хеширование с кукушкой,но с той разницей, что в этом случае пустой слот перемещается в соседство, вместо того, чтобы перемещать элементы с надеждой в конечном итоге найти пустой слот.) Каждый переход приближает открытый слот к исходному соседству, не делая недействительным соседство собственности любого из ведер по пути. В конце концов, открытый слот был перемещен в соседство, и вставляемая запись может быть добавлена ​​к нему.^{[ необходима цитата ]}

Хеширование Робин Гуда [ править ]

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

Хеширование с двумя вариантами [ править ]

Хеширование с двумя вариантами использует две разные хеш-функции, h ₁ ( x ) и h ₂ ( x ), для хеш-таблицы. Обе хеш-функции используются для вычисления двух положений таблицы. Когда объект вставляется в таблицу, он помещается в то место таблицы, которое содержит меньшее количество объектов (по умолчанию это расположение таблицы h ₁ ( x ), если есть равенство в размере корзины). Хеширование с двумя вариантами выбора использует принцип мощности двух вариантов. ^[27]

Динамическое изменение размера [ править ]

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

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

Изменение размера путем копирования всех записей [ править ]

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

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

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

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

Альтернативы перефразированию "все сразу" [ править ]

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

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

Постепенное изменение размера [ править ]

Альтернативой одновременному увеличению таблицы является постепенное перефразирование:

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

Чтобы обеспечить полное копирование старой таблицы до того, как потребуется увеличить новую таблицу, необходимо увеличить размер таблицы по крайней мере в ( r + 1) / r во время изменения размера.

Монотонные клавиши [ править ]

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

Учитывая некоторый начальный ключ k ₁ , последующий ключ k _i разделяет ключевую область [ k ₁ , ∞) на множество {[ k ₁ , k _i ), [ k _i , ∞) }. В общем, повторение этого процесса дает более точное разделение {[ k ₁ , k _{i 0} ), [ k _{i 0} , k _{i 1} ), ..., [ k _{i n - 1} , k _{i n} ), [ k _{i n}, ∞) } для некоторой последовательности монотонно возрастающих ключей ( k _{i 0} , ..., k _{i n} ) , где n - количество уточнений . Же процесс применяется, с соответствующими изменениями , чтобы монотонно убывающая ключи. Присваивая каждому подинтервалу этого раздела другую хеш-функцию или хеш-таблицу (или и то, и другое), а также уточняя раздел всякий раз, когда размер хеш-таблицы изменяется, этот подход гарантирует, что любой хэш-код ключа, однажды выданный, никогда не изменится, даже если хеш-таблица увеличена.

Поскольку общее количество записей обычно увеличивается за счет удвоения, для проверки останется только O (log ( N )) подинтервалов, а время двоичного поиска для перенаправления будет O (log (log ( N ))).

Линейное хеширование [ править ]

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

Хеширование для распределенных хеш-таблиц [ править ]

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

Производительность [ править ]

Анализ скорости [ править ]

В простейшей модели хэш-функция полностью не указана, и размер таблицы не изменяется. С идеальной хеш-функцией таблица размера с открытой адресацией не имеет коллизий и выдерживает до элементов с одним сравнением для успешного поиска, в то время как таблица размера с цепочкой и ключами имеет минимальные коллизии и сравнения для поиска. При наихудшей хеш-функции каждая вставка вызывает конфликт, и хеш-таблицы вырождают в линейный поиск с амортизированными сравнениями на каждую вставку и вплоть до сравнений для успешного поиска.${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle max (0, nk)}$${\ displaystyle \ Theta (1 + {\ frac {n} {k}})}$${\ Displaystyle \ Theta (п)}$${\ displaystyle n}$

Добавить в эту модель перехеширование несложно. Как и в случае с динамическим массивом , геометрическое изменение размера с коэффициентом означает, что вставляются только ключи или более раз, так что общее количество вставок ограничено выше , что составляет . Используя повторное хеширование для обслуживания , таблицы, использующие как цепочку, так и открытую адресацию, могут иметь неограниченное количество элементов и выполнять успешный поиск в одном сравнении для лучшего выбора хэш-функции.${\ displaystyle b}$${\displaystyle {\frac {n}{b^{i}}}}$${\displaystyle i}$${\displaystyle {\frac {bn}{b-1}}}$${\displaystyle \Theta (n)}$${\displaystyle n<k}$

В более реалистичных моделях хеш-функция является случайной величиной по распределению вероятностей хеш-функций, а производительность вычисляется в среднем по выбору хеш-функции. Когда это распределение является однородным , предположение называется «простым равномерным хешированием», и можно показать, что хеширование с цепочкой требует в среднем сравнений для неудачного поиска, а хеширование с открытой адресацией требует . ^[29] Обе эти границы являются постоянными, если мы поддерживаем ' использование изменения размера таблицы, где фиксированная константа меньше 1.${\displaystyle \Theta \left(1+{\frac {n}{k}}\right)}$${\displaystyle \Theta \left({\frac {1}{1-n/k}}\right)}$${\displaystyle {\frac {n}{k}}<c}$${\displaystyle c}$

Два фактора существенно влияют на задержку операций с хеш-таблицей: ^[30]

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

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

Использование памяти [ править ]

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

Другой метод был введен Дональдом Кнутом ^{[ необходима цитата ]} и называется частным . Для этого обсуждения предположит , что ключ, или обратимо-хэшированный версия этого ключа, представляет собой целое число м от {0, 1, 2, ..., М-1} и количество ковшей Н . m делится на N, чтобы получить частное q и остаток r . Остаток r используется для выбора ковша; в ведре нужно сохранить только частное q . Это экономит log ₂ (N) бита на элемент, что может быть очень важным в некоторых приложениях.

Quotienting легко работает с цепочкой хеш-таблиц или с простыми хеш-таблицами с кукушкой. Чтобы применить эту технику к обычным хеш-таблицам с открытой адресацией, Джон Г. Клири представил метод ^{[32], в} котором два бита ( первичный бит и бит изменения ) включаются в каждую корзину, чтобы позволить исходному индексу корзины ( r ) быть реконструирован.

В только что описанной схеме log ₂ (M / N) + 2 бита используются для хранения каждого ключа. Интересно отметить, что теоретическая минимальная память будет составлять log ₂ (M / N) + 1,4427 бит, где 1,4427 = log ₂ (e).

Особенности [ править ]

Преимущества [ править ]

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

Недостатки [ править ]

• Хотя операции с хеш-таблицей в среднем занимают постоянное время, стоимость хорошей хеш-функции может быть значительно выше, чем внутренний цикл алгоритма поиска для последовательного списка или дерева поиска. Таким образом, хеш-таблицы не эффективны, когда количество записей очень мало. (Однако в некоторых случаях высокая стоимость вычисления хэш-функции может быть уменьшена путем сохранения хеш-значения вместе с ключом.)
• Для некоторых приложений обработки строк, таких как проверка орфографии , хеш-таблицы могут быть менее эффективными, чем попытки , конечные автоматы или массивы Джуди . Кроме того, если существует не слишком много возможных ключей для хранения - то есть, если каждый ключ может быть представлен достаточно небольшим количеством бит - тогда вместо хеш-таблицы можно использовать ключ непосредственно в качестве индекса в массиве. ценностей. Обратите внимание, что в этом случае нет коллизий.
• Записи, хранящиеся в хэш-таблице, можно эффективно перечислить (с постоянной стоимостью записи), но только в некотором псевдослучайном порядке. Следовательно, не существует эффективного способа найти запись, ключ которой ближе всего к данному ключу. Перечисление всех n записей в определенном порядке обычно требует отдельного шага сортировки, стоимость которого пропорциональна log ( n ) на запись. Для сравнения, упорядоченные деревья поиска имеют стоимость поиска и вставки, пропорциональную log ( n ), но позволяют находить ближайший ключ примерно с той же стоимостью и упорядоченным перечислением всех записей с постоянной стоимостью записи. Однако LinkingHashMap может быть создан для создания хеш-таблицы с неслучайной последовательностью. ^[33]
• Если ключи не сохранены (потому что хеш-функция не имеет конфликтов), может не быть простого способа перечислить ключи, которые присутствуют в таблице в любой данный момент.
• Хотя средняя стоимость одной операции постоянна и довольно мала, стоимость одной операции может быть довольно высокой. В частности, если хэш-таблица использует динамическое изменение размера , операция вставки или удаления может иногда занимать время, пропорциональное количеству записей. Это может быть серьезным недостатком для приложений реального времени или интерактивных приложений.
• Хеш-таблицы в целом демонстрируют плохую локальность ссылок, то есть данные, к которым нужно получить доступ, распределены в памяти как бы случайным образом. Поскольку хеш-таблицы вызывают скачкообразные схемы доступа, это может вызвать промахи в кэше микропроцессора , вызывающие длительные задержки. Компактные структуры данных, такие как массивы, поиск которых выполняется с помощью линейного поиска, могут быть быстрее, если таблица относительно мала, а ключи компактны. Оптимальная производительность варьируется от системы к системе.
• Хеш-таблицы становятся совершенно неэффективными при большом количестве конфликтов. В то время как крайне неравномерное распределение хешей крайне маловероятно, что злонамеренный злоумышленник, зная о хэш-функции, может предоставить информацию в хэш, который создает наихудшее поведение, вызывая чрезмерные конфликты, что приводит к очень низкой производительности, например отказ в обслуживании нападения . ^{[34] [35] [36]} В критических приложениях может использоваться структура данных с лучшими гарантиями наихудшего случая; однако универсальное хеширование - рандомизированный алгоритм , не позволяющий злоумышленнику предсказать, какие входные данные вызывают наихудшее поведение - может быть предпочтительным. ^[37]Хэш-функция, используемая хеш-таблицей в кэше таблицы маршрутизации Linux, была изменена в Linux версии 2.4.2 в качестве меры противодействия таким атакам. ^[38]

Использует [ редактировать ]

Ассоциативные массивы [ править ]

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

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

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

Индексирование базы данных [ править ]

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

Кеши [ править ]

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

Наборы [ править ]

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

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

Представление объекта [ править ]

Некоторые динамические языки, такие как Perl , Python , JavaScript , Lua и Ruby , используют хэш-таблицы для реализации объектов . В этом представлении ключи - это имена членов и методов объекта, а значения - указатели на соответствующий член или метод.

Уникальное представление данных [ править ]

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

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

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

Реализации [ править ]

На языках программирования [ править ]

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

Java язык программирования ( в том числе вариант , который используется на Android ) включает в себя HashSet, HashMap, LinkedHashSetи LinkedHashMap родовые коллекции. ^[41]

В PHP 5 и 7 движок Zend 2 и движок Zend 3 (соответственно) используют одну из хэш-функций Дэниела Дж. Бернштейна для генерации хэш-значений, используемых при управлении отображениями указателей данных, хранящихся в хеш-таблице. В исходном коде PHP он помечен как DJBX33A(Daniel J. Bernstein, Times 33 с дополнением).

Встроенная реализация хеш-таблицы Python в форме dictтипа, а также хеш-тип Perl (%) используются внутренне для реализации пространств имен и, следовательно, должны уделять больше внимания безопасности, то есть атакам коллизий. Наборы Python также используют внутренние хэши для быстрого поиска (хотя они хранят только ключи, а не значения). ^[42] CPython 3.6+ использует вариант хэш-таблицы с упорядоченной вставкой, реализованный путем разделения хранилища значений на массив и хранения в стандартной хеш-таблице только набора индексов. ^[43]

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

В Ruby хеш-таблица использует модель открытой адресации, начиная с Ruby 2.4. ^{[44] [45]}

В стандартной библиотеке Rust общие структуры HashMapи HashSetструктуры используют линейное зондирование с кражей ведра Робин Гуда.

ANSI Smalltalk определяет классы Set/ IdentitySetи Dictionary/ IdentityDictionary. Все реализации Smalltalk предоставляют дополнительные (еще не стандартизованные) версии WeakSet, WeakKeyDictionaryи WeakValueDictionary.

Переменные массива Tcl - это хеш-таблицы, а словари Tcl - неизменяемые значения на основе хешей. Функциональность также доступна как функции библиотеки C Tcl_InitHashTable et al. (для общих хеш-таблиц) и Tcl_NewDictObj et al. (для значений словаря). Производительность была оценена независимо как чрезвычайно конкурентоспособная. ^[46]

В языке Wolfram поддерживаются хеш-таблицы начиная с версии 10. Они реализованы под именем Association.

Common Lisp предоставляет hash-tableкласс для эффективных отображений. Несмотря на свое название, языковой стандарт не требует фактического соблюдения каких-либо методов хеширования для реализаций. ^[47]

История [ править ]

Идея хеширования возникла независимо в разных местах. В январе 1953 года Ханс Петер Лун написал внутренний меморандум IBM, в котором использовалось хеширование с цепочкой. ^[48] Джин Амдал , Элейн М. МакГроу , Натаниэль Рочестер и Артур Сэмюэл реализовали программу, использующую хеширование, примерно в то же время. Открытая адресация с линейным зондированием (относительно простой шаг) приписывается Амдалу, но Ершов (в России) высказал ту же идею. ^[48]

См. Также [ править ]

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

Связанные структуры данных [ править ]

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

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме хеш-таблиц .

В Викиучебнике есть книга на тему: Структуры данных / Хеш-таблицы.

• Хеш-функция для поиска в хеш-таблице Боба Дженкинса.
• Хеш-функции Пола Хси
• Дизайн компактных и эффективных хеш-таблиц для Java
• Запись NIST в хеш-таблицах
• Лекция о хэш-таблицах из Стэнфордского CS106A
• Структуры открытых данных - Глава 5 - Хеш-таблицы , Пэт Морин
• Введение в алгоритмы MIT : хеширование 1 видео лекции MIT OCW
• Введение в алгоритмы MIT : хеширование 2 Видео лекции MIT OCW