Хэш таблицы java что делать с переполнением

Обновлено: 07.07.2024

Рассмотренные в разделе 14.1 функции хеширования преобразуют ключи в адреса таблицы; второй компонент алгоритма хеширования — определение обработки случаев, когда два ключа преобразуются в один и тот же адрес. Первое, что приходит на ум — построить для каждого адреса таблицы связный список элементов, ключи которых отображаются на этот адрес. Этот подход непосредственно приводит к обобщению метода элементарного поиска в списке (см. "Таблицы символов и деревья бинарного поиска" ) в программе 14.3, в которой вместо единственного списка используются M списков.

Такой метод традиционно называется цепочками переполнения (separate chaining), поскольку конфликтующие элементы объединяются в отдельные связные списки-цепочки. Пример таких цепочек приведен на рис. 14.6. Как и в случае элементарного последовательного поиска, эти списки можно хранить упорядоченными или оставить неупорядоченными. Здесь присутствует тот же основной компромисс, что и описанный в "Таблицы символов и деревья бинарного поиска" , но для цепочек переполнения более важна не экономия времени (поскольку списки невелики), а экономия памяти (поскольку списков много).

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

Хеширование с цепочками переполнения

Здесь показан результат вставки ключей A S E R C H I N G X M P L в первоначально пустую хеш-таблицу с цепочками переполнения (неупорядоченные списки); используются хеш-значения, приведенные вверху. A попадает в список 0, затем S попадает в список 2, E — в список 0 (в его начало, чтобы время вставки было постоянным), R — в список 4 и т.д.

Программа 14.3. Хеширование с цепочками переполнения

Данная реализация таблицы символов основана на замене конструктора ST и функций search и insert в таблице символов с применением связных списков из программы 12.6 на приведенные здесь функции, а также на замене ссылки head на массив ссылок heads. Здесь используются те же рекурсивные функции поиска и удаления в списке, что и в программе 12.6, но при этом используются M списков с ведущими ссылками в heads, с использованием хеш-функции для выбора одного из списков. Конструктор устанавливает M так, что каждый список будет содержать около пяти элементов; поэтому для выполнения остальных операций требуется всего несколько проверок.

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

Лемма 14.1. Цепочки переполнения уменьшают количество сравнений, выполняемых при последовательном поиске, в M раз (в среднем) и используют дополнительный объем памяти для M ссылок.

$\blacksquare$

Средняя длина списков равна N/M . Как было описано в "Таблицы символов и деревья бинарного поиска" , можно ожидать, что успешные поиски будут доходить приблизительно до середины какого-либо списка. Неудачные поиски будут доходить до конца списка, если списки неупорядочены, и до половины списка, если они упорядочены.

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

Лемма 14.1 тривиальна, поскольку средняя длина списков равна N/M независимо от распределения элементов по спискам. Например, предположим, что все элементы попадают в первый список. Тогда средняя длина списков равна (N + 0 + 0 + . + 0)/M = N/M . Истинная причина практической пользы хеширования заключается в том, что очень высока вероятность наличия около N/M элементов в каждом списке.

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

Для читателей, которые знакомы с основами вероятностного анализа, приведем краткое изложение этих классических рассуждений. Легко видеть, что вероятность того, что данный список будет содержать к элементов, равна

$\left(\begin</p> N\\ k \end\right)\left(\dfrac\right)^\left(1-\dfrac\right)^$

$\alpha = N/M$

Здесь выбираются k из N элементов: эти к элементов попадают в данный список с вероятностью 1/M , а остальные N — k элементов не попадают в данный список с вероятностью 1 — 1/M . Обозначив , это выражение можно переписать как

$\left(\begin</p> N\\ k \end\right)\left(\dfrac\right)^\left(1-\dfrac\right)^$

что, согласно классической аппроксимации Пуассона, меньше чем

$\dfrac<\alpha^<k></p> e^>$

$t\alpha$

Отсюда следует, что вероятность наличия в списке более чем элементов меньше, чем

$\left(\dfrac<\alpha e></p> \right)^e^$

Для используемых на практике диапазонов параметров эта вероятность исключительно мала. Например, если средняя длина списков равна 20, вероятность того, что в какой-либо список попадут более 40 элементов, меньше чем e^ \approx 0,0000016$" />
.

Приведенный анализ — пример классической задачи о размещении: N шаров случайным образом вбрасываются в одну из M урн, и анализируется распределение шаров по урнам. Классический математический анализ этих задач дает и много других интересных фактов, имеющих отношение к изучению алгоритмов хеширования. Например, в соответствии с аппроксимацией Пуассона количество пустых списков близко к $" />
. Хотя более интересен факт, что среднее количество элементов, вставленных до первой коллизии, равно приблизительно \approx1,25\sqrt$" />
. Этот результат — решение классической задачи о дне рождения. Например, в соответствии с этими же рассуждениями, при M= 365 среднее количество людей, среди которых найдутся двое с одинаковыми датами рождения, приблизительно равно 24. В соответствии со вторым классическим результатом среднее количество элементов, вставленных прежде, чем в каждом списке окажется по меньшей мере по одному элементу, приблизительно равно MHM Этот результат — решение классической задачи коллекционера карточек. Например, аналогичный анализ утверждает, что при M = 1280 нужно собрать около 9898 бейсбольных карточек (купонов), прежде чем удастся заполучить по одной карточке для каждого из 40 игроков каждой из 32 команд. Данные результаты весьма показательны для рассмотренных свойств хеширования. Практически они означают, что цепочки переполнения можно успешно использовать, если хеш-функция выдает значения, близкие к случайным (см. раздел ссылок).

Обычно в реализациях цепочек переполнения значение M выбирают достаточно малым, чтобы не тратить понапрасну большие непрерывные участки памяти с пустыми ссылками, но достаточно большим, чтобы последовательный поиск в списках был наиболее эффективным методом. Гибридные методы (вроде использования бинарных деревьев вместо связных списков), вряд ли стоят рассмотрения. Как правило, можно выбирать значение M равным приблизительно одной пятой или одной десятой от ожидаемого количества ключей в таблице, чтобы каждый из списков в среднем содержал порядка 5—10 ключей. Одно из достоинств цепочек переполнения состоит в том, что этот выбор не критичен: при наличии большего, чем ожидалось, количества ключей поиски будут требовать несколько больше времени, чем если бы заранее был выбран больший размер таблицы; при наличии в таблице меньшего количества ключей поиск будет сверхбыстрым при (скорее всего) небольшом дополнительном расходе памяти. Если памяти хватает, значение M можно выбрать достаточно большим, чтобы время поиска было постоянным; если же объем памяти критичен, все-таки можно повысить производительность в M раз, выбрав максимально возможное значение M.

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

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

В общем случае хеширование не подходит для использования в приложениях, в которых требуются реализации операций АТД сортировать и выбрать. Однако хеширование часто используется в типичных ситуациях, когда необходимо использовать таблицу символов с потенциально большим количеством операций найти, вставить и удалить с последующим однократным выводом элементов в порядке их ключей. Одним из примеров такого приложения является таблица символов в компиляторе; другой пример — программа удаления повторяющихся ключей, наподобие программы 12.11. Для обработки этой ситуации в реализации цепочек переполнения в виде неупорядоченных списков нужно воспользоваться одним из методов сортировки, описанных в лекциях 6—10. В реализации с использованием упорядоченных списков сортировку можно выполнить слиянием всех списков (см. упражнение 14.23) за время, пропорциональное Nlg M .

14.16. Сколько времени может потребоваться в худшем случае для вставки N ключей в первоначально пустую таблицу с цепочками переполнения в виде (1) неупорядоченных списков и (2) упорядоченных списков?

14.17. Приведите содержимое хеш-таблицы, образованной вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустую таблицу из M = 5 списков при использовании цепочек переполнения в виде неупорядоченных списков. Для преобразования k-ой буквы алфавита в индекс таблицы используйте хеш-функцию 11k mod M .

14.18. Выполните упражнение 14.17, но для случая упорядоченных списков. Зависит ли ответ от порядка вставки элементов?

14.19. Напишите программу, которая вставляет N случайных целых чисел в таблицу размером N/100 с цепочками переполнения, а затем определяет длину самого короткого и самого длинного списков, при N = 10 3 , 10 4 , 10 5 и 10 6 .

14.20. Измените программу 14.3, чтобы исключить из нее ведущие ссылки с помощью представления таблицы символов в виде массива узлов типа node (каждый элемент таблицы является первым узлом в ее списке).

14.21. Измените программу 14.3, включив в нее для каждого элемента целочисленное поле, значение которого устанавливается равным количеству элементов в таблице на момент вставки элемента. Затем реализуйте функцию, удаляющую все элементы, для которого значение этого поля больше заданного целого числа N.

14.22. Измените реализацию функции search в программе 14.3, чтобы она выводила все элементы с ключами, равными заданному ключу, так же, как это сделано в функции show.

14.23. Разработайте реализацию таблицы символов с цепочками переполнения в виде упорядоченных списков, которая включает деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить, объединить, выбрать и сортировать для АТД первого класса таблицы символов при поддержке клиентских дескрипторов (см. упражнения 12.6 и 12.7).

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

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

image

Мотивация использовать хеш-таблицы

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

Контейнер \ операция insert remove find
Array O(N) O(N) O(N)
List O(1) O(1) O(N)
Sorted array O(N) O(N) O(logN)
Бинарное дерево поиска O(logN) O(logN) O(logN)
Хеш-таблица O(1) O(1) O(1)

Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях

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

Понятие хеш-таблицы

Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

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

Теперь стало понятно, почему же это именно хеш-таблица.

Проблема коллизии

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

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

Решения проблемы коллизии методом двойного хеширования

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

Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g.

Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

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

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

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

Помня о данной проблеме построим наш класс.

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

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

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

Но к чему слова, код все разъяснит:

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

Я не понимаю, как возникают коллизии в хэш-таблице и способ их разрешения.
Но у меня есть догадка, что коллизия возникает, когда хэш-функция вычисляет хэш-значение за пределами int (то есть максимальное число в int - это примерно 2 млрд, а вычислилось, например, 3 млрд).

Вернее, способ я понимаю - это связный список, если возникает коллизия, но как оно внутри работает вообще не понимаю.

Допустим: вот у меня хэш-функция выдала значение 153, потом еще 153, но последнее 153 получилось в результате переполнения числа int (в реале, допустим, было примерно 2 млрд 153). Компьютер смотрит одинаково на числа 153 и примерно 2 млрд 153. Но! Меня удивляет, что коллизия всегда разрешается 100% правильно.

То есть в массиве под индексом 153 лежит связный список. Ключ = равен индексу массива. Там есть key = 153: Masha и ссылка на следующий элемент key = 153: Gena .

Как компьютер понимает, когда ему надо отдать значение Masha , а когда Gena ?


50.3k 153 153 золотых знака 54 54 серебряных знака 211 211 бронзовых знаков

Я не понимаю как возникают коллизии в хэш таблице и способ их разрешения

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

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

Элемент массива - список. Операция поиска пробегает по списку в поиске уже не хэша, а именно ключа. Например, в списке по индексу 153 есть (Misha)-(Gena).

Вопрос - есть ли Gena в таблице? Вычисляется хэш от "Gena", результат 153. Бежим по списку в элементе массива 153. Первый элемент списка равен "Gena"? Нет, он равен "Misha". Второй элемент? Да. Ответ - "Gena" в хэш-таблице есть. Аналогично со вставкой/удалением.

Руководство по пониманию структуры хэш-таблицы в Java.

1. Обзор

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

2. Когда использовать хэш-таблицу

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

Следовательно, Hashtable (или HashMap ) имеет смысл. Слова будут ключами в Hashtable , так как они должны быть уникальными. Определения, с другой стороны, будут значениями.

3. Пример использования

Давайте продолжим пример со словарем. Мы смоделируем Word в качестве ключа:

Допустим, значения являются Строками . Теперь мы можем создать Хэш-таблицу :

Во-первых, давайте добавим запись:

Кроме того, чтобы получить запись:

Наконец, давайте удалим запись:

В классе есть еще много методов, и мы опишем некоторые из них позже.

Но сначала давайте поговорим о некоторых требованиях к ключевому объекту.

4. Важность хэш-кода()

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

Но почему бы не хранить элементы последовательно, добавляя новые элементы в конец массива?

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

4.1. Таблица Прямых Адресов

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

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

Но здесь у нас есть две проблемы:

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

Метод hashCode() решает первую проблему.

Логика манипулирования данными в Хэш-таблице решает вторую проблему.

Давайте обсудим это подробнее.

4.2. Метод hashCode()

Любой объект Java наследует метод hashCode() , который возвращает значение int . Это значение вычисляется по адресу внутренней памяти объекта. По умолчанию hashCode() возвращает различные целые числа для различных объектов.

Таким образом, любой ключевой объект может быть преобразован в целое число с помощью hashCode() . Но это целое число может быть большим.

4.3. Сокращение диапазона

методы get() , put() и remove() содержат код, который решает вторую проблему – уменьшение диапазона возможных целых чисел.

Формула вычисляет индекс для ключа:

Как мы видим, индекс-это напоминание о делении хэша на размер массива . Обратите внимание, что одинаковые хэш-коды дают один и тот же индекс.

4.4. Столкновения

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

Такая структура данных называется хэш-таблицей с цепочкой.

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

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

Поэтому важно уменьшить количество столкновений. Чем больше массив, тем меньше вероятность столкновения. Коэффициент загрузки определяет баланс между размером массива и производительностью. По умолчанию он равен 0,75, что означает, что размер массива удваивается, когда 75% ячеек не становятся пустыми. Эта операция выполняется методом rehash () .

Но вернемся к ключам.

4.6. Переопределение equals() и хэш-кода()

Когда мы помещаем запись в Hashtable и извлекаем ее из нее, мы ожидаем, что значение может быть получено не только с тем же экземпляром ключа, но и с равным ключом:

Чтобы установить правила равенства, мы переопределяем ключ равняется() метод:

Но если мы не переопределим hashCode() при переопределении equals () , то два одинаковых ключа могут оказаться в разных сегментах, потому что Hashtable вычисляет индекс ключа, используя его хэш-код.

Давайте внимательно рассмотрим приведенный выше пример. Что произойдет, если мы не переопределим hashCode() ?

  • Здесь задействованы два экземпляра Word – первый предназначен для размещения записи, а второй-для получения записи. Хотя эти экземпляры равны, их метод hashCode() возвращает разные числа
  • Индекс для каждого ключа рассчитывается по формуле из раздела 4.3. В соответствии с этой формулой различные хэш-коды могут создавать разные индексы
  • Это означает, что мы помещаем запись в одно ведро, а затем пытаемся извлечь ее из другого ведра. Такая логика ломается Hashtable

Равные ключи должны возвращать равные хэш-коды, поэтому мы переопределяем Хэш-код() метод:

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

Кроме того, обратите внимание, что нас не волнуют ключи String , Integer , Long или другого типа оболочки. Оба метода equal() и hashCode() уже переопределены в классах-оболочках.

5. Итерация Хэш-Таблиц

Существует несколько способов итерации Хэш-таблиц. В этом разделе мы поговорим о них и объясним некоторые последствия.

5.1. Быстрая неудача: Итерация

Быстрая итерация означает, что если Хэш-таблица будет изменена после создания ее итератора , то будет вызвано исключение ConcurrentModificationException . Давайте продемонстрируем это.

Сначала мы создадим Хэш-таблицу и добавим в нее записи:

Во-вторых, мы создадим Итератор :

И в-третьих, мы изменим таблицу:

Теперь, если мы попытаемся выполнить итерацию по таблице, мы получим исключение ConcurrentModificationException :

ConcurrentModificationException помогает найти ошибки и, таким образом, избежать непредсказуемого поведения, когда, например, один поток перебирает таблицу, а другой пытается одновременно изменить ее.

5.2. Не Подведите Быстро: Перечисление

Перечисление в Хэш-таблице не является быстрым. Давайте рассмотрим пример.

Во-первых, давайте создадим Хэш-таблицу и добавим в нее записи:

Во-вторых, давайте создадим Перечисление :

В-третьих, давайте изменим таблицу:

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

5.3. Непредсказуемый Порядок итераций

Кроме того, обратите внимание, что порядок итераций в Hashtable непредсказуем и не соответствует порядку, в котором были добавлены записи.

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

Следовательно, давайте добавим несколько записей и проверим вывод:

6. Хэш-таблица против Хэш-карта

Hashtable и HashMap обеспечивают очень похожую функциональность.

Оба они обеспечивают:

  • Отказоустойчивая итерация
  • Непредсказуемый порядок итераций

Но есть и некоторые отличия:

  • HashMap не предоставляет никакого перечисления, в то время какHashtable обеспечивает не быстрое перечисление
  • Hashtable не допускает null ключи и null значения, в то время как HashMap допускает один null ключ и любое количество null значений
  • Методы Hashtable синхронизируются, в то время как методы HashMaps не синхронизируются

7. API Hashtable в Java 8

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

7.1. getOrDefault()

7.2. путИфАбсент()

7.3. логическое удаление()

Наконец, в то время как старый метод remove() возвращает значение, новый метод возвращает boolean .

7.4. заменить()

7.5. computeIfAbsent()

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

Следовательно, приведенная выше строка эквивалентна:

7.6. computeIfPresent()

Этот метод аналогичен методу replace () . Но, опять же, replace() принимает значение напрямую, а computeIfPresent() принимает функцию отображения. Он вычисляет значение внутри блока if , поэтому он более эффективен.

Допустим, нам нужно изменить определение:

Следовательно, приведенная выше строка эквивалентна:

7.7. вычисление()

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

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

Наконец, давайте убедимся, что на столе есть две кошки, две собаки, одна птица и две мыши:

7.8. слияние()

Существует еще один способ решения вышеуказанной задачи:

7.9. foreach()

Это новый способ перебора записей. Давайте распечатаем все записи:

7.10. Замените все()

Кроме того, мы можем заменить все значения без итерации:

8. Заключение

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

Кроме того, мы рассмотрели, что такое коллизии и что такое коэффициент загрузки в Hashtable. Кроме того, мы узнали, зачем переопределять equals() и hashCode() для ключевых объектов.

Наконец, мы говорили о свойствах Хэш-таблицы и специфичном API Java 8.

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

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

Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .

Коллизии

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

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

  • Метод цепочек.
  • Метод открытой адресации: линейное и квадратичное зондирование.

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

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

Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .

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

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

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

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

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

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

h(k, i) = (h′(k) + i) mod m ,

Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть, значение i увеличивается линейно.

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

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

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

  • c1 и c2 — положительные вспомогательные константы,
  • i =

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

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

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

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

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

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

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

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

Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть, значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.

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

  • kA mod 1 отделяет дробную часть kA ,
  • ⌊ ⌋ округляет значение
  • A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.

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

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

Читайте также: