Давайте сначала посмотрим на вопрос интервью:
Серия пар клавишных значений, хранящихся в HashMap, где ключ-это определенный тип, который мы настраиваем. После введения HashMap мы изменяем атрибуты ключа снаружи, а затем используем этот ключ для удаления элементов из HashMap. Что вернется в это время hashmap?
Пример кода и ответы были приведены в статье, но не указано никаких объяснений о принципе HashMap.
1. Особенности
Мы можем использовать любой класс в качестве ключа HashMap, но каковы ограничения на эти классы? Давайте посмотрим на следующий код:
Public Class Person {private String name; Public Perform (String name) {this.name = name; }} Map <человек, String> testmap = new Hashmap <> (); testmap.put (новый человек ("hello"), "world"); testmap.get (new Person ("hello")); // ---> nullПервоначально я хотел получить значение класса человека с равными значениями поля, но результат был нулевым. Любой, кто имеет небольшое знание HashMap, может видеть, что у класса человека нет метода HashCode с переопределением, что приводит к его наследию хэшкода объекта (возвращение является его адресом памяти). Это также причина, по которой инвариантные классы, такие как строка (или целое число и т. Д.), Обычно используются в качестве ключа Hashmap. Итак, как HashMap использует HashCode для быстрого индексации ключа?
2. Принцип
Во -первых, давайте посмотрим на простое решение для реализации HashMap в «Мышлении на Java»:
//: контейнеры/simplehashmap.java // демонстрационная хешированная карта. import java.util.*; импорт net.mindview.util.*; открытый класс SimpleHashmap <K, V> расширяет AbstractMap <K, V> {// Выберите основное число для размера таблицы Hash, чтобы достичь единообразного дистрибции: Static Final Size = 997; // Вы не можете иметь физический массив дженериков, но вы можете подняться на один: @suppresswarnings ("uncecked") LinkedList <mapentry <K, v >> [] Buckets = новый LinkedList [size]; public v put (k key, v value) {v oldvalue = null; int index = math.abs (key.hashcode ()) % размер; if (buckets [index] == null) ведра [index] = new LinkedList <mapentry <k, v >> (); LinkedList <Mapentry <K, V >> Bucket = Buckets [Index]; Mapentry <K, v> pair = new Mapentry <K, v> (ключ, значение); логический нашел = false; ListIterator <mapentry <K, v >> it = bucket.listiterator (); while (it.hasnext ()) {mapentry <k, v> ipair = it.next (); if (ipair.getkey (). equals (key)) {oldvalue = ipair.getValue (); it.set (pare); // заменить старое на новое найдено = true; перерыв; }} if (! найдено) ведра [index] .add (pair); вернуть OldValue; } public v get (объект ключа) {int index = math.abs (key.hashcode ()) % size; if (buckets [index] == null) return null; for (mapentry <k, v> ipair: buckets [index]) if (ipair.getkey (). equals (key)) return ipair.getvalue (); вернуть ноль; } public set <map.Entry <K, v >> intrentSet () {set <map.Entry <K, v >> set = new Hashset <map.Entry <K, v >> (); для (LinkedList <mapentry <K, V >> ведро: ведра) {if (bucket == null) продолжить; для (Mapentry <K, V> mpair: Bucket) set.add (mpair); } return Set; } public static void main (string [] args) {simpleHashMap <String, String> m = new SimpleHashMap <String, String> (); M.Putalall (страны. Капитали (25)); System.out.println (m); System.out.println (M.Get ("Eritrea")); System.out.println (M.EntrySet ()); }}SimpleHashmap Construction Hash Table для хранения ключей. Функция хеш - это модуль операции Math.abs (key.hashcode ()) % %, а хэш -конфликт разрешается с помощью связанного метода списка; Каждый слот с ковшом хранит карту. Entry с тем же значением индекса (хэш), как показано на рисунке ниже:
Принцип реализации HashMap JDK аналогичен тем, что использует хэш -таблицу адреса цепного адреса для хранения Map.Entry:
/*** Таблица, изменившаяся по мере необходимости. Длина всегда должна быть силой двух. */Transient Intry <K, V> [] table = (inpit <K, v> []) umpty_table; Статическая запись класса <K, V> реализует Map.Entry <K, v> {final K -ключ; V Значение; Вход <K, V> Далее; int hash; …}Индекс Map.Entry получается путем хэшкода ключа. Если вы хотите получить значение, соответствующее ключу, вычислите его индекс для ключа, а затем вытащите карту в таблице, чтобы получить его. Для получения подробной информации см. Код:
public v get (object key) {if (key == null) return getFornullKey (); Inpit <K, v> intry = getEntry (key); return null == запись? null: entry.getValue ();} окончательная запись <k, v> getEntry (object key) {if (size == 0) {return null; } int hash = (key == null)? 0: хэш (ключ); for (inpit <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {объект k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) return e; } return null;}Можно видеть, что хэшкод напрямую влияет на эффективность функции хэш -хэш -хэшмапа - хороший хэшкод значительно снизит конфликты хэш и улучшит производительность запросов. В то же время, это также объясняет два вопроса, поднятых в начале: если пользовательский класс выполняет ключ HashMap, расчет хэшкода должен охватывать все поля конструктора, в противном случае можно получить нуль.