Нижеследующее в основном после прочтения «Безумных лекций по Java» и некоторых блогов, связанных с классами контейнеров Java, а также множества вопросов интервью, связанных с контейнерами Java, участвующими в facebook.Мы продолжим обновлять этот раздел позже.
Вопросы для интервью, связанные с HashMap
1. Каков процесс добавления пары ключ-значение в HashMap?
2. Каков процесс добавления пары ключ-значение в ConcurrentHashMap?
3. В чем разница между HashMap и HashTable, ConcurrentHashMap?
4. Нужно ли перефразировать после расширения HashMap?
5. Как расширяется HashMap и почему все 2 в N-й степени?
6. Как ConcurrentHashMap записывает размер количества элементов?
7. Почему ConcurrentHashMap и HashTable не поддерживают ключ, а значение равно null?
8. В чем разница между HashSet и HashMap?
9. Каковы методы реализации удаления элементов при обходе HashMap?
Каков процесс добавления пары ключ-значение в 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). Если превышает, увеличьте емкость.
Исходный код выглядит следующим образом:
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;
// 计算index，并对null做处理
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 节点key存在，直接覆盖value
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// 判断该链为红黑树
// hash值不相等，即key不相等；为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 该链为链表
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 结点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
++modCount;
// 超过最大容量 就扩容
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
Каков процесс добавления пары ключ-значение в ConcurrentHashMap?
Это моя собственная блок-схема, как показано ниже:
1. Определите нулевое значение
Определите, является ли key==null или value==null, если да, создайте исключение нулевого указателя.
2. Рассчитать хэш
Вычислить хеш-значение по ключу (результат вычисления согласуется с HashMap, а способ записи отличается).
3. Войдите в цикл for, чтобы вставить или обновить элементы
-
3.1 tab==null || tab.length==0,
Указывает, что текущая вкладка не была инициализирована.
Затем вызовите метод initTable() для инициализации вкладки. (В методе initTable, чтобы управлять только одним потоком для инициализации таблицы, текущий поток присвоит -1 переменной SIZECTL через операцию CAS. Если присвоение выполнено успешно, поток может инициализировать таблицу, в противном случае он вызовите метод Thread.yield(), чтобы получить квант времени).
-
3.2 f ==null
(Узел
f вычисляет индекс массива в соответствии с хэш-значением, элементом, хранящимся в индексе, f может быть нулевым, головным узлом связанного списка, корневым узлом красно-черного дерева или миграцией узел флага ForwardNode) Указывает, что в текущем местоположении нет пары ключ-значение с коллизией хэшей.
Затем создайте узел на основе ключа и значения, используйте операцию CAS, чтобы установить индекс текущего массива, и прервите цикл for.
-
3.3 f != null && f.hash = -1
Это означает, что ConcurrentHashMap расширяется, текущий узел f является узлом флага, а элементы конфликта хэшей, хранящиеся в текущем индексе, были перенесены.
Затем текущий поток вызовет метод helpTransfer(), чтобы помочь расширению.После завершения расширения вкладка укажет на новую таблицу, а затем продолжит выполнение цикла for.
-
3.4 В дополнение к трем вышеуказанным ситуациям
Это означает, что узел f является головным узлом связанного списка или корневым узлом красно-черного дерева, затем добавьте синхронизирующую блокировку синхронизации к f, а затем сделайте следующие суждения:
-
f.hash > 0
Если хэш-значение f больше 0, текущий индекс массива хранит связанный список, а f является головным узлом связанного списка.
Пройдите по связанному списку. Если есть узел с тем же значением хеш-функции, что и текущий узел, который нужно вставить, обновите значение узла. В противном случае создайте узел
в соответствии с ключом и значением и добавьте его в конец связанного списка. -
f instanceof TreeBin
Если f имеет тип TreeBin, это означает, что текущий индекс массива хранит красно-черное дерево, а f является корневым узлом красно-черного дерева.Вызовите метод putTreeVal, чтобы вставить или обновить узел.
После завершения вставки оценивается binCount (когда хранилищем индексов массива является связанный список, binCount — длина связанного списка), когда binCount превышает 8,и когда длина массива больше 64, затем вызовите метод treeifyBin, чтобы преобразовать связанный список в красно-черное дерево. Наконец, вырваться из цикла for.
-
PS:
Во многих технических статьях говорится, что если длина связанного списка больше 8, то он будет преобразован в красно-черное дерево.Я не обращал внимания на эту деталь в свое время, пока друг в группе не указал, что когда длина исходного связанного списка превышает 8, метод treeifyBin действительно будет вызван, но он будет оцениваться в методе treeifyBinЯвляется ли текущая вкладка пустой или длина массива меньше 64, если условия соблюдены, то вызов метода resize для инициализации или расширения вкладки не приведет к преобразованию связанного списка в красно-черное дерево.
Исходный код метода putVal для добавления пар ключ-значение:
Исходный код метода treeifyBin:
MIN_TREEIFY_CAPACITY — 64.
4. Определите, требуется ли расширение
Вызовите addCount(), чтобы добавить к текущей длине массива 1. В методе addCount() он будет судить, превышает ли текущее количество элементов sizeCtl (порог расширения, общая длина * 0,75), если да, то он будет расширяться, если он находится в процессе расширения, текущий поток поможет в расширении.
В чем разница между HashMap и HashTable, ConcurrentHashMap?
Он в основном анализирует базовую структуру данных, безопасность потоков, эффективность выполнения, разрешает ли значение Null, начальную емкость и расширение, а также вычисление хеш-значения.
1. Базовая структура данных
transient Node<K,V>[] table; //HashMap
transient volatile Node<K,V>[] table;//ConcurrentHashMap
private transient Entry<?,?>[] table;//HashTable
HashMap=массив+связный список+красно-черное дерево
Базовая структура данных HashMap представляет собой массив + связанный список + красно-черное дерево. Каждый элемент массива хранится как головной узел связанного списка. Связанный список хранит набор пар ключ-значение с конфликтующими хеш-значениями. которые решаются методом адресной цепочки, коллизия хэшей. Чтобы длина связанного списка не была слишком большой и не влияла на эффективность поиска элементов, когда длина связанного списка больше 8, связанный список преобразуется в красно-черное дерево, а когда длина связного списка меньше 6, красно-черное дерево преобразуется в связанный список. Причина, по которой критическая точка равна 8, заключается в том, что временная сложность поиска красно-черного дерева равна logN, а средняя временная сложность поиска связанного списка равна N/2.Когда N равно 8, logN равно 3, что меньше чем N / 2, просто отлично.Уменьшите временную сложность поиска, преобразовав его в красно-черное дерево.
Hashtable = массив + связанный список
Базовая структура данных Hashtable такая же, как и у HashMap. Базовая структура данных представляет собой массив + связанный список, который также использует метод цепочек адресов для разрешения конфликтов. Однако, когда связанный список слишком длинный, он не будет преобразуется в красно-черное дерево для уменьшения временной сложности поиска. Hashtable — это устаревший класс, который редко используется в реальной разработке.
ConcurrentHashMap=массив+связный список+красно-черное дерево
Базовая структура данных ConcurrentHashMap согласуется со структурой HashMap.Основная структура данных представляет собой массив + связанный список + красно-черное дерево. Он просто использует volatile для изменения своих атрибутов, чтобы обеспечить видимость памяти (после того, как поток изменит эти атрибуты, он сделает недействительным кеш атрибута в других потоках, так что самое последнее значение будет взято при следующем чтении).
2. Безопасность потоков
HashMap не является потокобезопасным
HashMap не является потокобезопасным. (Например, когда несколько потоков вставляют несколько пар ключ-значение, если хэши ключей двух пар ключ-значение сталкиваются, это может привести к тому, что два потока будут работать с узлами в одном и том же связанном списке, что приведет к перезаписи значения одна пара ключ-значение)
Потокобезопасность HashTable
HashTable является потокобезопасным.Большинство методов модифицируются с помощью ключевого слова synchronized, так что только один поток может одновременно синхронно изменять HashTable, а производительность высока.
Безопасность потоков ConcurrentHashMap
ConcurrentHashMap является потокобезопасным, в основном за счет работы CAS + синхронизируется для обеспечения потокобезопасности.
CAS-операция
При вставке новой пары ключ-значение в ConcurrentHashMap, если соответствующий элемент нижнего индекса массива имеет значение null, узел атомарно устанавливается в массив посредством операции CAS.
//这是添加新的键值对的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他代码
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // 因为对应的数组下标元素为null，所以null作为预期值，new Node<K,V>(hash, key, value, null)作为即将更新的值，只有当内存中的值与即将预期值一致时，才会进行更新，保证原子性。
}
...其他代码
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
синхронизированный замок
При вставке новой пары ключ-значение в ConcurrentHashMap, если соответствующий элемент нижнего индекса массива не равен нулю, синхронизированная блокировка будет добавлена к элементу, хранящемуся в нижнем индексе массива (то есть головному узлу связанного списка), и затем будет выполнена операция вставки.
Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是数组下标存储的元素
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
3. Эффективность исполнения
Поскольку HashMap не является потокобезопасным, эффективность выполнения будет выше, за ней следует ConcurrentHashMap, поскольку HashTable добавляет синхронизированные блокировки ко всей HashTable при изменении и доступе, поэтому эффективность является самой низкой.
4. Разрешить ли появление нулевых значений
И ключ, и нуль HashMap могут быть нулевыми.Если ключ нулевой, вычисленное хеш-значение будет равно 0, а окончательный вычисленный индекс массива также будет равен 0, поэтому пара ключ-значение, ключ которой равен нулю, будет храниться в массив в связанном списке первого элемента. Пары ключ-значение, значение которых равно null, также могут быть вставлены обычным образом, что согласуется с процессом вставки обычных пар ключ-значение.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Ключ и значение HashTable не могут быть нулевыми. Если для ключа пары ключ-значение в HashTable задано значение null, будет выдано исключение нулевого указателя, поскольку метод hashCode() не может быть вызван для получения нулевого значения. хэш-значение. Точно так же, когда значение равно null, оно будет оценено в методе put, а затем будет выдано исключение нулевого указателя.
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode();
...其他代码
}
Ключ и значение ConcurrentHashMap не могут быть нулевыми, что будет оцениваться в методе putVal.Если это нуль, будет выдано исключение нулевого указателя.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
...其他代码
}
5. Начальная мощность и расширение
Не указывать начальную емкость
Если начальная емкость не указана, емкость по умолчанию для HashMap и ConcurrentHashMap будет равна 16, а емкость HashTable по умолчанию будет равна 11.
Не указывать начальную емкость
Если указана начальная емкость, емкость HashMap и ConcurrentHashMap будет равна степени двойки, что немного больше начальной емкости, и HashTable будет использовать начальную емкость,
Расширение
При расширении HashMap и ConcurrentHashMap будут удваивать исходную длину при расширении, а HashTable будет удваиваться плюс 1.
6. вычисление значения хэша
HashTable будет расширен до 2n + 1. Причина, по которой емкость HashTable равна 11, а расширение — 2n + 1, заключается в том, чтобы гарантировать, что длина HashTable является простым числом, потому что нижний индекс массива является модулем hashCode ключ и длина массива вычисляются, а когда длина массива является простым числом, это может обеспечить более равномерное распределение рассчитанных индексов массива, вы можете увидеть эту статьюФото.GitHub.IO/алгоритм/2…
public synchronized V put(K key, V value) {
...其他代码
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
...其他代码
}
Хэш-значения HashMap и ConcurrentHashMap выполняются путем XOR между старшими 16 битами и младшими 16 битами ключа hashCode() (это может сохранить характеристики старших битов и избежать некоторых ключей с разными старшими битами и одинаковыми младшими битами). битов, что приводит к конфликтам хэшей), Получите значение хеш-функции, а затем вычислите хэш&(n-1), чтобы получить индекс массива. (n — длина массива, потому что, когда n — целая степень числа 2, результат хеширования по модулю n математически равен хэшу & (n-1), а компьютер работает быстрее при &, так что это также длина HashMap всегда Причина установки степени 2)
//HashMap计算hash值的方法
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//ConcurrentHashMap计算hash值的方法
static int spread(int h) {//h是对象的hashCode
return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;
}
Нужно ли перефразировать после расширения HashMap?
После JDK1.8 повторное хэширование не требуется, так как хэш-значение пары ключ-значение в основном получается путем операции XOR между старшими 16 битами и младшими 16 битами хэш-кода() ключа.Пометьте индекс, поскольку длина представляет собой целочисленную степень. из 2, когда длина становится в два раза больше исходного размера после расширения, разница между результатом вычисления hash%(2*length) заключается в том, равно ли значение бита длины 1 или 0, если оно равно 0, то индекс в новый массив такой же, как у старого массива.Если он равен 1, индекс в новом массиве будет индексом + длина массива в старом массиве.
Как происходит расширение HashMap и почему размер N равен степени 2?
Расширение триггера
Если начальная длина не указана, длина массива HashMap по умолчанию равна 16. При добавлении новой пары ключ-значение будет вызываться метод putVal(), в методе после успешного добавления новой пары ключ-значение , будет оцениваться, превышает ли текущее количество элементов пороговое значение (длина массива * коэффициент загрузки 0,75), если это так, вызовите метод изменения размера для расширения. Конкретные этапы расширения следующие:
Рассчитать длину после расширения
-
если текущая таблица пуста
Затем напрямую инициализируйте массив с длиной массива 16 и верните его.
-
Если длина текущей таблицы уже больше максимального значения, указанного HashMap в 30-й степени 2
Затем верните старую таблицу напрямую без расширения.
-
Другие случаи
Расширьте длину таблицы в 2 раза, а затем рассчитайте новый порог расширения (новая длина массива * 0,75).
инициализировать новый массив
Новый массив будет инициализирован в соответствии с расширенной длиной массива и напрямую назначен таблице переменных-членов текущего hashMap.
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
Этот шаг очень интересен, и это также одно из проявлений того, что HashMap не является потокобезопасным, потому что newTab в это время все еще является пустым массивом.Если другие потоки обращаются к HashMap, перейдите к newTab, чтобы найти пару ключ-значение в соответствии с к ключу, и он вернет ноль. На самом деле ключ может иметь соответствующие пары ключ-значение, но все пары ключ-значение хранятся в старой таблице и не были перенесены.
(Напротив, HashTable решает проблему доступа других потоков во время раскрытия, модифицируя большинство методов с помощью ключевого слова synchronized, то есть, когда поток выполняет метод раскрытия, он блокирует объект HashTable, и другие потоки не могут получить к нему доступ. HashTable. ConcurrentHashMap решает проблему доступа других потоков при расширении за счет установки идентификационного узла ForwardingNode.При расширении, когда поток мигрирует все конфликтующие элементы Hash под индексом в массиве, массив будет изменен.Элемент массива индекса установлен к идентификационному узлу ForwardingNode, и когда другие потоки обращаются к нему, если найдено, что нижний индекс массива отображения хеш-значения ключа соответствует идентификационному узлу ForwardingNode (ForwardingNode наследуется от обычного Node, разница заключается в хеш-значении этого узла .. будет установлено в -1, и будет дополнительный указатель nextTable, указывающий на новую вкладку в процессе расширения), то по переменной nextTable в ForwardingNode элемент будет найден в новой вкладке (если он находится при добавлении новой пары ключ-значение, это ForwardingNode, затем вспомогательное расширение или блокировка ожидания, после завершения расширения перейти к новому массиву для обновления или вставки элементов)
Элемент миграции
Поскольку длина массива hashmap всегда 2 к nth Power, и она становится вдвое больше исходного размера после расширения, поэтому существует математическая формула. Когда длина составляет 2 к N-й мощности,
hash%length=hash&(length-1)
И поскольку длина — это N-я степень числа 2, длина-1 на самом деле равна N-1 единицам в двоичном формате. Например:
длина 16, длина 10000 в двоичном формате,
длина-1 равна 15, что равно 1111 в двоичном формате.
2*длина 32, а длина 100000 в двоичном формате.
2*length-1 равно 31, а длина 11111 в двоичном формате.
Следовательно, разница между результатом вычисления hash&(length-1) и результатом вычисления hash&(2*length-1) заключается в том, что после расширения нужно смотреть еще на один бит, то есть смотреть на результат & 1 из N-го бита и хеш-значения.
Предполагая, что исходная длина массива равна 16, двоичное представление длины-1 равно 1111. Хэш-значение ключа 1 равно 9, двоичное представление равно 01001, хеш-значение ключа 2 равно 25, 11001,
Таким образом, результат hash&(length-1) должен смотреть только на результат младших 4 битов.Младшие 4 бита 9 и 25 оба равны 1001, поэтому результаты вычислений одинаковы, и все результаты вычислений 9, поэтому индекс в массиве равен 9. в списке элементов.
После расширения длина массива равна 32, двоичное представление длины-1 равно 11111, хеш-значение ключа1 равно 9, двоичное представление равно 01001, хеш-значение ключа2 равно 25, 11001,
Таким образом, результат hash&(2*length-1) должен смотреть на младшие 5 битов результата.Младшие 4 бита 9 и 25 оба равны 1001, поэтому результаты вычислений противоречивы, а результаты вычислений оба 9 и 25, потому что хеш-значение ключа2 является первым. Пять цифр равны 1, а пятая цифра хеш-значения ключа1 равна 0, поэтому будет еще 16, что соответствует размеру исходной длины массива.
Следовательно, элементы конфликта хэшей, хранящиеся в связанном списке под тем же индексом индекса исходного массива, индексом newIndex в новом массиве после раскрытия является либо индекс, либо индекс+длина (в зависимости от того, равен ли N-й бит хеш-значения 1 , или 0, что является результатом hash&length, длина исходного массива равна степени N-1 числа 2)
Следовательно, он будет проходить по связанному списку (или красно-черному дереву), а затем вычислять результат хеширования и длины каждого узла по индексу индекса массива, а затем сохранять его в двух разных временных связанных списках.После завершения обхода результат hash&length равен 0. Связанный список будет сохранен в позиции индекса нового массива, а временный связанный список, состоящий из элементов, результат hash&length равен 1, будет сохранен в позиции index+length нового массива.
Как ConcurrentHashMap записывает размер количества элементов?
HashMap по умолчанию не является потокобезопасным.Можно считать, что одновременно может выполняться только один поток, поэтому hashMap использует очень простую переменную размера типа int для записи количества пар ключ-значение HashMap.
Реализация HashMap, записывающая количество пар ключ-значение, выглядит следующим образом:
transient int size;
public int size() {
return size;
}
Реализация ConcurrentHashMap для записи количества пар ключ-значение выглядит следующим образом:
//size方法最大只能返回Integer.MAX_VALUE
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ?Integer.MAX_VALUE : (int)n);
}
//mappingCount方法可以返回long类型的最大值，
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;
//sumCount会返回sumCount加上CounterCells数组中每个元素as存储的value
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
@sun.misc.Contended //这个注解可以避免伪共享，提升性能。加与不加，性能差距达到了 5 倍。在缓存系统中，由于一个缓存行是出于32-256个字节之间，常见的缓存行为64个字节。而一般的变量可能达不到那么多字节，所以会出现多个相互独立的变量存储在一个缓存行中的情况，此时即便多线程访问缓存行上相互独立变量时，也涉及到并发竞争，会有性能开销，加了@sun.misc.Contended这个注解，在jDK8中，会对对象前后都增加128字节的padding，使用2倍于大多数硬件缓存行的大小来避免相邻扇区预取导致的伪共享冲突。
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
Каждый раз, когда добавляется x новых пар ключ-значение, будет вызываться метод addCount(), чтобы использовать операцию CAS для baseCount + x. Если операция завершится ошибкой, будет создан новый объект типа CounterCell, новое число x будет сохранен, и объект будет добавлен в массив CounterCells.
Почему ConcurrentHashMap и HashTable не поддерживают ключ, а значение равно null?
Поскольку HashMap не является потокобезопасным, он по умолчанию используется в однопоточной среде.Если get(key) имеет значение null, вы можете передать containsKey(key) метод, чтобы определить, является ли значение этого ключа нулевым или ключ не существует, а ConcurrentHashMap, HashTable являются потокобезопасными, В многопоточных операциях, поскольку две операции get(key) и containsKey(key) вместе не являются атомарными операциями, Могут быть другие потоки, изменяющие данные в середине выполнения, поэтому невозможно различить, является ли значение нулевым или ключ не существует. Что касается ConcurrentHashMap, ключ HashTable не может быть нулевым, что в основном является замыслом дизайнера.
Разница между HashSet и HashMap?
HashMap в основном используется для хранения неповторяющихся пар ключ-значение, а HashSet хранит неповторяющиеся объекты. Хотя HashMap наследуется от AbstractMap и реализует интерфейс Map, HashSet наследуется от AbstractSet и реализует интерфейс Set. Но поскольку все они требуют дедупликации, основная реализация HashSet основана на HashMap (если нам нужно повторно использовать класс, мы можем использовать режим наследования или комбинированный режим. Комбинированный режим заключается в использовании класса как композиции нового часть класса, чтобы достичь цели повторного использования.) Например, в классе HashSet есть карта переменных-членов типа HashMap, которая является приложением комбинированного режима.
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();//占位对象
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;//占位对象
}
}
В методе построения HashSet создается HashMap и присваивается свойству карты, а затем при добавлении элементов элементы добавляются в HashMap как ключи, но значением является объект-заполнитель PRESENT. Кромеclone(),writeObject(),readObject()Именно HashSet должен быть реализован сам по себе, другие методы напрямую вызывают методы в HashMap. Так как же HashMap добивается неповторения ключей?
При вызове метода putVal HashMap для добавления новой пары ключ-значение выполняются следующие операции:
1. Рассчитанный ключ значения хеш-функции.
2. Сопоставьте нижний индекс массива в соответствии с хеш-значением, а затем получите соответствующий элемент нижнего индекса массива.
3. Нижний индекс массива хранит связанный список.Связанный список содержит элементы с конфликтами хэшей.Связный список будет пройден для определения hash1==hash2.Кроме того,key1==key2 или key1.equals(key2 ).
Поскольку хеш-код двух разных объектов может совпадать, но хэш-код одного и того же объекта должен быть равен,
== должен судить, указывают ли две переменные или экземпляры на один и тот же адрес памяти.Если они являются одним и тем же адресом памяти, объекты должны быть равны.
int hash = hash(key);//根据key计算hash值
p = tab[i = (n - 1) & hash];//根据hash值映射数组下标，然后获取数组下标的对应的元素。
for (int binCount = 0; ; ++binCount) {//数组下标存储的是一个链表，链表包含了哈希冲突的元素，会对链表进行遍历，判断每个节点的hash值与插入元素的hash值是否相等，并且是存储key对象的地址相等，或者key相等。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
Каковы методы реализации для удаления элементов во время обхода HashMap?
Первый вывод таков:
1-й метод - for-each перебирает HashMap.entrySet, удаляет с помощью HashMap.remove() (результат: выдает исключение).
Второй метод - for-each проходит HashMap.keySet, использует HashMap.remove() для удаления (результат: выдает исключение).
3-й метод — используйте HashMap.entrySet().iterator() для перебора удалений (результат: правильное удаление).
Давайте подробно рассмотрим причины ниже!
Метод обхода и удаления HashMap аналогичен методу ArrayList, но метод вызова API отличается. Сначала инициализируйте HashMap, мы хотим удалить пары ключ-значение, ключ которых содержит строку «3».
HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
hashMap.put("key1",1);
hashMap.put("key2",2);
hashMap.put("key3",3);
hashMap.put("key4",4);
hashMap.put("key5",5);
hashMap.put("key6",6);
Способ 1 - для каждого итерата над hashmap.entryset, удаляет с помощью hashmap.remove () (результат: racks inclov)
for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {
String key = entry.getKey();
if(key.contains("3")){
hashMap.remove(entry.getKey());
}
System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
}
Выходной результат:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key1=1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key2=2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key5=5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key6=6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是key3=3
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)
at com.test.HashMapTest.main(HashMapTest.java:22)
Второй метод - для каждого проходит HashMap.keySet и удаляется с помощью HashMap.remove() (результат: выдает исключение)
Set<String> keySet = hashMap.keySet();
for(String key : keySet){
if(key.contains("3")){
keySet.remove(key);
}
System.out.println("当前HashMap是"+hashMap+" 当前key是"+key);
}
Результат выглядит следующим образом:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前key是key3
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)
at com.test.HashMapTest.main(HashMapTest.java:23)
3-й метод — используйте HashMap.entrySet().iterator() для перебора удалений (результат: правильное удаление)
Iterator<Map.Entry<String, Integer>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if(entry.getKey().contains("3")){
iterator.remove();
}
System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
}
Выходной результат:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key1=1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key2=2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key5=5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key6=6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key4=4
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是deletekey=3
Первый метод и второй метод вызывают исключение ConcurrentModificationException, и причина для вышеуказанного метода обхода-удаления ошибки ArrayList одинакова, HashIterator также имеет ожидаемыйModCount, когда во время обхода будет получен следующий элемент, будет вызван метод next(), а затем Оцениваются значения ExpectedModCount и modCount, и если они несовместимы, создается исключение ConcurrentModificationException.
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
PS: что такое ConcurrentModificationException?
Согласно документации CONCULRENTMODICATIONCECTION, некоторые объекты не допускают одновременных модификаций, и это исключение брошено, когда эти модификации обнаружены. (Например, некоторые коллекции не позволяют одно нить пройти, а другая нить модифицирует коллекцию).
Некоторые наборы (такие как Collection, Vector, Arraylist, LinkedList, HashSet, Hashtable, Treemap, AbstractList, Serialized Form) Реализация итератора, если этот итератор можно назвать «отказоустойчивым итератором», если эта параллельная модификация предоставляется.Это означает, что итератор быстрого сбоя обнаруживает, что обнаружена параллельная модификация, и исключение выдается напрямую вместо продолжения выполнения, ожидая, пока некоторые значения ошибки не вызовут исключение.
Обнаружение аномалии в основном достигается с помощью двух переменных, modCount иожидаемыйModCount,
- modCount
Количество модификаций коллекции, которое обычно хранится в коллекции (например, ArrayList).Каждый раз, когда вызывается метод add(), метод remove() возвращает modCount+1
- expectedModCount
Ожидаемый modCount обычно хранится в Iterator (объект итератора, возвращаемый методом ArrayList.iterator()). Как правило, начальное значение присваивается при инициализации Iterator, а expectModCount обновляется при вызове метода remove() объекта Итератор называется. (Вы можете посмотреть исходный код ArrayList.Itr выше)
Затем, когда итератор вызывает next() для обхода элементов, вызывается метод checkForCommodification() для сравнения modCount и ожидаемогоModCount, и если они несовместимы, генерируется ConcurrentModificationException.
ConcurrentModificationException также возникает, когда однопоточный итератор не работает должным образом. (пример выше)
Суммировать
Поскольку итераторы ArrayList и HashMap являются упомянутыми выше «отказоустойчивыми итераторами», итератор будет сравнивать ожидаемыйModCount и modCount при получении следующего элемента и удалении элемента, и если они несовместимы, будет выдано исключение.
Поэтому при использовании Iterator для обхода элементов (для каждого обхода базовая реализация также является Iterator), вам нужно удалить элементы, вы должны использоватьМетод итератора remove()Для удаления вместо непосредственного вызова метода remove() самого ArrayList или HashMap, иначе ожидаемыйModCount в итераторе не будет обновляться вовремя, а при получении следующего элемента или удалении элемента ожидаемыеModCount и modCount несовместимы , а затем создается исключение ConcurrentModificationException.