Хэш-таблица
Хэш-таблица | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | Неупорядоченный ассоциативный массив | |||||||||||||||||||||||
Изобретенный | 1953 | |||||||||||||||||||||||
|
В вычислениях — хеш-таблица это структура данных, карты (также известного как словарь или ассоциативный массив) часто используемая для реализации абстрактного типа данных . Хэш-таблица использует хэш-функцию для вычисления индекса , также называемого хеш-кодом , в массиве сегментов или слотов , из которого можно найти желаемое значение. Во время поиска ключ хэшируется, и полученный хеш указывает, где хранится соответствующее значение.
Большинство проектов хеш-таблиц используют несовершенную хеш-функцию . Хэш-коллизии , когда хэш-функция генерирует один и тот же индекс для более чем одного ключа, поэтому обычно должны быть каким-то образом учтены.
В хорошо размерной хеш-таблице средняя временная сложность каждого поиска не зависит от количества элементов, хранящихся в таблице. Многие конструкции хэш-таблиц также допускают произвольные вставки и удаления пар ключ-значение с амортизированной постоянной средней стоимостью за операцию. [2] [3] [4]
Хеширование является примером компромисса между пространством и временем . Если память бесконечна, весь ключ можно использовать непосредственно как индекс для определения его значения за один доступ к памяти. С другой стороны, если доступно бесконечное время, значения можно хранить без учета их ключей, а двоичный или линейный поиск . для извлечения элемента можно использовать [5] : 458
Во многих ситуациях хеш-таблицы оказываются в среднем более эффективными, чем деревья поиска или любая другая в таблицах структура поиска . По этой причине они широко используются во многих видах компьютерного программного обеспечения , особенно для ассоциативных массивов , индексации баз данных , кэшей и наборов .
История
[ редактировать ]Идея хеширования возникла независимо в разных местах. В январе 1953 года Ханс Петер Лун написал внутренний меморандум IBM , в котором использовалось хеширование с цепочкой. Первый пример открытой адресации был предложен А.Д. Линем на основе меморандума Луна. [3] : 547 Примерно в то же время Джин Амдал , Элейн М. МакГроу , Натаниэль Рочестер и Артур Сэмюэл из IBM Research реализовали хеширование для IBM 701 ассемблера . [6] : 124 Открытую адресацию с линейным зондированием приписывают Амдалу, хотя Андрей Ершов . ту же идею выдвинул независимо [6] : 124–125 Термин «открытая адресация» был придуман У. Уэсли Петерсоном в его статье, в которой обсуждается проблема поиска в больших файлах. [7] : 15
Первая опубликованная работа по хешированию с цепочкой принадлежит Арнольду Дюми , который обсуждал идею использования остатка по модулю простого числа в качестве хэш-функции. [7] : 15 Слово «хеширование» впервые было опубликовано в статье Роберта Морриса. [6] : 126 Теоретический анализ линейного зондирования первоначально был представлен Конхеймом и Вайсом. [7] : 15
Обзор
[ редактировать ]Ассоциативный массив хранит набор пар (ключ, значение) и допускает вставку, удаление и поиск (поиск) с ограничением уникальных ключей . В реализации ассоциативных массивов в виде хэш-таблицы массив длины частично заполнен элементы, где . Значение сохраняется в индексном месте , где является хеш-функцией, и . [7] : 2 При разумных предположениях хеш-таблицы имеют лучшие ограничения по времени сложности операций поиска, удаления и вставки по сравнению с самобалансирующими двоичными деревьями поиска . [7] : 1
Хэш-таблицы также часто используются для реализации наборов, опуская сохраненное значение для каждого ключа и просто отслеживая, присутствует ли ключ. [7] : 1
Коэффициент нагрузки
[ редактировать ]Коэффициент нагрузки является критической статистикой хеш-таблицы и определяется следующим образом: [1] где
- — количество записей, занятых в хеш-таблице.
- это количество ведер.
Производительность хеш-таблицы ухудшается в зависимости от коэффициента загрузки. . [7] : 2
Программное обеспечение обычно гарантирует, что коэффициент загрузки остается ниже определенной константы, . Это помогает поддерживать хорошую производительность. Поэтому общий подход заключается в изменении размера или «перехешировании» хеш-таблицы всякий раз, когда коэффициент загрузки достигает . Аналогичным образом можно изменить размер таблицы, если коэффициент загрузки упадет ниже . [8]
Коэффициент нагрузки для отдельной цепочки
[ редактировать ]При использовании отдельных цепочек хеш-таблиц каждый слот массива сегментов хранит указатель на список или массив данных. [9]
Производительность отдельных цепочек хеш-таблиц постепенно снижается по мере роста коэффициента загрузки, и нет фиксированной точки, после которой абсолютно необходимо изменение размера. [8]
При раздельной цепочке значение который обеспечивает наилучшую производительность, обычно находится в диапазоне от 1 до 3. [8]
Коэффициент загрузки для открытой адресации
[ редактировать ]При открытой адресации каждый слот массива сегментов содержит ровно один элемент. Поэтому хеш-таблица с открытым адресом не может иметь коэффициент загрузки больше 1. [9]
Производительность открытой адресации становится очень плохой, когда коэффициент загрузки приближается к 1. [8]
Поэтому хеш-таблица, использующая открытую адресацию, должна быть изменена или перехеширована, если коэффициент загрузки приближается к 1. [8]
При открытой адресации приемлемые показатели максимального коэффициента загрузки. должно находиться в пределах от 0,6 до 0,75. [10] [11] : 110
Хэш-функция
[ редактировать ]функция Хэш- отображает вселенную ключей к индексам или слотам внутри таблицы, то есть для . Обычные реализации хеш-функций основаны на предположении целочисленной вселенной , что все элементы таблицы происходят из юниверса. , где длина битовая ограничен размером слова компьютерной архитектуры . [7] : 2
Хэш-функция говорят, что он идеален для данного набора оно инъективно если , то есть если каждый элемент отображает другое значение в . [12] [13] Идеальную хэш-функцию можно создать, если все ключи известны заранее. [12]
Предположение о целочисленной вселенной
[ редактировать ]Схемы хеширования, используемые в предположении целочисленной вселенной, включают хеширование делением, хеширование умножением, универсальное хеширование , динамическое идеальное хеширование и статическое идеальное хеширование . [7] : 2 Однако широко используемой схемой является хеширование делением. [14] : 264 [11] : 110
Хеширование по делению
[ редактировать ]Схема хеширования делением следующая: [7] : 2 Где это хеш-дайджест и это размер стола.
Хеширование путем умножения
[ редактировать ]Схема хеширования умножением следующая: [7] : 2–3 Где является вещественной константой и это размер стола. Преимущество хеширования путем умножения состоит в том, что не критично. [7] : 2–3 Хотя любое значение производит хэш-функцию, Дональд Кнут предлагает использовать золотое сечение . [7] : 3
Выбор хеш-функции
[ редактировать ]Равномерное распределение хеш-значений является фундаментальным требованием хеш-функции. Неравномерное распределение увеличивает количество коллизий и стоимость их разрешения. Единообразие иногда трудно обеспечить при проектировании, но его можно оценить эмпирически с использованием статистических тестов, например критерия хи-квадрат Пирсона для дискретных равномерных распределений. [15] [16]
Распределение должно быть равномерным только для размеров таблиц, встречающихся в приложении. В частности, если используется динамическое изменение размера с точным удвоением и уменьшением размера таблицы вдвое, то хеш-функция должна быть однородной только тогда, когда размер равен степени двойки . Здесь индекс можно вычислить как некоторый диапазон битов хэш-функции. С другой стороны, некоторые алгоритмы хеширования предпочитают, чтобы размер был простым числом . [17]
Для открытых схем адресации хеш-функция также должна избегать кластеризации — сопоставления двух или более ключей с последовательными слотами. Такая кластеризация может привести к резкому увеличению затрат на поиск, даже если коэффициент загрузки низкий и коллизии нечасты. Утверждается, что популярный мультипликативный хеш имеет особенно плохое поведение при кластеризации. [17] [3]
K-независимое хеширование предлагает способ доказать, что определенная хеш-функция не имеет плохих наборов ключей для данного типа хеш-таблицы. Ряд результатов K-независимости известен для схем разрешения коллизий, таких как линейное зондирование и хеширование с кукушкой. Поскольку K-независимость может доказать, что хеш-функция работает, можно сосредоточиться на поиске максимально быстрой такой хеш-функции. [18]
Разрешение столкновений
[ редактировать ]Алгоритм поиска, использующий хеширование, состоит из двух частей. Первая часть — вычисление хэш-функции , которая преобразует ключ поиска в индекс массива . В идеальном случае никакие два ключа поиска не совпадают с одним и тем же индексом массива. Однако это не всегда так, и невозможно гарантировать невидимые данные. [19] : 515 Следовательно, вторая часть алгоритма — разрешение коллизий. Двумя распространенными методами разрешения коллизий являются отдельная цепочка и открытая адресация. [5] : 458
Отдельная цепочка
[ редактировать ]При раздельной цепочке процесс включает в себя создание связанного списка с парой ключ-значение для каждого индекса массива поиска. Конфликтующие элементы объединяются в единый связанный список, по которому можно получить доступ к элементу с помощью уникального ключа поиска. [5] : 464 Разрешение коллизий посредством связывания со связанным списком — распространенный метод реализации хеш-таблиц. Позволять и быть хеш-таблицей и узлом соответственно, операция включает в себя следующее: [14] : 258
Chained-Hash-Insert(T, k) insert x at the head of linked list T[h(k)] Chained-Hash-Search(T, k) search for an element with key k in linked list T[h(k)] Chained-Hash-Delete(T, k) delete x from the linked list T[h(k)]
Если элемент сопоставим численно или лексически и вставлен в список с сохранением общего порядка , это приводит к более быстрому прекращению безуспешных поисков. [19] : 520–521
Другие структуры данных для отдельной цепочки
[ редактировать ]Если ключи упорядочены , было бы эффективно использовать концепции « самоорганизации », такие как использование самобалансирующегося двоичного дерева поиска , с помощью которого теоретический худший случай можно свести к , хотя это и вносит дополнительные сложности. [19] : 521
В динамическом идеальном хешировании используются двухуровневые хэш-таблицы, чтобы уменьшить сложность поиска и гарантировать гарантированное получение результата. в худшем случае. В этой технике ведра записи организованы как идеальные хэш-таблицы с слоты, обеспечивающие постоянное время поиска в худшем случае и малое амортизируемое время для вставки. [20] Исследование показывает, что раздельное связывание на основе массива на 97% более производительно по сравнению со стандартным методом связанного списка при большой нагрузке. [21] : 99
Такие методы, как использование дерева слияния для каждого сегмента, также приводят к постоянному времени для всех операций с высокой вероятностью. [22]
Кэширование и локальность ссылки
[ редактировать ]Связанный список реализации отдельной цепочки может не учитывать кэш из- за пространственной локальности — локальности ссылки — когда узлы связанного списка разбросаны по памяти, поэтому обход списка во время вставки и поиска может повлечь за собой неэффективность кэша ЦП . [21] : 91
В вариантах разрешения коллизий с учетом кэша посредством отдельной цепочки динамический массив , который оказался более удобным для кэша, используется в том месте, где обычно развертывается связанный список или самобалансирующиеся двоичные деревья поиска, поскольку шаблон непрерывного размещения массива могут быть использованы устройствами предварительной выборки аппаратного кэша , такими как резервный буфер трансляции , что приводит к сокращению времени доступа и потребления памяти. [23] [24] [25]
Открытая адресация
[ редактировать ]Открытая адресация — это еще один метод разрешения коллизий, при котором каждая запись записи сохраняется в самом массиве сегментов, а разрешение хэша выполняется посредством зондирования . Когда необходимо вставить новую запись, сегменты проверяются, начиная с хешированного слота и продолжая некоторую тестовую последовательность , пока не будет найден незанятый слот. При поиске записи сегменты сканируются в одной и той же последовательности, пока не будет найдена либо целевая запись, либо не найден неиспользуемый слот массива, что свидетельствует о неудачном поиске. [26]
Хорошо известные последовательности зондов включают:
- Линейное зондирование , при котором интервал между зондами фиксирован (обычно 1). [27]
- Квадратичное зондирование , при котором интервал между зондами увеличивается путем добавления последовательных выходных данных квадратичного полинома к значению, полученному в результате исходного вычисления хеш-функции. [28] : 272
- Двойное хеширование , при котором интервал между проверками вычисляется вторичной хэш-функцией. [28] : 272–273
Производительность открытой адресации может быть медленнее по сравнению с раздельной цепочкой, поскольку последовательность проверки увеличивается при увеличении коэффициента загрузки. приближается к 1. [8] [21] : 93 Зондирование приводит к бесконечному циклу , если коэффициент загрузки достигает 1 в случае полностью заполненной таблицы. [5] : 471 Средняя стоимость линейного зондирования зависит от способности хэш-функции распределять элементы равномерно по таблице, чтобы избежать кластеризации , поскольку формирование кластеров приведет к увеличению времени поиска. [5] : 472
Кэширование и локальность ссылки
[ редактировать ]Поскольку слоты расположены в последовательных местах, линейное зондирование может привести к лучшему использованию кэша ЦП за счет локальности ссылок, что приведет к снижению задержки памяти . [27]
Другие методы разрешения коллизий, основанные на открытой адресации.
[ редактировать ]Объединенное хеширование
[ редактировать ]Объединенное хеширование — это гибрид отдельной цепочки и открытой адресации, при которой сегменты или узлы связаны внутри таблицы. [29] : 6–8 Алгоритм идеально подходит для фиксированного распределения памяти . [29] : 4 Коллизия при объединенном хешировании разрешается путем определения пустого слота с наибольшим индексом в хеш-таблице, затем в этот слот вставляется конфликтующее значение. Бакет также связан со слотом вставленного узла, который содержит его конфликтующий хэш-адрес. [29] : 8
Хеширование с кукушкой
[ редактировать ]Хеширование с кукушкой — это форма метода разрешения коллизий с открытой адресацией, которая гарантирует сложность поиска в худшем случае и постоянное амортизированное время для вставок. Конфликт разрешается путем поддержки двух хеш-таблиц, каждая из которых имеет свою собственную хеш-функцию, при этом конфликтующий слот заменяется заданным элементом, а занятый элемент слота перемещается в другую хеш-таблицу. Процесс продолжается до тех пор, пока каждый ключ не займет свое место в пустых ячейках таблиц; если процедура входит в бесконечный цикл , который определяется посредством поддержания счетчика порогового цикла, обе хеш-таблицы перехэшируются с использованием новых хэш-функций, и процедура продолжается. [30] : 124–125
Классическое хеширование
[ редактировать ]Хеширование Hopscotch — это алгоритм, основанный на открытой адресации, который сочетает в себе элементы хеширования с кукушкой , линейного зондирования и цепочки посредством понятия окрестности сегментов — последующих сегментов вокруг любого данного занятого сегмента, также называемого «виртуальным» контейнером. [31] : 351–352 Алгоритм предназначен для обеспечения более высокой производительности, когда коэффициент загрузки хеш-таблицы превышает 90%; он также обеспечивает высокую пропускную способность при параллельных настройках , поэтому хорошо подходит для реализации параллельной хэш-таблицы изменяемого размера . [31] : 350 Характеристика окрестности хеширования в классах гарантирует свойство, заключающееся в том, что стоимость поиска желаемого элемента в любых заданных корзинах внутри окрестности очень близка к стоимости его поиска в самой корзине; алгоритм пытается стать элементом в своем окружении — с возможными затратами, связанными с вытеснением других элементов. [31] : 352
Каждый сегмент в хеш-таблице включает в себя дополнительную «информацию о переходе» — H -бит битовый массив для указания относительного расстояния до элемента, который изначально был хеширован в текущем виртуальном сегменте в пределах записей H -1. [31] : 352 Позволять и быть ключом, который нужно вставить, и сегментом, в который хешируется ключ соответственно; В процедуре вставки задействовано несколько случаев, так что свойство соседства алгоритма гарантировано: [31] : 352–353 если пуст, элемент вставлен, а самый левый бит растрового изображения установлен в 1; если он не пуст, для поиска пустого слота в таблице используется линейное зондирование, растровое изображение сегмента обновляется с последующей вставкой; если пустой слот не находится в пределах диапазона окрестности , т.е. H -1, последующая манипуляция массивом битов обмена и информации о переходе для каждого сегмента выполняется в соответствии с его инвариантными свойствами окрестности . [31] : 353
Робин Гуд хэширует
[ редактировать ]Хеширование Робин Гуда — это алгоритм разрешения коллизий на основе открытой адресации; коллизии разрешаются за счет смещения самого дальнего элемента (или самой длинной пробной последовательности (PSL)) от его «исходного местоположения», т. е. корзины, в которую элемент был хеширован. [32] : 12 Хотя хеширование Робин Гуда не меняет теоретическую стоимость поиска , оно существенно влияет на дисперсию распределения . элементов по корзинам [33] : 2 т.е. речь идет о формировании кластера в хеш-таблице. [34] Каждый узел в хеш-таблице, использующий хеширование Робин Гуда, должен быть дополнен для хранения дополнительного значения PSL. [35] Позволять быть ключом для вставки, быть (дополнительной) длиной PSL , быть хеш-таблицей и быть индексом, процедура вставки следующая: [32] : 12–13 [36] : 5
- Если : итерация переходит к следующему сегменту без попытки внешнего зондирования.
- Если : вставить элемент в ведро ; менять с -будь как будет ; продолжить исследование с ведро для вставки ; повторяйте процедуру, пока каждый элемент не будет вставлен.
Динамическое изменение размера
[ редактировать ]Повторные вставки приводят к увеличению количества записей в хеш-таблице, что, следовательно, увеличивает коэффициент загрузки; для поддержания амортизированной выполнение операций поиска и вставки, размер хеш-таблицы динамически изменяется, а элементы таблиц перехэшируются в сегменты новой хеш-таблицы, [8] поскольку элементы не могут быть скопированы, поскольку изменение размеров таблицы приводит к разным значениям хеш-функции из-за операции по модулю . [37] Если хеш-таблица становится «слишком пустой» после удаления некоторых элементов, можно выполнить изменение размера, чтобы избежать чрезмерного использования памяти . [38]
Изменение размера путем перемещения всех записей
[ редактировать ]Как правило, новая хеш-таблица, размер которой вдвое превышает размер исходной хеш-таблицы, выделяется в частном порядке, и каждый элемент исходной хэш-таблицы перемещается во вновь выделенную путем вычисления хэш-значений элементов с последующей операцией вставки. Перефразирование — это просто, но вычислительно дорого. [39] : 478–479
Альтернативы перефразированию «все сразу»
[ редактировать ]Некоторые реализации хеш-таблиц, особенно в системах реального времени , не могут заплатить за увеличение всей хеш-таблицы одновременно, поскольку это может прервать критичные по времени операции. Если невозможно избежать динамического изменения размера, решение состоит в том, чтобы выполнять изменение размера постепенно, чтобы избежать провалов в памяти (обычно на 50% от размера новой таблицы) во время перехеширования и во избежание фрагментации памяти , которая вызывает уплотнение кучи из -за освобождения больших блоков памяти, вызванных старая хэш-таблица. [40] : 2–3 В таком случае операция повторного хеширования выполняется постепенно путем расширения предыдущего блока памяти, выделенного для старой хеш-таблицы, так что сегменты хеш-таблицы остаются неизменными. Общий подход к амортизированному перефразированию предполагает сохранение двух хэш-функций. и . Процесс повторного хеширования элементов корзины в соответствии с новой хеш-функцией называется очисткой и реализуется с помощью шаблона команды путем инкапсуляции таких операций, как , и через обертку , в которой каждый элемент в корзине перехешируется, а его процедура выглядит следующим образом: [40] : 3
- Чистый ведро.
- Чистый ведро.
- Команда . выполняется
Линейное хеширование
[ редактировать ]Линейное хеширование — это реализация хеш-таблицы, которая обеспечивает динамический рост или сжатие таблицы по одному блоку за раз. [41]
Производительность
[ редактировать ]Производительность хеш-таблицы зависит от способности хеш-функции генерировать квазислучайные числа ( ) для записей в хэш-таблице, где , и обозначает ключ, количество сегментов и хэш-функцию такие, что . Если хэш-функция генерирует то же самое для разных ключей ( ), это приводит к столкновению , которое решается различными способами. Постоянная временная сложность ( ) операции в хеш-таблице предполагается при условии, что хеш-функция не генерирует конфликтующие индексы; таким образом, производительность хеш-таблицы прямо пропорциональна способности выбранной хеш-функции распределять индексы. [42] : 1 Однако построение такой хеш-функции практически невозможно , поэтому реализация зависит от в конкретных случаях методов разрешения коллизий для достижения более высокой производительности. [42] : 2
Приложения
[ редактировать ]Ассоциативные массивы
[ редактировать ]Хэш-таблицы обычно используются для реализации многих типов таблиц в памяти. Они используются для реализации ассоциативных массивов . [28]
Индексирование базы данных
[ редактировать ]Хэш-таблицы также могут использоваться в качестве дисковых структур данных и индексов базы данных (например, в dbm ), хотя B-деревья . в этих приложениях более популярны [43]
Тайники
[ редактировать ]Хэш-таблицы могут использоваться для реализации кэшей , вспомогательных таблиц данных, которые используются для ускорения доступа к данным, которые в основном хранятся на более медленных носителях. В этом приложении коллизии хэшей можно обрабатывать, отбрасывая одну из двух конфликтующих записей — обычно удаляя старый элемент, который в данный момент хранится в таблице, и перезаписывая его новым элементом, поэтому каждый элемент в таблице имеет уникальное значение хеш-функции. [44] [45]
Наборы
[ редактировать ]Хэш-таблицы могут использоваться при реализации заданной структуры данных , которая может хранить уникальные значения без какого-либо определенного порядка; set обычно используется при проверке членства значения в коллекции, а не при поиске элементов. [46]
Таблица транспонирования
[ редактировать ]Таблица преобразования в сложную хэш-таблицу, в которой хранится информация о каждом разделе, по которому осуществлялся поиск. [47]
Реализации
[ редактировать ]Многие языки программирования предоставляют функциональность хеш-таблиц либо в виде встроенных ассоциативных массивов, либо в виде стандартных библиотечных модулей.
В JavaScript «объект» — это изменяемая коллекция пар ключ-значение (называемых «свойствами»), где каждый ключ представляет собой либо строку, либо гарантированно уникальный «символ»; любое другое значение, используемое в качестве ключа, сначала преобразуется в строку. За исключением семи «примитивных» типов данных, каждое значение в JavaScript является объектом. [48] ECMAScript 2015 также добавил Map
структура данных, которая принимает произвольные значения в качестве ключей. [49]
С++ 11 включает в себя unordered_map
в своей стандартной библиотеке для хранения ключей и значений произвольных типов . [50]
Go встроен map
реализует хеш-таблицу в виде типа . [51]
Java включает в себя Язык программирования HashSet
, HashMap
, LinkedHashSet
, и LinkedHashMap
универсальные коллекции. [52]
Python Встроенный dict
реализует хеш-таблицу в виде типа . [53]
Ruby встроенный в Hash
использует модель открытой адресации, начиная с Ruby 2.4. [54]
Rust включает в себя Язык программирования HashMap
, HashSet
как часть стандартной библиотеки Rust. [55]
Стандартная библиотека .NET включает в себя HashSet
и Dictionary
, [56] [57] поэтому его можно использовать из таких языков, как C# и VB.NET . [58]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Массачусетский технологический институт. стр. 253–280. ISBN 978-0-262-03384-8 .
- ^ Лейзерсон, Чарльз Э. (осень 2005 г.). «Лекция 13: Амортизированные алгоритмы, удвоение таблиц, потенциальный метод» . курс MIT 6.046J/18.410J «Введение в алгоритмы» . Архивировано из оригинала 7 августа 2009 года.
- ^ Перейти обратно: а б с Кнут, Дональд (1998). Искусство компьютерного программирования . Том. 3: Сортировка и поиск (2-е изд.). Аддисон-Уэсли. стр. 513–558. ISBN 978-0-201-89685-5 .
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 11: Хэш-таблицы». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 221–252 . ISBN 978-0-262-53196-2 .
- ^ Перейти обратно: а б с д и Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы . Том. 1 (4-е изд.). Addison-Wesley Professional – через Принстонский университет , факультет компьютерных наук.
- ^ Перейти обратно: а б с Конхейм, Алан Г. (2010). Хеширование в информатике . дои : 10.1002/9780470630617 . ISBN 978-0-470-34473-6 .
- ^ Перейти обратно: а б с д и ж г час я дж к л м Мехта, Динеш П.; Мехта, Динеш П.; Сахни, Сартадж, ред. (2004). Справочник по структурам данных и приложениям . дои : 10.1201/9781420035179 . ISBN 978-0-429-14701-2 .
- ^ Перейти обратно: а б с д и ж г Майерс, Эндрю (2008). «CS 312: Хэш-таблицы и амортизированный анализ» . Корнелльский университет , факультет компьютерных наук. Архивировано из оригинала 26 апреля 2021 года . Проверено 26 октября 2021 г. - через cs.cornell.edu.
- ^ Перейти обратно: а б Джеймс С. Планк и Брэд Вандер Занден. «Конспекты лекций CS140 — Хеширование» .
- ^ Маурер, В.Д.; Льюис, Т.Г. (март 1975 г.). «Методы хеш-таблиц». Обзоры вычислительной техники ACM . 7 (1): 5–19. дои : 10.1145/356643.356645 . S2CID 17874775 .
- ^ Перейти обратно: а б Оволаби, Олумид (февраль 2003 г.). «Эмпирические исследования некоторых хэш-функций». Информационные и программные технологии . 45 (2): 109–112. дои : 10.1016/S0950-5849(02)00174-X .
- ^ Перейти обратно: а б Лу, Йи; Прабхакар, Баладжи; Бономи, Флавио (2006). Идеальное хеширование для сетевых приложений . 2006 Международный симпозиум IEEE по теории информации. стр. 2774–2778. дои : 10.1109/ISIT.2006.261567 . ISBN 1-4244-0505-Х . S2CID 1494710 .
- ^ Белазуги, Джамаль; Ботельо, Фабиано К.; Дитцфельбингер, Мартин (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 .
- ^ Перейти обратно: а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 11: Хэш-таблицы». Введение в алгоритмы (2-е изд.). Массачусетский технологический институт . ISBN 978-0-262-53196-2 .
- ^ Пирсон, Карл (1900). «О том критерии, что данная система отклонений от вероятного в случае коррелированной системы переменных такова, что можно разумно предположить, что она возникла в результате случайной выборки» . Философский журнал . Серия 5. 50 (302): 157–175. дои : 10.1080/14786440009463897 .
- ^ Плакетт, Робин (1983). «Карл Пирсон и тест хи-квадрат». Международный статистический обзор . 51 (1): 59–72. дои : 10.2307/1402731 . JSTOR 1402731 .
- ^ Перейти обратно: а б Ван, Томас (март 1997 г.). «Таблица простых двойных хэшей» . Архивировано из оригинала 3 сентября 1999 года . Проверено 10 мая 2015 г.
- ^ Вегман, Марк Н.; Картер, Дж. Лоуренс (июнь 1981 г.). «Новые хэш-функции и их использование при аутентификации и установлении равенства» . Журнал компьютерных и системных наук . 22 (3): 265–279. дои : 10.1016/0022-0000(81)90033-7 .
- ^ Перейти обратно: а б с Дональд Э. Кнут (24 апреля 1998 г.). Искусство компьютерного программирования: Том 3: Сортировка и поиск . Аддисон-Уэсли Профессионал. ISBN 978-0-201-89685-5 .
- ^ Демейн, Эрик; Линд, Джефф (весна 2003 г.). «Лекция 2» (PDF) . 6.897: Расширенные структуры данных. Лаборатория компьютерных наук и искусственного интеллекта Массачусетского технологического института . Архивировано (PDF) из оригинала 15 июня 2010 г. Проверено 30 июня 2008 г.
- ^ Перейти обратно: а б с Калпеппер, Дж. Шейн; Моффат, Алистер (2005). «Расширенные байт-коды с ограниченными свойствами префикса». Обработка строк и поиск информации . Конспекты лекций по информатике. Том. 3772. стр. 1–12. дои : 10.1007/11575832_1 . ISBN 978-3-540-29740-6 .
- ^ Уиллард, Дэн Э. (2000). «Изучение вычислительной геометрии, деревьев Ван Эмде Боаса и хеширования с точки зрения дерева слияния». SIAM Journal по вычислительной технике . 29 (3): 1030–1049. дои : 10.1137/S0097539797322425 . МР 1740562 . .
- ^ Аскитис, Николас; Синха, Ранджан (октябрь 2010 г.). «Разработка масштабируемых, кэш- и компактных попыток для строк». Журнал ВЛДБ . 19 (5): 633–660. дои : 10.1007/s00778-010-0183-9 .
- ^ Аскитис, Николас; Зобель, Джастин (октябрь 2005 г.). «Разрешение конфликтов с учетом кэша в строковых хеш-таблицах». Материалы 12-й Международной конференции по обработке строк и поиску информации (SPIRE 2005) . Том. 3772/2005. стр. 91–102. дои : 10.1007/11575832_11 . ISBN 978-3-540-29740-6 .
- ^ Аскитис, Николас (2009). «Быстрые и компактные хеш-таблицы для целочисленных ключей» (PDF) . Материалы 32-й Австралазийской конференции по информатике (ACSC 2009) . Том. 91. стр. 113–122. ISBN 978-1-920682-72-9 . Архивировано из оригинала (PDF) 16 февраля 2011 года . Проверено 13 июня 2010 г.
- ^ Тененбаум, Аарон М.; Медленно, Едидия; Аугенштейн, Моше Дж. (1990). Структуры данных с использованием C . Прентис Холл. стр. 456–461, с. 472. ИСБН 978-0-13-199746-2 .
- ^ Перейти обратно: а б Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка Хашинг». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том 2161. С. 121–133. CiteSeerX 10.1.1.25.4189 . дои : 10.1007/3-540-44676-1_10 . ISBN 978-3-540-42493-2 .
- ^ Перейти обратно: а б с Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «11 хэш-таблиц», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 221–252, ISBN 0-262-03293-7 .
- ^ Перейти обратно: а б с Виттер, Джеффри С.; Чен, Вэнь-Чин (1987). Проектирование и анализ объединенного хеширования . Нью-Йорк, США: Издательство Оксфордского университета . ISBN 978-0-19-504182-8 – через Archive.org .
- ^ Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка Хашинг». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том 2161. С. 121–133. CiteSeerX 10.1.1.25.4189 . дои : 10.1007/3-540-44676-1_10 . ISBN 978-3-540-42493-2 .
- ^ Перейти обратно: а б с д и ж Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). «Хеширование в классиках». Распределенные вычисления . Конспекты лекций по информатике. Том. 5218. стр. 350–364. дои : 10.1007/978-3-540-87779-0_24 . ISBN 978-3-540-87778-3 .
- ^ Перейти обратно: а б Селис, Питер (1986). Робин Гуд Хэшинг (PDF) . Онтарио, Канада: Университет Ватерлоо , кафедра. компьютерных наук. ISBN 978-0-315-29700-5 . OCLC 14083698 . Архивировано (PDF) оригинала 1 ноября 2021 г. Проверено 2 ноября 2021 г.
- ^ Поблете, ПВ; Виола, А. (июль 2019 г.). «Анализ Робин Гуда и других алгоритмов хеширования в рамках модели случайного зондирования с удалениями и без них». Комбинаторика, теория вероятностей и вычисления . 28 (4): 600–617. дои : 10.1017/S0963548318000408 . S2CID 125374363 .
- ^ Кларксон, Майкл (2014). «Лекция 13: Хэш-таблицы» . Корнелльский университет , факультет компьютерных наук. Архивировано из оригинала 7 октября 2021 года . Получено 1 ноября 2021 г. через cs.cornell.edu.
- ^ Грис, Дэвид (2017). «JavaHyperText и структура данных: хеширование Робин Гуда» (PDF) . Корнелльский университет , факультет компьютерных наук. Архивировано (PDF) из оригинала 26 апреля 2021 г. Получено 2 ноября 2021 г. через cs.cornell.edu.
- ^ Селис, Педро (28 марта 1988 г.). Внешнее хеширование Робин Гуда (PDF) (Технический отчет). Блумингтон, Индиана: Университет Индианы , факультет компьютерных наук. 246. Архивировано (PDF) из оригинала 3 ноября 2021 г. . Проверено 2 ноября 2021 г.
- ^ Годдард, Уэйн (2021). «Глава C5: Хэш-таблицы» (PDF) . Клемсонский университет . стр. 15–16 . Проверено 4 декабря 2023 г.
- ^ Девадас, Шрини; Демейн, Эрик (25 февраля 2011 г.). «Введение в алгоритмы: изменение размера хэш-таблиц» (PDF) . Массачусетский технологический институт , факультет компьютерных наук. Архивировано (PDF) из оригинала 7 мая 2021 г. Проверено 9 ноября 2021 г. - через MIT OpenCourseWare .
- ^ Тареджа, Рима (2014). «Хеширование и столкновение». Структуры данных с использованием C . Издательство Оксфордского университета. стр. 464–488. ISBN 978-0-19-809930-7 .
- ^ Перейти обратно: а б Фридман, Скотт; Кришнан, Ананд; Лейдефрост, Николас (18 марта 2003 г.). «Хеш-таблицы для встраиваемых систем и систем реального времени» (PDF) . Все компьютерные науки и инженерные исследования . Вашингтонский университет в Сент-Луисе . дои : 10.7936/K7WD3XXV . Архивировано (PDF) оригинала 9 июня 2021 г. Получено 9 ноября 2021 г. - через Северо-Западного университета . факультет компьютерных наук
- ^ Литвин, Витольд (1980). «Линейное хеширование: новый инструмент для адресации файлов и таблиц» (PDF) . Учеб. 6-я конференция по очень большим базам данных . Университет Карнеги-Меллон . стр. 212–223. Архивировано (PDF) из оригинала 6 мая 2021 г. Получено 10 ноября 2021 г. через cs.cmu.edu.
- ^ Перейти обратно: а б Дейк, Том Ван (2010). «Анализ и улучшение производительности хеш-таблицы» (PDF) . Нидерланды : Университет Твенте . Архивировано (PDF) из оригинала 6 ноября 2021 г. Проверено 31 декабря 2021 г.
- ^ Лех Банаховский. «Индексы и внешняя сортировка» . pl:Польско-Японская академия компьютерных технологий . Архивировано из оригинала 26 марта 2022 года . Проверено 26 марта 2022 г.
- ^ Чжун, Лян; Чжэн, Сюэцянь; Лю, Юн; Ван, Мэнтин; Цао, Ян (февраль 2020 г.). «Максимализация коэффициента попадания в кэш при передаче данных между устройствами через сотовые сети». Китайские коммуникации . 17 (2): 232–238. дои : 10.23919/jcc.2020.02.018 . S2CID 212649328 .
- ^ Боттомли, Джеймс (1 января 2004 г.). «Понимание кэширования» . Linux-журнал . Архивировано из оригинала 4 декабря 2020 года . Проверено 16 апреля 2022 г.
- ^ Джилл Симан (2014). «Таблицы набора и хеширования» (PDF) . Техасский государственный университет . Архивировано из оригинала 1 апреля 2022 года . Проверено 26 марта 2022 г.
{{cite web}}
: CS1 maint: bot: исходный статус URL неизвестен ( ссылка ) - ^ «Таблица транспозиции — вики по шахматному программированию» . www.chessprogramming.org . Архивировано из оригинала 14 февраля 2021 года . Проверено 1 мая 2020 г.
- ^ «Типы данных и структуры данных JavaScript — JavaScript | MDN» . http://developer.mozilla.org . Проверено 24 июля 2022 г.
- ^ «Карта — JavaScript | MDN» . http://developer.mozilla.org . 20 июня 2023 г. . Проверено 15 июля 2023 г.
- ^ «Язык программирования C++ — Техническая спецификация» (PDF) . Международная организация по стандартизации . стр. 812–813. Архивировано из оригинала (PDF) 21 января 2022 года . Проверено 8 февраля 2022 г.
- ^ «Спецификация языка программирования Go» . go.dev . Проверено 1 января 2023 г.
- ^ «Урок: Реализации (Учебные руководства по Java™ > Коллекции)» . docs.oracle.com . Архивировано из оригинала 18 января 2017 года . Проверено 27 апреля 2018 г.
- ^ Чжан, Хуан; Цзя, Юнвэй (2020). «Оптимизация перефразирования Redis на основе машинного обучения» . Физический журнал: серия конференций . 1453 (1): 3. Бибкод : 2020JPhCS1453a2048Z . дои : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738 .
- ^ Джонан Шеффлер (25 декабря 2016 г.). «Выпущен Ruby 2.4: более быстрые хэши, унифицированные целые числа и улучшенное округление» . геройку.com . Архивировано из оригинала 3 июля 2019 года . Проверено 3 июля 2019 г.
- ^ «doc.rust-lang.org» . Архивировано из оригинала 8 декабря 2022 года . Проверено 14 декабря 2022 г.
- ^ «Класс HashSet (System.Collections.Generic)» . Learn.microsoft.com . Проверено 1 июля 2023 г.
- ^ дотнет-бот. «Класс словаря (System.Collections.Generic)» . Learn.microsoft.com . Проверено 16 января 2024 г.
- ^ «Пример 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