Jump to content

Хэш-таблица

(Перенаправлено с карты хеша )

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

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

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

В хорошо размерной хеш-таблице средняя временная сложность каждого поиска не зависит от количества элементов, хранящихся в таблице. Многие конструкции хэш-таблиц также допускают произвольные вставки и удаления пар ключ-значение с амортизированной постоянной средней стоимостью за операцию. [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]

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

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

Открытая адресация — это еще один метод разрешения коллизий, при котором каждая запись записи сохраняется в самом массиве сегментов, а разрешение хэша выполняется посредством зондирования . Когда необходимо вставить новую запись, сегменты проверяются, начиная с хешированного слота и продолжая некоторую тестовую последовательность , пока не будет найден незанятый слот. При поиске записи сегменты сканируются в одной и той же последовательности, пока не будет найдена либо целевая запись, либо не найден неиспользуемый слот массива, что свидетельствует о неудачном поиске. [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]

См. также

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

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b62cb31ec383d8d8d620465bb7745267__1722041280
URL1:https://arc.ask3.ru/arc/aa/b6/67/b62cb31ec383d8d8d620465bb7745267.html
Заголовок, (Title) документа по адресу, URL1:
Hash table - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)