Как работает hashmap в java

Как работает HashMap?

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

Нюансы которые стоит повторить и запомнить:
�� Общий принцип: внутренний массив table , содержащий бакеты (корзины) – списки элементов с одинаковыми пересчитанными хэш-суммами;
�� Пересчет хэш-суммы для умещения int индексов в capacity ячейках table ;
�� rehash – удвоение размера table при достижении threshold ( capacity*loadFactor ) занятых бакетов;
�� Невозможность сжать однажды раздувшийся table ;
�� Два способа разрешения коллизий: используемый в HashMap метод цепочек и альтернатива – открытая адресация;
�� Варианты для многопоточного использования: пересинхронизированная Hashtable и умная ConcurrentHashMap ;
�� Оптимизация Java 8: превращение списка в бакете в дерево при достижении 8 элементов – при большом количестве коллизий скорость доступа растет с O(n) до O(log(n));
�� Явное использование бакета 0 для ключа null ;
�� Связь с HashSet – HashMap , в котором используются только ключи;
�� Нет гарантий порядка элементов;

Обсуждая этот вопрос на интервью вы обязательно затронете особенности методов equals/hashCode. Возможно придется поговорить об альтернативных хранилищах ключ-значение – TreeMap, LinkedHashMap.

Java Blog

HashMap в Java работает по принципу хеширования. Это структура данных, которая позволяет сохранять объект и извлекать его за постоянное время O(1). При хешировании хеш-функции используются для связывания ключа и значения в HashMap. Объекты сохраняются путем вызова метода put(key, value) HashMap и извлекаются путем вызова метода get(key). Когда мы вызываем метод put, вызывается метод hashcode() ключевого объекта, чтобы хеш-функция карты могла найти место в корзине для хранения объекта значения, который на самом деле является индексом внутреннего массива, известного как таблица. HashMap внутренне хранит отображение в виде объекта Map.Entry, который содержит как объект ключа, так и объект значения.

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

Если мы попытаемся получить объект из этого связанного списка, нам понадобится дополнительная проверка для поиска правильного значения, это выполняется методом equals(). Поскольку каждый узел содержит запись, HashMap продолжает сравнивать ключевой объект записи с переданным ключом, используя equals(), и когда он возвращает true, Map возвращает соответствующее значение.

Интерфейсы Comparable и Comparator в Java
Как HashMap обрабатывает коллизии в Java
В чем будет проблема, если не переопределять метод hashCode()

HashMap в Java

В терминах компьютерного программирования карта представляет собой набор ассоциаций между парами объектов. Java HashMap — это базовая реализация интерфейса Map. Java предоставляет две структуры данных для хэш-таблиц: одна — Hashtable, а следующая — HashMap. HashMap похож на Hashtable с двумя исключениями: методы HashMap несинхронизированы и позволяют вводить нулевые и нулевые значения в отличие от Hashtable. Hashtable синхронизируется и работает плохо в однопоточной среде. Из-за этого HashMap обычно предпочтительнее, если только вам не нужно заниматься потоками и синхронизацией. HashMap не является надежной коллекцией потоков и требует правильной обработки синхронизации.

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

HashMap

Объекты хранятся путем вызова метода put (ключ, значение) HashMap и извлекаются вызовом метода get (key).

Как работает hashmap Java?

HashMap работает по принципу Hashing. В простом случае хеширование — это способ присвоения уникального кода для любой переменной / объекта после применения любой формулы / алгоритма по его свойствам. Функция хэша должна возвращать один и тот же хэш-код каждый раз, когда функция применяется на одинаковых или равных объектах.

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

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

Как добавить элементы в Hashmap?

import Java.util.*; class TestClass < public static void main (String[] args) throws Java.lang.Exception < // Создание HashMap HashMapdays = new HashMap(); // Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); > >

Как получить размер Java HashMap?

Метод size() используется для возврата числа сопоставлений значений ключа на этой карте.

// Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); System.out.println("Size of HashMap: "+ days.size());

Вывод:

Size of HashMap: 4

Как перебирать элементы в Hashmap?

Существует несколько способов просмотра элементов в Hashmap.

Используйте функцию entrySet() для итерации по карте и нужно получить доступ к значению и ключу:

HashMap days = new HashMap(); days.put(1,»Sunday»); days.put(2,»Monday»); days.put(3,»Tuesday»); days.put(4,»Wednesday»); Set set = days.entrySet(); for (Map.Entry sg : set)

Вывод:

Key :1 Value :Sunday Key :2 Value :Monday Key :3 Value :Tuesday Key :4 Value :Wednesday

Использование для цикла:

// Итерация по HashMap for(Integer key: days.keySet())

Вывод:

1 :: Sunday 2 :: Monday 3 :: Tuesday 4 :: Wednesday

Использование итератора и Map.Entry:

Iterator> it = days.entrySet().iterator(); while (it.hasNext()) < Map.Entrypair = it.next(); System.out.println( pair.getKey() + " " + pair.getValue()); >

Вывод:

1 Sunday 2 Monday 3 Tuesday 4 Wednesday

Использование foreach и Map.Entry:

for (Map.Entry pair : days.entrySet())

Вывод:

1 Sunday 2 Monday 3 Tuesday 4 Wednesday

Использование цикла while:

Set set = days.entrySet(); Iterator i = set.iterator(); while(i.hasNext())

Удаление записей из HashMap

Метод remove() используется для удаления сопоставления для указанного ключа с этой карты, если он присутствует.

// Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); // удалить значение для ключа 3 days.remove(3); System.out.println("Values after remove: "+ days);

Вывод:

Values after remove:

Удалить все значения из Java HashMap

// Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); System.out.println("Brefor remove: "+ days.size()); // удалить весь элемент из hashmap days.clear(); System.out.println("After remove: "+ days.size());

Вывод:

Brefor remove: 4 After remove: 0

Как выполнить поиск ключа в HashMap?

Используя метод containsKey(), вы можете узнать о существовании ключа.

// Создание HashMap HashMap days = new HashMap(); // Добавление пар ключ / значение days.put(1,»Sunday»); days.put(2,»Monday»); days.put(3,»Tuesday»); days.put(4,»Wednesday»); Integer key=4; if(days.containsKey(key))< System.out.println("Key " + key + " found"); >else

Вывод:

Key 4 found

Как получить ключ от значения в HashMap?

// Создание HashMap HashMap days = new HashMap(); // Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); Integer key= null; String value="Tuesday"; for(Map.Entry entry: days.entrySet()) < if(value.equals(entry.getValue()))< key = (Integer)entry.getKey(); break; // нарушение, потому что его одна к одной карте >> System.out.println("Found Key : "+ key +" value: " + value);

Вывод:

Found Key : 3 value: Tuesday

Следующая Java-программа иллюстрирует весь вышеупомянутый метод в одной программе

import Java.util.*; class TestClass < public static void main (String[] args) throws Java.lang.Exception < // Как создать HashMap? HashMap days = new HashMap (); // Как добавить пары ключ / значение в HashMap? days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); days.put(5,"Thursday"); days.put(6,"Friday"); days.put(7,"Saturday"); // Как проходить через HashMap? for(Map.Entry m:days.entrySet()) < System.out.println(m.getKey()+" "+m.getValue()); >// Как удалить определенный элемент из HashMap days.remove(3); Set set = days.entrySet(); for (Map.Entry sg : set) < System.out.println("Key :"+sg.getKey() + " Value :"+days.get(sg.getKey())); >// Как найти ключ в HashMap? Integer key=4; if(days.containsKey(key))< System.out.println("Key " + key + " found"); >else < System.out.println("Key " + key+ " does not exist"); >// Как получить ключ от его значения в HashMap Integer iKey= null; String value="Monday"; for(Map.Entry entry: days.entrySet()) < if(value.equals(entry.getValue()))< iKey = (Integer)entry.getKey(); break; // нарушение, потому что его одна к одной карте >> System.out.println("Found Key : "+ iKey +" value: " + value); // Как удалить весь элемент из HashMap? days.clear(); // Как найти размер HashMap System.out.println("After remove: "+ days.size()); > >

Различия между HashMap и Hashtable

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

Различия между HashMap и Hashtable

Hashtable синхронизируется, а HashMap не синхронизируется. Это делает HashMap лучше для не-потоковых приложений, поскольку несинхронизированные объекты обычно выполняют намного лучше, чем синхронизированные. Синхронизированный означает, что только один поток может изменить хэш-таблицу в один момент времени. В принципе, это означает, что любой поток перед выполнением обновления на хэш-таблице должен будет получить блокировку объекта, в то время как другие будут ждать освобождения блокировки. Источник: http://net-informations.com/Java/col/hashmap.htm

Внутренняя работа HashMap в Java

[примечание от автора перевода] Перевод был выполнен для собственных нужд, но если кому -то это окажется полезным, значит мир стал хоть немного, но лучше! Оригинальная статья — Internal Working of HashMap in Java

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

Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:

int — хэш
K — ключ
V — значение
Node — следующий элемент

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

Хэширование

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

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

// специальный класс Key для переопределени методов hashCode() // и equals() class Key < String key; Key(String key) < this.key = key; >@Override public int hashCode() < return (int)key.charAt(0); >@Override public boolean equals(Object obj) < return key.equals((String)obj); >>

Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.

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

Метод hashCode()

Метод hashCode() используется для получения хэш кода объекта. Метод hashCode() класса Object возвращает ссылку памяти объекта в целочисленной форме (идентификационный хеш (identity hash code)). Сигнатура метода public native hashCode() . Это говорит о том, что метод реализован как нативный, поскольку в java нет какого -то метода позволяющего получить ссылку на объект. Допускается определять собственную реализацию метода hashCode(). В классе HashMap метод hashCode() используется для вычисления корзины (bucket) и следовательно вычисления индекса.

Метод equals()

Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.

Корзины (Buckets)

Bucket -это единственный элемент массива HashMap. Он используется для хранения узлов (Nodes). Два или более узла могут иметь один и тот -же bucket. В этом случае для связи узлов используется структура данных связанный список. Bucket -ы различаются по ёмкости (свойство capacity). Отношение между bucket и capacity выглядит следующим образом:

capacity = number of buckets * load factor

Один bucket может иметь более, чем один узел, это зависит от реализации метода hashCode(). Чем лучше реализованн ваш метод hashCode(), тем лучше будут использоваться ваши bucket -ы.

Вычисление индекса в HashMap

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

index = hashCode(key) & (n-1).

где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.

изначально пустой hashMap: здесь размер hashmap равен 16:

HashMap map = new HashMap();

HashMap:

вставка пар Ключ — Значение: добавить одну пару ключ — значение в конец HashMap

map.put(new Key("vishal"), 20);

Вычислить значение ключа . Оно будет сгенерированно, как 118.
Вычислить индекс с помощью метода index , который будет равен 6.
Создать объект node.

 < int hash = 118 // не строка, а // объект класса Key Key key = Integer value = 20 Node next = null >

Теперь HashMap выглядит примерно так:

добавление другой пары ключ — значение: теперь добавим другую пару

map.put(new Key("sachin"), 30);

Вычислить значение ключа . Оно будет сгенерированно, как 115.
Вычислить индекс с помощью метода index , который будет равен 3.
Создать объект node.

 < int hash = 115 Key key = Integer value = 30 Node next = null >

Теперь HashMap выглядит примерно так:

в случае возникновения коллизий: теперь добавим другую пару

map.put(new Key("vaibhav"), 40);

Вычислить значение ключа . Оно будет сгенерированно, как 118.
Вычислить индекс с помощью метода index , который будет равен 6.
Создать объект node.

 < int hash = 118 Key key = Integer value = 20 Node next = null >

Теперь HashMap выглядит примерно так:

[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.

map.get(new Key("sachin"));

Вычислить хэш код объекта . Он был сгенерирован, как 115.
Вычислить индекс с помощью метода index , который будет равен 3.
Перейти по индексу 3 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
В нашем случае элемент найден и возвращаемое значение равно 30.

получаем значение по ключу vaibahv:

map.get(new Key("vaibhav"));

Вычислить хэш код объекта . Он был сгенерирован, как 118.
Вычислить индекс с помощью метода index , который будет равен 6.
Перейти по индексу 6 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
В данном случае он не найден и следующий объект node не равен null.
Если следующий объект node равен null, возвращаем null.
Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.

// Java программа для иллюстрации // внутренней работы HashMap import java.util.HashMap; class Key < String key; Key(String key) < this.key = key; >@Override public int hashCode() < int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; >@Override public boolean equals(Object obj) < return key.equals(((Key)obj).key); >> // Driver class public class GFG < public static void main(String[] args) < HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); >>

hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Изменения в Java 8

Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных «связанный список» и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).

Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

Важный момент

Сложность операций get() и put() практически константна до тех пор, пока не будет проведенно повторное хэширование.
В случае коллизий, если индексы двух и более объектов node одинаковые, объекты node соединяются с помощью связанного списка, т.е. ссылка на второй объект node хранится в первом, на третий во втором и т.д.
Если данный ключ уже существует в HashMap, значение перезаписывается.
Хэш код null равен 0.
Когда объект получается по ключу происходят переходы по связанному списку до тех пор, пока объект не будет найден или ссылка на следующий объект не будет равна null.

Как работает hashmap в java