Резюме
Принцип HashMap также является вопросом, который часто возникает в интервью с крупными фабриками, и это также контейнер Java, обычно используемый в работе.Эта статья в основном анализирует и объясняет следующие вопросы, чтобы помочь вам понять принцип HashMap.
1. Каков процесс добавления пары ключ-значение в HashMap?
2. Почему HashMap не является потокобезопасным?
3. Зачем переписывать методы hashCode() и equal() вместе?
Каков процесс добавления пары ключ-значение в HashMap?
Это блок-схема, найденная в Интернете. Вы можете посмотреть на эту блок-схему в сочетании с шагами, чтобы понять процесс добавления пар "ключ-значение".
1. Инициализировать таблицу
Определите, является ли таблица пустой или нулевой, в противном случае выполните метод resize() (метод resize обычно вызывается при расширении, а также может вызываться для инициализации таблицы).
2. Рассчитайте хеш-значение
Вычислите хэш-значение в соответствии с ключом значения ключа. (Поскольку hashCode является переменной типа int, она имеет размер 4 байта и 32 бита, поэтому над младшими 16 битами и старшими 16 битами hashCode будет выполняться операция исключающего ИЛИ, чтобы сохранить характеристики старших битов, так что полученное хэш-значение распределяется более равномерно)
static final int hash(Object key) {
int h;
return (key == null) ？ 0 : (h = key.hashCode()) ^ (h >>> 16);
}
3. Вставьте или обновите узлы
Вычислите вставленный индекс массива i в соответствии с (n - 1) и хэшем, а затем оцените
table[i]==null
Тогда это означает, что под текущим индексом массива нет элемента с хеш-конфликтом, и новый узел добавляется напрямую.
table[i].hash == hash &&(table[i]== key || (key != null && key.equals(table[i].key)))
Определите, совпадает ли первый элемент таблицы[i] с ключом, и если он совпадает, обновите значение напрямую.
table[i] instanceof TreeNode
Определите, является ли table[i] treeNode, то есть является ли table[i] красно-черным деревом, и если это красно-черное дерево, вставьте пары ключ-значение непосредственно в дерево.
Другие ситуации
Вышеупомянутые условия оценки не выполняются, что указывает на то, что table[i] хранит связанный список, а затем просматривает связанный список, чтобы определить, равен ли ключ существующего элемента ключу вставленной пары ключ-значение, если да, обновите значение, если нет, то вставьте новый узел в конец связанного списка. После вставки определите, больше ли длина связанного списка 8. Если она больше 8, преобразуйте связанный список в красно-черное дерево.
4. Расширение
После успешной вставки определите, превышает ли фактическое количество пар ключ-значение порог максимальной емкости (обычно длина массива * коэффициент загрузки 0,75). Если превышает, увеличьте емкость.
Исходный код выглядит следующим образом:
2. Почему HashMap не является потокобезопасным?
На самом деле, изучив метод добавления пар ключ-значение в HashMap, мы можем увидеть, что во всем методе не используется блокировка, поэтому при многострочном параллельном доступе это может вызвать проблему несогласованности данных.
Например:
Если есть два потока, которые добавляют пары ключ-значение, оба выполняются дляif ((tab = table) == null || (n = tab.length) == 0)Эта строка оператора инициализирует массив табличных переменных, что приведет к перезаписи уже инициализированной таблицы массива, а затем ранее инициализированный поток добавит пару ключ-значение к ранее инициализированному массиву, что приведет к потере ключ- пара значений.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
...后面的代码省略
}
3. Зачем переписывать методы hashCode() и equal() вместе?
Когда наш объект используется в качестве ключа в HashMap или элемента в HashSet, методы hashCode() и equal() должны быть переписаны одновременно.
Сначала взгляните на реализацию методов hashCode() и equal() по умолчанию.
Вы можете видеть, что исходный код в классе Object выглядит следующим образом: Вы можете видеть, что реализация метода equals() по умолчанию предназначена для определения того, совпадают ли адреса памяти двух объектов, чтобы определить возвращаемый результат.
public native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}
Многие блоги в Интернете говорят, что реализация hashCode по умолчанию должна возвращать адрес памяти, что не соответствует действительности.Возьмем OpenJDK в качестве примера, существует 5 методов вычисления hashCode по умолчанию, некоторые возвращают случайные числа, а некоторые возвращают адреса памяти. Какой метод расчета используется, зависит от библиотеки времени выполнения и конкретной реализации JVM.
Заинтересованные друзья могут читать этот блогblog.CSDN.net/Сюй Siwei1236…
Затем посмотрите на метод hashCode(), применение метода equal() в HashMap.
static final int hash(Object key) {
int h;
//因为hashCode是一个int类型的变量，是4字节，32位，所以这里会将hashCode的低16位与高16位进行一个异或运算，来保留高位的特征，以便于得到的hash值更加均匀分布
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
Чтобы равномерно хранить набор пар ключ-значение в массиве, HashMap вычисляет хэш-код ключа для получения хеш-значения по модулю длины массива с хэшем, получает индекс массива и сохраняет пару ключ-значение. в соответствующем индексе массива Под связанным списком (при условии, что длина связанного списка меньше 8, порог преобразования в красно-черное дерево не достигнут).
Ниже приведен метод putVal() для добавления пар ключ-значение. Код, выполняемый, когда нижний индекс массива соответствует связанному списку.
//遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//已经遍历到链表末尾，说明链表不存在这个key
p.next = newNode(hash, key, value, null);//在末尾添加这个键值对
if (binCount >= TREEIFY_THRESHOLD - 1) //超过链表转化为红黑树的阀值（也急速链表长度》=8）
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
Можно ясно видеть, что метод оценки того, равен ли добавленный ключ существующему ключу в связанном списке, в основномe.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))), То есть: 1. Сначала оцените, равны ли хеш-значения, и сразу закончите суждение, если они не равны, потому что хеш-значения не равны, и ключи точно не равны. 2. Определить, равны ли адреса памяти двух ключевых объектов (равны одному и тому же объекту в памяти). 3. Если ключ не нулевой, вызовите метод equal() ключа, чтобы определить, равен ли он, потому что возможно, что адреса, хранящиеся в памяти двух ключей, различны, но они равны. Это как
String a = new String("test");
String b = new String("test");
System.out.println("a==b is "+a==b);//打印为false
System.out.println("a.equals(b) is "+a.equals(b));//打印为true
задний план
Предположим, у нас есть класс KeyObject. Предположим, мы думаем, что атрибуты a двух KeyObjects равны, тогда KeyObjects равны и равны. Мы используем KeyObject в качестве ключа HashMap и используем равенство KeyObject в качестве стандарта дедупликации. .Неравные значения идут в HashMap
public static class KeyObject {
Integer a;
public KeyObject(Integer a) {
this.a = a;
}
}
Предположим, что ни метод hashCode(), ни метод equals() не переопределены (результат: HashMap не может гарантировать дедупликацию)
Выполните следующий код:
public static void main(String[] args) {
KeyObject key1 = new KeyObject(1);
KeyObject key2 = new KeyObject(1);
System.out.println("key1的hashCode为"+ key1.hashCode());
System.out.println("key2的hashCode为" + key2.hashCode());
System.out.println("key1.equals(key2)的结果为"+(key1.equals(key2)));
HashMap<KeyObject,String> hashMap = new HashMap<KeyObject,String>();
hashMap.put(key1,"value1");
hashMap.put(key2,"value2");
//打印hashMap
for(KeyObject key :hashMap.keySet()){
System.out.println("KeyObject.a="+key.a+" : "+hashMap.get(key));
}
}
Если метод hashCode() и метод equals() KeyObject не переопределены, то даже если атрибут a KeyObject равен 1, hashCode ключей1 и key2 различны, а методы equals() ключей1 и key2 не равны Таким образом, key1 и key2 могут существовать в hashMap одновременно.
распечатать результат:
key1的hashCode为728890494
key2的hashCode为1558600329
key1.equals(key2)的结果为false
KeyObject.a=1 : value1
KeyObject.a=1 : value2
Если переписан только метод hashCode() (результат: оценка равенства не может быть выполнена корректно с элементами связанного списка, поэтому дедупликация не может быть гарантирована)
Выполните следующий код:
public static class KeyObject {
Integer a;
public KeyObject(Integer a) {
this.a = a;
}
@Override
public int hashCode() {
return a;
}
public static void main(String[] args) {
KeyObject key1 = new KeyObject(1);
KeyObject key2 = new KeyObject(1);
System.out.println("key1的hashCode为"+ key1.hashCode());
System.out.println("key2的hashCode为" + key2.hashCode());
System.out.println("key1.equals(key2)的结果为"+(key1.equals(key2)));
HashMap<KeyObject,String> hashMap = new HashMap<KeyObject,String>();
hashMap.put(key1,"value1");
hashMap.put(key2,"value2");
for(KeyObject key :hashMap.keySet()){
System.out.println("TestObject.a="+key.a+" : "+hashMap.get(key));
}
}
}
В настоящее время реализация метода equal() является реализацией по умолчанию, то есть, когда адреса памяти двух объектов равны, метод equal() возвращает true Хотя атрибуты key1 и key2 одинаковы , они различаются по объекту памяти, поэтому результат key1==key2 будет ложным.Реализация по умолчанию метода equals() объекта KeyObject заключается в оценке адресов памяти двух объектов, поэтому key1.equals(key2) также будет ложным, поэтому эти две пары ключ-значение можно многократно добавлять в hashMap.
Выходной результат:
key1的hashCode为1
key2的hashCode为1
key1.equals(key2)的结果为false
TestObject.a=1 : value1
TestObject.a=1 : value2
Если переписан только метод equals() (результат: сопоставление с другими индексами массива в HashMap, дублирование не может быть гарантировано)
public static class KeyObject {
Integer a;
public KeyObject(Integer a) {
this.a = a;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
KeyObject keyObject = (KeyObject) o;
return Objects.equals(a, keyObject.a);
}
public static void main(String[] args) {
KeyObject key1 = new KeyObject(1);
KeyObject key2 = new KeyObject(1);
System.out.println("key1的hashCode为"+ key1.hashCode());
System.out.println("key2的hashCode为" + key2.hashCode());
System.out.println("key1.equals(key2)的结果为"+(key1.equals(key2)));
HashMap<KeyObject,String> hashMap = new HashMap<KeyObject,String>();
hashMap.put(key1,"value1");
hashMap.put(key2,"value2");
for(KeyObject key :hashMap.keySet()){
System.out.println("TestObject.a="+key.a+" : "+hashMap.get(key));
}
}
}
Предполагая, что используется только метод equals(), метод hashCode будет реализован по умолчанию, а конкретный метод расчета зависит от JVM (в ходе тестирования было обнаружено, что объекты с разными адресами памяти, но одинаковыми, их hashCodes не то же самое), поэтому рассчитанный индекс массива отличается, он будет храниться в связанном списке под разными индексами массива в hashMap, что также приведет к дублированию элементов в HashMap.
Результат выглядит следующим образом:
key1的hashCode为1289479439
key2的hashCode为6738746
key1.equals(key2)的结果为true
TestObject.a=1 : value1
TestObject.a=1 : value2
Суммировать
Поэтому, когда наш объект используется в качестве ключа в HashMap или элемента в HashSet, методы hashCode() и equal() должны быть переписаны одновременно, потому что hashCode повлияет на индекс массива, хранящийся в ключе, и его связь с элемент связанного списка Предварительное суждение, equal() является окончательным критерием для оценки того, равен ли ключ ключу в связанном списке.
- Следовательно, только переписывание метода hashCode() приведет к невозможности правильно оценить равенство с элементами связанного списка и, следовательно, не может гарантировать дедупликацию.
- Только переопределение метода equals() приводит к тому, что пары ключ-значение сопоставляются с разными индексами массива в HashMap, что не может гарантировать дедупликацию.