Что такое хэш таблица в java
Руководство по пониманию структуры хэш-таблицы в Java.
3. Как отсортировать значения мапы
Здесь стоит использовать подход, аналогичный первому для ключей — получать список значений и сортировать их в списке: И лямбда для этого выглядит так:
7.2. путИфАбсент()
Допустим, нам нужно вставить слово “кошка “ , только если его еще нет в словаре.
«Хорошие» хеш-функции
«Хорошие» хеш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.
Ниже мы рассмотрим различные методы определения «качества» хэш-функций.
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. Универсальное хеширование
В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.
Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.
5.3. Непредсказуемый Порядок итераций
Кроме того, обратите внимание, что порядок итераций в Hashtable непредсказуем и не соответствует порядку, в котором были добавлены записи.
Это понятно, поскольку он вычисляет каждый индекс, используя хэш-код ключа. Кроме того, время от времени происходит перестановка, перестраивая порядок структуры данных.
Следовательно, давайте добавим несколько записей и проверим вывод:
7. API Hashtable в Java 8
Java 8 представила новые методы, которые помогают сделать наш код чище. В частности, мы можем избавиться от некоторых блоков if . Давайте продемонстрируем это.
0. Как перебрать все значения Map
Перебор значений — самая частая операция, которую вы выполняете с мапами. Все пары (ключ-значение) хранятся во внутреннем интерфейсе Map.Entry, а чтобы получить их, нужно вызвать метод entrySet() . Он возвращает множество (Set) пар, которые можно перебрать в цикле:
7.10. Замените все()
Кроме того, мы можем заменить все значения без итерации:
4.2. Метод hashCode()
Любой объект Java наследует метод hashCode() , который возвращает значение int . Это значение вычисляется по адресу внутренней памяти объекта. По умолчанию hashCode() возвращает различные целые числа для различных объектов.
Таким образом, любой ключевой объект может быть преобразован в целое число с помощью hashCode() . Но это целое число может быть большим.
1. Как конвертировать Map в List
- keySet() — возвращает множество(Set) ключей;
- values() — возвращает коллекцию(Collection) значений;
- entrySet() — возвращает множество(Set) наборов “ключ-значение”.
7.1. getOrDefault()
Допустим, нам нужно получить определение слова “собака “ и присвоить его переменной, если она находится в таблице. В противном случае назначьте переменной “не найдено”.
Коллизии
Когда хеш-функция генерирует один индекс для нескольких ключей, возникает конфликт: неизвестно, какое значение нужно сохранить в этом индексе. Это называется коллизией хеш-таблицы.
Есть несколько методов борьбы с коллизиями:
- метод цепочек;
- метод открытой адресации: линейное и квадратичное зондирование.
1. Метод цепочек
Суть этого метода проста: если хеш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка.
Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .
Удаление элементов
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — "А может оно и не надо?").
Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.
Теперь удалим те же 150 элементов, и снова замерим.
7.7. вычисление()
Теперь мы решим еще одну задачу. Допустим , у нас есть массив String , где элементы не являются уникальными. Кроме того, давайте подсчитаем, сколько вхождений строки мы можем получить в массиве. Вот массив:
Кроме того, мы хотим создать Хэш-таблицу , которая содержит животное в качестве ключа и количество его вхождений в качестве значения.
Наконец, давайте убедимся, что на столе есть две кошки, две собаки, одна птица и две мыши:
5. Итерация Хэш-Таблиц
Существует несколько способов итерации Хэш-таблиц. В этом разделе мы поговорим о них и объясним некоторые последствия.
4.5. Коэффициент нагрузки
Нетрудно догадаться, что столкновения замедляют операции с элементами. Чтобы получить запись, недостаточно знать ее индекс, но нам нужно пройти по списку и выполнить сравнение с каждым элементом.
Поэтому важно уменьшить количество столкновений. Чем больше массив, тем меньше вероятность столкновения. Коэффициент загрузки определяет баланс между размером массива и производительностью. По умолчанию он равен 0,75, что означает, что размер массива удваивается, когда 75% ячеек не становятся пустыми. Эта операция выполняется методом rehash () .
Но вернемся к ключам.
7.9. foreach()
Это новый способ перебора записей. Давайте распечатаем все записи:
8. Заключение
В этой статье мы описали назначение структуры хэш-таблицы и показали, как усложнить структуру таблицы прямых адресов, чтобы получить ее.
Кроме того, мы рассмотрели, что такое коллизии и что такое коэффициент загрузки в Hashtable. Кроме того, мы узнали, зачем переопределять equals() и hashCode() для ключевых объектов.
Наконец, мы говорили о свойствах Хэш-таблицы и специфичном API Java 8.
Привет! Сегодня мы дадим ответы на самые распространенные вопросы о Map, но для начала давай вспомним, что это такое. Map — это структура данных, которая содержит набор пар “ключ-значение”. По своей структуре данных напоминает словарь, поэтому ее часто так и называют. В то же время, Map является интерфейсом, и в стандартном jdk содержит основные реализации: Hashmap, LinkedHashMap, Hashtable, TreeMap. Самая используемая реализация — Hashmap, поэтому и будем ее использовать в наших примерах. Вот так выглядит стандартное создание и заполнение мапы: А так — получение значений по ключу: Если все из вышесказанного понятно, приступим к нашим ответам на популярные вопросы!
7.4. заменить()
Допустим, нам нужно заменить определение “кошка”, но только в том случае, если его старое определение – “маленькое одомашненное плотоядное млекопитающее”.
4.4. Столкновения
Кроме того, даже разные хэш-коды могут создавать один и тот же индекс . Мы называем это столкновением. Для разрешения коллизий Хэш-таблица хранит Связанный список пар ключ-значение.
Такая структура данных называется хэш-таблицей с цепочкой.
Создание объекта
- table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
- loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
- threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
- size — Количество элементов HashMap-а;
Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Resize и Transfer
Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.
Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.
Если в исходный hashmap добавить, скажем, еще 15 элементов, то в результате размер будет увеличен и распределение элементов изменится.
1. Обзор
Hashtable – это самая старая реализация структуры данных хэш-таблицы в Java. |/HashMap – это вторая реализация, которая была представлена в JDK 1.2.
Оба класса предоставляют схожие функциональные возможности, но есть и небольшие различия, которые мы рассмотрим в этом уроке.
7.5. computeIfAbsent()
Этот метод аналогичен putIfAbsent() . Но putIfAbsent() принимает значение напрямую, а computeIfAbsent() принимает функцию отображения. Он вычисляет значение только после проверки ключа, и это более эффективно, особенно если значение трудно получить.
Следовательно, приведенная выше строка эквивалентна:
Псевдокод операций
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
Префиксное дерево
Префиксное дерево (trie) — структура данных, в которой путь от корня дерева к листу (последнему элементу) дерева определяет строку.
Слово «trie» происходит от слова «retrieval» (извлечение), но обычно произносится как «try». Для наших целей узлы в trie являются массивами. Мы можем использовать trie для хранения словаря слов, как показано на этой диаграмме.
В этом trie каждый индекс в массиве обозначает букву алфавита. Каждый из этих индексов также указывает на другой массив букв. Сверху мы сохраняем имена известных ученых, например. Менделя, Менделеева, Павлова, Пастера и Тьюринга. Символ Δ обозначает конец имени. Мы должны следить за тем, где заканчиваются слова, так что если одно слово действительно содержит другое слово (например, Менделеев и Мендель), мы знаем, что оба слова существуют. В коде символ Δ может быть логическим флагом в каждом узле.
Таким образом, при прохождении дерева сверху вниз формируются слова.
Описание структуры узла префиксного дерева — ниже. Заметьте, мы фактически не сохраняем слова в trie, мы просто сохраняем последовательность указателей и логическое значение.
Пример работы с префиксным деревом
Есть следующего вида префиксальное дерево, в котором есть слова bat и zoom :
Давайте рассмотрим пример поиска ключа «bat» в этом trie. Переходя по последовательным ссылкам сверху вниз, пока не встретим маркер конца слова, получим слово bat:
Мы начнем поиск в корневом узле. Берём первую букву нашего ключа «b» и ищем соответствующее место в нашем дочернем массиве. Мы рассмотрим второй индекс — индекс 1 — для «b». В общем случае, если у нас есть алфавитный символ c, мы можем определить соответствие в дочернем массиве, используя такую формулу:
В этом случае указатель в нашем дочернем массиве с индексом 1 не является NULL, поэтому мы продолжим поиск ключа «bat». Если мы однажды наткнёмся на указатель NULL в правильном месте дочернего массива, тогда, смотря на ключ, мы должны были бы сказать, что мы ничего не смогли найти для этого ключа.
Теперь мы возьмем вторую букву нашего ключа «a» и продолжим следовать по указателям, пока не дойдем до конца нашего ключа.
Теперь (сюрприз!) мы возьмем третью букву нашего ключа, «t», и продолжим идти по указателям, пока не дойдем до конца нашего ключа.
Если мы дойдем до конца ключа, и не попадём в «тупик» (NULL-указатель), как здесь, то нам остается только проверить еще одну вещь: был ли этот ключ фактически сохранен в trie? На нашей диаграмме это обозначается галочкой, означающей, что bool is_word = true .
Обратите внимание, на то, что ключ «zoo» отсутствует в словаре, хотя мы смогли дойти до конца этого ключа, не попав в тупик.
Точно так же, если бы мы попытались найти ключ «bath», индекс массива массива от второго до последнего узла, соответствующий букве Н, содержал бы указатель NULL, поэтому «bath» отсутствует в словаре.
Давайте рассмотрим, как можно вставить элемент в префиксное дерево. В некотором смысле процесс вставки похож на процесс поиска.
Для того чтобы вставить слово zoo в массив, необходимо начать с корневого узла, следуя по указателям, соответствующим буквам нашего ключа, проходим по списку и устанавливаем маркер:
К счастью, мы можем следить за указателями до конца ключа.
Поскольку «zoo» является префиксом слова «zoom», которое хранится в нашем словаре, нам не нужно выделять новые узлы. Мы можем просто установить is_word в true на соответствующем узле.
А если бы мы захотели добавить в дерево слово bath, то, пройдя по всем указателям, мы бы зашли в тупик прежде, чем добрались до конца ключа.
Поэтому нам нужно определить один новый узел для каждой оставшейся буквы нашего ключа.
Затем нам нужно будет сделать индекс h предыдущего узла ссылкой на этот новый узел. То есть в последнем элементе слова bat создаем ссылку, указывающую на букву h:
Наконец, мы устанавливаем значение true для is_word bool нового узла. Если предположить, что длина ключа ограничена фиксированной константой, ясно, что и поиск, и вставка выполняются за фиксированное время. Обратите внимание, что количество элементов, хранящихся в trie, не влияет на время поиска или вставки, влияние оказывает только длина ключа. В отличие от этого добавление записей в хеш-таблицу имеет тенденцию замедления поиска в будущем.
Естественно, благоприятная асимптотическая сложность привлекает, однако не стоит обольщаться, на практике всё не так радужно. Мы также должны учитывать, что для хранения слова в trie нам нужно, в худшем случае, несколько узлов, пропорциональных длине самого слова. Попытки, как правило, требуют много места, и в этом отличие этой структуры данных от, скажем, хеш-таблиц, где нам нужен только один новый узел для хранения пары ключ-значение.
В хеш-таблице обработка новых индексов производится при помощи ключей. А элементы, связанные с этим ключом, сохраняются в индексе. Этот процесс называется хешированием.
Пусть k — ключ, а h(x) — хеш-функция.
Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .
2. Как отсортировать ключи мапы
Поместить Map.Entry в список и отсортировать его, используя Comparator.
В компараторе будем сравнивать исключительно ключи пар:
Если разобрался с лямбдами, эту запись можно существенно сократить:
Использовать SortedMap , а точнее, ее реализацию — TreeMap , которая в конструкторе принимает Comparator. Данный компаратор будет применяться к ключам мапы, поэтому ключами должны быть классы, реализующие интерфейс Comparable :
И, конечно, все можно переписать, используя лямбды:
В отличие от первого способа, используя SortedMap, мы всегда будем хранить данные в отсортированном виде.
5. Как создать двунаправленную мапу
Иногда появляется необходимость использовать структуру данных, в которой и ключи, и значения будут уникальными, то есть мапа будет содержать пары “ключ-ключ”. Такая структура данных позволяет создать "инвертированный просмотр/поиск" по мапе. То есть, мы можем найти ключ по его значению.Эту структуру данных называют двунаправленной мапой, которая, к сожалению, не поддерживается JDK. Но, к счастью, ее реализацию можно найти в библиотеках Apache Common Collections или Guava. Там она называется BidiMap и BiMap соответственно. Эти реализации вводят ограничения на уникальность ключей и значений. Таким образом получаются отношения one-to-one.
Хеш-таблица — это структура данных для хранения пар ключей и их значений. По сути она представляет собой массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Важное свойство хеш-таблицы: поиск, вставка и удаление элементов из таблицы выполняются за фиксированное время, то есть О(1), то есть они нужны тогда, когда максимально важна скорость этих операций.
В примере на картинке позиция каждого слова в хеш-таблице зависит от порядкового номера первой буквы этого слова в английском алфавите.
Хеш-функция — это функция, которая принимает в качестве аргумента какой-то элемент (который нужно вставить в хеш-таблицу), а в результате выдает позицию заданного элемента в хеш-таблицы.
По сути она сопоставляет ключи индексам массива. Например, на картинке выше мы видим, что хеш-функция сопоставила ключ ‘banana’ с индексом 1.
Но что происходит под капотом?
Хеш-функция принимает ключ на вход и вычисляет индекс массива, исходя из внутренних свойств этого ключа.
Сначала вам нужно использовать хеш-функцию, чтобы определить, где в хеш-таблице хранится данный ключ. Затем нужно будет использовать ту же самую хеш-функцию, чтобы определить, где в хеш-таблице искать данный ключ. По этой причине важно, чтобы хеш-функция вела себя последовательно и выводила один и тот же индекс для одинаковых входных данных.
Примеры хеш-функций: порядковый номер первой буквы слова в алфавите, остаток от деления на 13 и тому подобное.
Ниже приведены код хеш-функции на основе первой буквы в строке
4.3. Сокращение диапазона
методы get() , put() и remove() содержат код, который решает вторую проблему – уменьшение диапазона возможных целых чисел.
Формула вычисляет индекс для ключа:
Где tab.length – размер массива, а hash – число, возвращаемое методом ключа hashCode () .
Как мы видим, индекс-это напоминание о делении хэша на размер массива . Обратите внимание, что одинаковые хэш-коды дают один и тот же индекс.
7.3. логическое удаление()
Допустим, нам нужно удалить слово “кошка”, но только если это определение “животное”.
Наконец, в то время как старый метод remove() возвращает значение, новый метод возвращает boolean .
2. Когда использовать хэш-таблицу
Допустим, у нас есть словарь, где каждое слово имеет свое определение. Кроме того, нам нужно быстро получать, вставлять и удалять слова из словаря.
Следовательно, Hashtable (или HashMap ) имеет смысл. Слова будут ключами в Hashtable , так как они должны быть уникальными. Определения, с другой стороны, будут значениями.
3. Пример использования
Давайте продолжим пример со словарем. Мы смоделируем Word в качестве ключа:
Допустим, значения являются Строками . Теперь мы можем создать Хэш-таблицу :
Во-первых, давайте добавим запись:
Кроме того, чтобы получить запись:
Наконец, давайте удалим запись:
В классе есть еще много методов, и мы опишем некоторые из них позже.
Но сначала давайте поговорим о некоторых требованиях к ключевому объекту.
5.2. Не Подведите Быстро: Перечисление
Перечисление в Хэш-таблице не является быстрым. Давайте рассмотрим пример.
Во-первых, давайте создадим Хэш-таблицу и добавим в нее записи:
Во-вторых, давайте создадим Перечисление :
В-третьих, давайте изменим таблицу:
Теперь, если мы пройдем по таблице, она не вызовет исключения:
7.8. слияние()
Существует еще один способ решения вышеуказанной задачи:
Второй аргумент, 1 , – это значение, которое сопоставляется с ключом, если ключ еще не находится в таблице. Если ключ уже есть в таблице, то мы вычисляем его как старое значение+1 .
6. Хэш-таблица против Хэш-карта
Hashtable и HashMap обеспечивают очень похожую функциональность.
Оба они обеспечивают:
- Отказоустойчивая итерация
- Непредсказуемый порядок итераций
Но есть и некоторые отличия:
- HashMap не предоставляет никакого перечисления, в то время какHashtable обеспечивает не быстрое перечисление
- Hashtable не допускает null ключи и null значения, в то время как HashMap допускает один null ключ и любое количество null значений
- Методы Hashtable синхронизируются, в то время как методы HashMaps не синхронизируются
7.6. computeIfPresent()
Этот метод аналогичен методу replace () . Но, опять же, replace() принимает значение напрямую, а computeIfPresent() принимает функцию отображения. Он вычисляет значение внутри блока if , поэтому он более эффективен.
Допустим, нам нужно изменить определение:
Следовательно, приведенная выше строка эквивалентна:
4. В чем разница между HashMap, TreeMap, и Hashtable
Порядок элементов. HashMap и Hashtable не гарантируют, что элементы будут храниться в порядке добавления. Кроме того, они не гарантируют, что порядок элементов не будет меняться со временем. В свою очередь, TreeMap гарантирует хранение элементов в порядке добавления или же в соответствии с заданным компаратором.
Допустимые значения. HashMap позволяет иметь ключ и значение null, HashTable — нет. TreeMap может использовать значения null только если это позволяет компаратор. Без использования компаратора (при хранении пар в порядке добавления) значение null не допускается.
Синхронизация. Только HashTable синхронизирована, остальные — нет. Если к мапе не будут обращаться разные потоки, рекомендуется использовать HashMap вместо HashTable.
Коллизии (столкновения)
Ситуация, когда для разных ключей получается одно и то же хеш-значение, называется коллизией или столкновением. Например, в изображенную ранее таблицу на основе первых символов строки мы попробуем добавить новое слово berry.
Индекс Berry ссылается на 1, как и банан. Это пример столкновения, результат хеширования двух ключей к одному индексу. Даже если ваш хеш-табличка больше, чем ваш набор данных, и вы выбрали хорошую хеш-функцию, вам нужен план борьбы со столкновениями, если и когда они возникнут.
Полученное новое значение также нужно куда-то записать, и для этого нужно определить, куда именно оно будет записано. Это называется решением коллизии.
Двумя распространенными методами борьбы с коллизиями являются линейное зондирование и метод цепочек.
Линейное зондирование заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция.
При методе цепочек, каждая ячейка хеш-таблицы — это список значений. При возникновении коллизии, новое значение просто добавляется в список в ту же ячейку таблицы.
5.1. Быстрая неудача: Итерация
Быстрая итерация означает, что если Хэш-таблица будет изменена после создания ее итератора , то будет вызвано исключение ConcurrentModificationException . Давайте продемонстрируем это.
Сначала мы создадим Хэш-таблицу и добавим в нее записи:
Во-вторых, мы создадим Итератор :
И в-третьих, мы изменим таблицу:
Теперь, если мы попытаемся выполнить итерацию по таблице, мы получим исключение ConcurrentModificationException :
ConcurrentModificationException помогает найти ошибки и, таким образом, избежать непредсказуемого поведения, когда, например, один поток перебирает таблицу, а другой пытается одновременно изменить ее.
4. Важность хэш-кода()
Для использования в качестве ключа в Hashtable объект не должен нарушать контракт hashCode (). Короче говоря, равные объекты должны возвращать один и тот же код. Чтобы понять, почему, давайте посмотрим, как организована хэш-таблица.
Хэш-таблица использует массив. Каждая позиция в массиве представляет собой “ведро”, которое может быть либо нулевым, либо содержать одну или несколько пар ключ-значение. Рассчитывается индекс каждой пары.
Но почему бы не хранить элементы последовательно, добавляя новые элементы в конец массива?
Дело в том, что найти элемент по индексу намного быстрее, чем последовательно перебирать элементы со сравнением. Следовательно, нам нужна функция, которая сопоставляет ключи с индексами.
4.1. Таблица Прямых Адресов
Простейшим примером такого сопоставления является таблица прямых адресов. Здесь ключи используются в качестве индексов:
Ключи уникальны, то есть каждое ведро содержит одну пару ключ-значение. Этот метод хорошо работает для целочисленных ключей, когда возможный диапазон их достаточно мал.
Но здесь у нас есть две проблемы:
- Во-первых, наши ключи-это не целые числа, а объекты Word
- Во-вторых, если бы они были целыми числами, никто не гарантировал бы, что они маленькие. Представьте, что ключи 1, 2 и 1000000. У нас будет большой массив размером 1000000 всего с тремя элементами, а остальное будет потрачено впустую
Метод hashCode() решает первую проблему.
Логика манипулирования данными в Хэш-таблице решает вторую проблему.
Давайте обсудим это подробнее.
4.6. Переопределение equals() и хэш-кода()
Когда мы помещаем запись в Hashtable и извлекаем ее из нее, мы ожидаем, что значение может быть получено не только с тем же экземпляром ключа, но и с равным ключом:
Чтобы установить правила равенства, мы переопределяем ключ равняется() метод:
Но если мы не переопределим hashCode() при переопределении equals () , то два одинаковых ключа могут оказаться в разных сегментах, потому что Hashtable вычисляет индекс ключа, используя его хэш-код.
Давайте внимательно рассмотрим приведенный выше пример. Что произойдет, если мы не переопределим hashCode() ?
- Здесь задействованы два экземпляра Word – первый предназначен для размещения записи, а второй-для получения записи. Хотя эти экземпляры равны, их метод hashCode() возвращает разные числа
- Индекс для каждого ключа рассчитывается по формуле из раздела 4.3. В соответствии с этой формулой различные хэш-коды могут создавать разные индексы
- Это означает, что мы помещаем запись в одно ведро, а затем пытаемся извлечь ее из другого ведра. Такая логика ломается Hashtable
Равные ключи должны возвращать равные хэш-коды, поэтому мы переопределяем Хэш-код() метод:
Обратите внимание , что также рекомендуется, чтобы не равные ключи возвращали разные хэш-коды , иначе они окажутся в одном и том же ведре. Это ударит по производительности, следовательно, потеряет некоторые преимущества хэш-таблицы .
Кроме того, обратите внимание, что нас не волнуют ключи String , Integer , Long или другого типа оболочки. Оба метода equal() и hashCode() уже переопределены в классах-оболочках.
Итераторы
HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:
Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).
Добавление элементов
-
Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value) (вариант с добавлением null-ключа рассмотрим чуть позже).
Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).
В моем случае, для ключа со значением ''0'' метод hashCode() вернул значение 48, в итоге:
При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:
-
Пропускается, ключ не равен null
-
Все элементы цепочки, привязанные к table[0], поочередно просматриваются в поисках элемента с ключом null. Если такой элемент в цепочке существует, его значение перезаписывается.
-
Пропускается, ключ не равен null
Читайте также: