Привет! Вы найдете множество руководств по реализации HashMaps, но очень немногие из них подробно разбираются в HashMaps. Здесь мы собираемся понять внутреннюю работу HashMap и понять, как ее можно улучшить в зависимости от потребностей пользователя. Итак, давайте нырнем. Если вы где-то застряли, продолжайте читать. Потому что я разрешил все сомнения в самой статье. Если у вас остались сомнения, задавайте их в комментариях. Это моя попытка для # 100DaysOfCode

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

Давай сделаем одно. Откройте Cmd (командную строку для Windows или терминал для IOS) и введите команду:
`javap java.util.HashMap`

И нажмите Enter.

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

Что такое HashMap? Мы вернемся к этому снова через несколько минут.

Интересно, если бы мы могли смешать возможности Array (извлечение O (1)) и связанного списка (динамическое добавление и удаление узлов), насколько мощными мы могли бы стать?
Это именно то, что делает HashMap.

Предположим, что хэш-карта - это место для хранения всех данных. Итак, основываясь на этом, мы могли бы захотеть добавить данные, извлечь данные или манипулировать данными, верно? Мы рассмотрим все это, изучив структуру Java-класса HashMap.

`публичный класс java.util.HashMap‹ K, V ›{}`

Что это значит? В нем говорится, что HashMap (место хранения) будет хранить данные в виде пары ключ-значение, где K - ключ, а V - значение. Вы спросите, почему пара "ключ-значение"? Это потому, что это упрощает поиск данных.

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

Я сказал вам, что HashMap хранит данные в паре «ключ-значение» и использует возможности как массива, так и связанного списка. Это потому, что в нем реализован массив и связанный список (да!).
Массив используется для хранения хэша ключа, а связанный список используется для хранения данных, ключа и прочего.
Следует отметить, что HashMap хранит объект в форме Entry Class. И этот класс Entry имеет форму связанного списка.
Класс Entry выглядит так.

static class Entry<K,V> implements Map.Entry<K,V>
{
  final K key;
  V value;
  Entry<K,V> next;
  final int hash;
  ........
}

Итак, давайте предположим, что каждый ключ может соответствовать нескольким значениям (коллизия - объяснение приведено позже), эти несколько значений будут затем сохранены в объекте ввода одно за другим, и каждый объект ввода будет узлом LinkedList.

Коллизии в HashMap.

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

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

В основном необходимо выполнить 3 операции:

  1. Добавление данных
  2. Извлечение данных
  3. Управление данными

Давайте подробно рассмотрим каждую из них.

1. Добавление данных

Чтобы добавить данные в HashMap, мы используем метод put ().

`public V put (K ключ, V значение) {…}`

Он говорит о добавлении данных в виде пары ключ-значение, где K может быть любым, например int, String, char или даже Object. То же самое и с ценностью. И этот метод возвращает старое значение, имеющееся для этого ключа. Если для этого ключа нет значения, этот метод вернет null.

Давайте углубимся в поставленный метод.

public V put(K key, V value) 
{
  if (key == null)
  return putForNullKey(value);
  int hash = hash(key.hashCode());
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next)
  {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    {
      V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
   }
   return null;
}

Шаг 1. Что он говорит, сначала проверьте, имеет ли он значение null. Если он равен нулю, не принимайте хэш ключа, так как это приведет к ошибке, а вместо этого возьмите данные и вставьте узел связанного списка в 0-й индекс массива и поместите данные и ключ как объект ввода. Только один объект может быть сохранен в 0-м индексе.
Если ключ не равен нулю, тогда возьмите хэш ключа с помощью метода хеширования, переопределенного разработчиком из класса объекта, а затем снова возьмите хеш с помощью метода хеширования реализуется HashMap.

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

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

Как предотвратить ввод двойного ключа? Это делается методом equals (). Метод равенства, используемый в условии if в приведенном выше примере. Если ключ присутствует, он просто добавляет объект Entry в следующий узел в этом месте массива.

2. Получение данных

Для поиска HashMap использует метод get ().
`public V get (K)`
Я получаю прототип этого метода из команды javap, которую я использовал ранее.

Этот метод говорит, что он дает вам значение (объект входа), если вы добавляете ключ в метод get. Давайте углубимся в структуру метода. Это почти то же самое, что и метод put ().

public V get(Object key)
{
  if (key == null)
  return getForNullKey();
  int hash = hash(key.hashCode());
  for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
   {
     Object k;
     if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
     return e.value;
   }
  return null;
}

Шаг 1. Проверьте, является ли ключ нулевым. Если ключ равен нулю, вернуть значение, хранящееся в 0-м индексе массива.

Шаг 2. Если ключ не равен нулю, возьмите ключ и используйте метод hashCode (), переопределенный разработчиком, если он есть. Затем снова возьмите хэш вывода.

Шаг 3. В цикле for вы видите, что вы извлекаете весь связанный список в этом месте массива, передавая индекс (рассчитанный с помощью метода indexFor ())

Шаг 4: Теперь мы знаем, что каждый объект входа выглядит так.

static class Entry<K,V> implements Map.Entry<K,V>
{
 final K key;
 V value;
 Entry<K,V> next;
 final int hash;
 ........
}

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

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

Шаг 4: Если мы находим значение, мы возвращаем его или возвращаем null.

3. Управление данными

`public V remove (K);
public void clear ();
public boolean remove (K, V);
public boolean replace (K, V, V);
public V replace (K, V); `

Все эти методы используются для управления данными. Думаю, теперь вы понимаете, как это работает. Тем не менее, если вы этого не сделаете, спросите в разделе комментариев.

Производительность HashMap

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

Начальная емкость - это размер массива. Значение по умолчанию - 16. Оно возрастает в степени 2.

Коэффициент загрузки - это значение, определяющее, в какой момент необходимо изменить размер массива. Значение по умолчанию 0,75. Это означает, что если массив был заполнен до INITIAL_CAPACITY * LoadFactor, размер массива изменится, и тогда он станет 32 в длину (16 * 2). И это повторяется снова и снова.

Если вы хотите установить их явно, вы можете сделать это следующим образом.
Map<String,String> hashMapWithCapacity=new HashMap<>(32);
Map<String,String> hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);

Высокое значение INITIAL_CAPACITY подходит для большого количества записей, но для небольших итераций.
А низкое значение INITIAL_CAPACITY хорошо для небольшого количества записей, но при большом количестве итераций.

Новое в Java 8

Начиная с java 8, когда количество записей в связанном списке достигает 8 (MIN_TREEIFY_CAPACITY;), он преобразует связанный список в сбалансированное дерево. Это повысило производительность в миллион раз.
Ранее метод get имел сложность O (n) в худшем случае. Но это изменилось в Java 8. Он стал O (logn). Это произошло из-за сбалансированного дерева, которое ускорило обход.

Теперь даже с миллионом записей это занимает всего 10 наносекунд!

Итак, в этом сила HashMaps

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