Что такое коллизия в программировании

Коллизия хэш-функции

Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H(x) = H(y).

Содержание

Коллизии криптографических хеш-функций

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

Для криптографических хеш-функций различают два типа стойкости к нахождению коллизий:

Также ключевым свойством хеш-функций является их необратимость:

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

Разрешение коллизий в хеш-таблицах

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

Источник

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

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

Содержание

Разрешение коллизий с помощью цепочек [ править ]

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

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

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

Стратегии поиска [ править ]

При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

Проверка наличия элемента в таблице [ править ]

Проверка осуществляется аналогично добавлению: мы проверяем ячейку [math]i[/math] и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.

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

Проблемы данных стратегий [ править ]

Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.

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

Удаление элемента без пометок [ править ]

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на [math]q[/math] позиций назад. При этом:

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

Хеш-таблицу считаем зацикленной

Вариант с зацикливанием мы не рассматриваем, поскольку если [math]q[/math] взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций

Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.

Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце [math]\mathrm[/math] (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.

Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на [math]q[/math] позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.

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

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

Принцип двойного хеширования [ править ]

[math]\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))\gt p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))[/math]

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

[math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

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

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

[math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 [/math]

[math] h_1(k) = k \bmod 13 [/math]

[math] h_2(k) = 1 + k \bmod 11 [/math]

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

Простая реализация [ править ]

Реализация с удалением [ править ]

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

Источник

Хэш-таблицы

В этой статье вы познакомитесь с хэш-таблицами и увидите примеры их реализации в Cи, C++, Java и Python.

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

Хэширование (хэш-функция)

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

Пусть k — ключ, а h(x) — хэш-функция.

Коллизии

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

Есть несколько методов борьбы с коллизиями:

1. Метод цепочек

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

Псевдокод операций

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

Существует несколько видов открытой адресации:

a) Линейное зондирование

Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.

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

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:

c) Двойное хэширование

h(k, i) = (h1(k) + ih2(k)) mod m

«Хорошие» хэш-функции

«Хорошие» хэш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.

Ниже мы рассмотрим различные методы определения «качества» хэш-функций.

1. Метод деления

Если k — ключ, а m — размер хэш-таблицы, то хэш-функция h() вычисляется следующим образом:

2. Метод умножения

3. Универсальное хеширование

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

Источник

Box2d: анатомия коллизий

Что такое коллизии?

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

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

Получении информации о столкновении

Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.

Проверка списка контактов

В любой момент можно перебрать все контакты мира (имеется в виду b2World)

или получить контакты тела определенного объекта

Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.

Слушатели контактов

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

Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование «обратных вызовов при коллизиях» рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.

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

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

Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.

Столкновение шаг за шагом.

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

Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.

AABB фикстур начинают перекрываться

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

Результат: контакт существует, но IsTouching() возвращает ложь

Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…

Фикстуры начинают пересекаться.

Приблизив верхний угол квадрата, можно увидеть переход, как на следующих изображениях

Шаг n

Шаг n+1 (не bullet-объекты)

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

Шаг n+1 (треугольник — bullet-объект)

Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули 🙂 тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.

Точки столкновения и нормаль

К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.

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

Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.

Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:

Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.

Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:

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

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

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

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

Реакция на столкновение

( (b2Contact::Update, b2Island::Report))
Шаг_столкновения

Шаг_столкновения + 1

Шаг_столкновения + 1

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

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

Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:

Результат: PreSolve and PostSolve вызываются несколько раз

PreSolve and PostSolve

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

В PreSolve можно сделать следующие настройки объекта контакта:

Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.

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

Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне 😀

PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье » sticky projectiles» содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.

Возвращаемся к сценарию столкновения

Фикстуры больше не перекрываются

(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.

(увеличенный масштаб)

AABB фикстур не перекрываются

(b2ContactManager::Collide)

Результат: контакт удаляется из списка контактов мира и тела.

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

Источник

Alex tools

Хэш-таблица: разрешение коллизий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отдельное сцепление с другими структурами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кукушечное хэширование

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

Hopscotch хэширование

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

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

Хэширование Робина Гуда

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

Двухвариантное хэширование

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

Источник