I. Обзор
HashMap — это хэш-таблица, в которой хранится карта значений ключа, представляющая собой асинхронную реализацию интерфейса Map на основе хэш-таблицы. Эта реализация предоставляет все необязательные операции с картами и допускает нулевые значения и нулевые ключи.
Как разработчики Java, мы обычно часто используем HashMap.Вы когда-нибудь задумывались, как реализован HashMap? Есть ли что-то, на что нам нужно обратить внимание при использовании HashMap? Как его использовать, чтобы максимизировать эффективность HashMap? Затем мы отвечаем на эти вопросы и читаем исходный код HashMap, чтобы раскрыть тайну HashMap.Обратите внимание, что версия исходного кода jdk, прочитанная на этот раз, — 1.8.
2. Шпионить за структурой данных HashMap
Давайте сначала рассмотрим свойства и методы построения HashMap, чтобы получить предварительное представление о HashMap и понять, что это за структура данных.
/**
/**hashMap默认容量，1<<4=16**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默认最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子0.75，后续用来扩容的判断条件
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转换为红黑树的阈值，默认是8
static final int TREEIFY_THRESHOLD = 8;
//红黑树转换链表的阀值，默认是6
static final int UNTREEIFY_THRESHOLD = 6;
//进行链表转换最少需要的数组长度，如果没有达到这个数字，只能进行扩容
static final int MIN_TREEIFY_CAPACITY = 64;
//节点数组
transient Node<K,V>[] table;
//map的Entry缓存
transient Set<Map.Entry<K,V>> entrySet;
//map中存放的键值对数目
transient int size;
//记录这个map数据结构发生改变的次数,用于快速失败机制
transient int modCount;
//实际的负载因子
final float loadFactor;
//内部类，节点类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
//HashMap指定容量和加载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//指定容量的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默认的构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//直接给定Map的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
Прочитав метод построения и свойства HashMap выше, мы знаем, что есть 3 наиболее важных элемента HashMap: первый — это емкость, второй — коэффициент загрузки, а третий — построение узла Node. Емкость HashMap по умолчанию — 16. Вы также можете указать емкость для создания.Коэффициент загрузки по умолчанию — 0,75.Когда коэффициент использования емкости HashMap достигает 0,75 от общего соотношения, емкость будет расширена. HashMap объявляет массив узлов Node, и в то же время узлы Node могут указывать на следующий Node, поэтому пока внутренняя структура данных HashMap, вероятно, такая (в будущем она изменится, что будет подробно позже):
Зная приблизительную структуру данных HashMap, давайте разберемся с общими методами HashMap и посмотрим, как HashMap добавляет, ищет, удаляет, расширяет и другие операции.
В-третьих, исходный код общего метода HashMap
- put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**真正的put方法逻辑*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table还没初始化就进行扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**如果计算出来table数组索引[i]为空，就直接构造新节点赋值*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/**如果计算出的Hash值索引一样，同时key也一样，如果onlyIfAbsent为true就忽略，否则覆盖原来的value*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/**判断是否为树节点，如果是就调用树节点添加方法*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
/**如果当前key对应的hash索引是最后一个的话*/
if ((e = p.next) == null) {
/**构造新的节点添加到尾部*/
p.next = newNode(hash, key, value, null);
/**如果该节点链表数大于等于8*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
/**进行红黑树转换*/
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
/**判断是否需要覆盖相同key的value**/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
/***用于支持LinkedHashMap的方法*/
afterNodeAccess(e);
return oldValue;
}
}
/**记录修改次数*/
++modCount;
if (++size > threshold)
//扩容
resize();
/***用于支持LinkedHashMap的方法*/
afterNodeInsertion(evict);
return null;
}
HashMap вызывает метод put, сначала вычисляет значение индекса массива таблиц с помощью Hash(key)&(table.length-1), а затем, если позиция равна null, напрямую создает новый узел и присваивает значение; если текущий position уже имеет Если ключ равен и onlyIfAbsent одновременно имеет значение true, то новый элемент будет проигнорирован (значение по умолчанию — false). Если ключи не равны, построить новый узел узла и разместить его в конце последнего узла.При этом, если количество узлов связанных списков больше или равно 8, связанный список становится красно-черным преобразование дерева будет выполнено. Наконец, если размер карты превышает общий размер более чем в 0,75 раза, она будет расширена.
- get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//真正执行HashMap的get()方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断如果key的索引位置不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断该位置第一个元素的key和hash值是否一样，一样就返回该元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果第一个元素不是查找的key，那么判断链表是否还有元素
if ((e = first.next) != null) {
//如果是树节点，执行树节点查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//不是树节点，循环遍历查找，直到查找到对应的key或者最后一个元素为止
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Метод get HashMap проще, чем метод put.Во-первых, оценивается, является ли первый индекс индекса искомым ключом, а если нет, то выполняется цикл по связанному списку.
Приведенный выше исходный код приводит к новому контенту, вычислению хэша, преобразованию красно-черного дерева и расширению. Далее давайте проанализируем содержимое этих трех частей и посмотрим, как HashMap вычисляет индекс, преобразует красно-черное дерево и расширяет емкость.
- Рассчитать хэш-значение
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Вычисление хеш-значения здесь заключается не в том, чтобы напрямую найти хэш-код ключа, а в том, чтобы получить значение хэш-кода и затем выполнить операцию, хэш-код беззнаковый и сдвигается вправо на 16 бит, а затем выполняется операция XOR. с исходным значением. Зачем вы это делаете? Разве его нельзя рассчитать, непосредственно проанализировав метод хэш-кода? Для такого дизайна есть причина: мы знаем, что HashMap, наконец, вычисляет позицию индекса через(n - 1) & hashДля расчета n — это длина массива, этот метод на самом деле является операцией остатка n, мы знаем, что битовая операция выполняется быстрее, чем операция остатка, так что это тоже оптимизация. Итак, почему вам нужно смещаться вправо, когда вы хотите найти значение хэша? Потому что у нас n, то есть длина табличного массива, относительно невелика.При выполнении битовых операций в операции участвуют только младшие биты, а старшие биты в операции не участвуют.Например , значение по умолчанию n=16, преобразованное в 32-битную двоичную систему00000000000000000000000000010000, Следовательно, так как старшие биты n все равны 0, выполнять битовые операции бессмысленно.Поэтому, чтобы старшие биты тоже участвовали в операции, сначала сдвиньте 16 бит вправо, а затем выполните операцию XOR с собой.Это может увеличить случайность хеш.пола, снизить вероятность столкновения. Давайте проанализируем это через диаграмму:
Мы предполагаем, что двоичное значение хеш-значения:00101010101010101010101011111101, n по умолчанию равно 16, и процесс расчета выглядит следующим образом:
Конечный результат преобразуется в десятичное число: 7, которое вычисляет позицию, в которой ключ может быть кэширован в позиции, где индекс массива равен 7.
- трансформация красно-черного дерева
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//判断table数组长度是否小于64，如果小于就进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//把普通节点转换成红黑树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果尾部节点为空，那么说明没有确定头部节点，设置该节点为头部节点
if (tl == null)
hd = p;
else {
//如果已经存在尾部节点，那么把刚刚转换的p节点设置为尾部节点
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//节点转换完成后，确定了头部节点，开始进行红黑树转换
if ((tab[index] = hd) != null)
//把普通treeNode列表转换成为红黑树
hd.treeify(tab);
}
}
Основной операцией здесь является преобразование обычных узлов node в узлы treeNode, в это время он все еще находится в виде связанного списка в начале, а окончательное преобразование красно-черного дерева зависит отhd.treeify(tab)метод преобразования.
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//确定root节点，如果root为空，就设置当前节点为root节点，并设置是黑节点。
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
//如果root节点已经确定，就开始构造红黑树，下面是左节点和右节点的确定，涉及到排序。
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//遍历root，把节点x插入到红黑树中，执行先插入，后修正
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//比较k和pk的值，用于判断是遍历左子树还是右子树
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
Выше приведен процесс формирования красно-черного дерева.Из-за недостатка места, как повернуть красно-черное дерево сзади, что требует базовых знаний о структуре данных, в этой статье не обсуждается. После создания дерева HashMap реальная структура в настоящее время выглядит следующим образом:
- Расширение
final Node<K,V>[] resize() {
// 当前table保存
Node<K,V>[] oldTab = table;
//保存table的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//保存当前阈值
int oldThr = threshold;
int newCap, newThr = 0;
//如果当前table的长度大于0
if (oldCap > 0) {
//当前table已经是最大长度了，无法扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否则扩容为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果当前table大容量等于0，并且阈值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
//设定新容量就是阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//容量和阈值都给默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//计算新阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//初始化新table数组。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//旧table数组不为null,说明已经初始化过了。
if (oldTab != null) {
//循环遍历旧table数组的元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//这里应该是为了垃圾回收。
oldTab[j] = null;
//如果当前遍历的元素，没有后续节点
if (e.next == null)
//直接把元素赋值给扩容后的数组中
newTab[e.hash & (newCap - 1)] = e;
//如果是树节点，进行树节点分割操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 将table中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成重新计算hash操作
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Вот что сложнее понять, так это то, что(e.hash & oldCap) == 0Создать два связанных списка, а потом присвоить им исходную позицию развернутой таблицы или "исходная позиция + oldCap", как вы тут это понимаете? Поскольку мы используем степень расширения 2 (то есть в 2 раза больше исходной), после расширения значение хеш-функции пересчитывается, и элемент либо находится в исходной позиции, либо исходная позиция перемещается в степени 2. Мы используем картинку, чтобы проиллюстрировать этот механизм проектирования:
(e.hash & oldCap)Если он равен 0, вы можете знать положение элемента в новой таблице, и вам не нужно пересчитывать хеш-значение каждого элемента.Вот оптимизация расширения jdk1.8. Приведенный выше исходный код включает разделение красно-черных деревьев по тому же принципу, что и перераспределение связанных списков, и делается то же суждение.(e.hash & oldCap)Будь то 0 или нет, его можно разделить на 2 дерева. Разница лишь в том, что он включает в себя вращение и изменение цвета красно-черного дерева. Заинтересованные студенты могут прочитать его самостоятельно. На этот раз он не будет анализироваться. по космическим причинам.
4. Резюме
- Длина инициализации HashMap по умолчанию равна 16, а коэффициент загрузки равен 0,75.Требования для преобразования красно-черного дерева должны состоять в том, чтобы количество связанных списков было больше 8. При этом длина массива таблицы должна быть больше 64, иначе его можно только расширить.
- HashMap может определить первую емкость только после фактического выполнения метода put, что может сэкономить место.
- HashMap вычисляет хеш-значение ключа, чтобы уменьшить коллизии и повысить случайность расчета индекса, а также вычисляет старший бит хеш-значения с исходным хэш-значением.
- HashMap выполняет операцию с деревом, сначала проходит узлы связанного списка, преобразует их в узлы дерева, а затем строит красно-черное дерево, сначала определяет корневой узел, затем определяет левое и правое деревья, вставляет узлы дерева и, наконец, исправляет красный. -черное дерево (изменение цвета и т.д.)
- Расширение HashMap, каждое расширение до степени 2 (то есть в 2 раза больше исходного), расширение для определения новой позиции элемента должно быть в порядке только с битовой операцией исходного значения емкости, что позволяет избежать пересчета хэша значение операции всех элементов.
5. Ссылка
Механизм расширения HashMap --- resize()
Переосмысление HashMap в серии Java 8
6. Рекомендуемое чтение
"ReentrantLock блокировки Java (1)》
"ReentrantLock из Java Lock (2)》
"ReentrantReadWriteLock блокировки Java》
"Введение в программирование JAVA NIO (1)》
"Введение в программирование JAVA NIO (2)》