面试-Java【之】HashMap原理，源码逐行分析，理论总结（变量、常量、数据结构、Node、TreeNode、初始化、添加、查询、更新、删除）
1.源码分析
1.HashMap属性与变量（扩容因子、扩容阈值、结构转换阈值…）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
//默认扩容的临界值（table大于此值时，进行扩容）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//扩容临界值的最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
//链表转红黑树的大小阈值（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
static final int TREEIFY_THRESHOLD = 8;
//链表转红黑树的大小阈值（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
static final int MIN_TREEIFY_CAPACITY = 64;
//红黑树转链表的阈值（当链表长度小于6，并且数组长度小于64时， 红黑树数据结构，转为链表）
static final int UNTREEIFY_THRESHOLD = 6;
//当前扩容因子（扩容时的倍数），默认0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//数组（内部存储 Node链表节点，或者，TreeNode红黑树节点）
transient Node<K,V>[] table;
//扩容的临界值（table大于此值时，进行扩容）,默认值 DEFAULT_INITIAL_CAPACITY
int threshold;
//当前扩容因子（扩容时的倍数）
final float loadFactor;
}
2.Node（链表节点）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
//当前节点-hash
final int hash;
//当前节点-key
final K key;
//当前节点-value
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;
}
}
}
3.TreeNode（红黑树节点）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//父节点
TreeNode<K,V> parent; // red-black tree links
//相邻左侧节点
TreeNode<K,V> left;
//相邻右侧节点
TreeNode<K,V> right;
//上一页
TreeNode<K,V> prev; // needed to unlink next upon deletion
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
}
4.初始化（new）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
//设置扩容因子，和，扩容临界值，并未初始化数组
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);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//设置扩容因子，和，扩容临界值，并未初始化数组
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参构造函数，设置扩容临界值，并未初始化数组
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//设置扩容临界值，并，插入数据
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
5.插入、更新（put、putVal）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
//key : 键
//value : 值
//hash(key) : 调用对象自身的 hash方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//tab:当前数组
//i:数据在tab中的索引下标
//p:在tab中，key对应的下标节点数据，也就是 tab[i]
//n:tab长度
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果tab为空，执行初始化或扩容数组
//resize() ：初始化或扩容数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果tab中当前位置没有数据，直接创建并插入节点
//i是tab中，数据对应存放的位置： = (n - 1) & hash
//p是tab中，数据对应存放的值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果位置上已经有数据，此时出现冲突
else {
//对比当前位置数据的Key，与将要插入的数据的Key，如果一致，直接替换数据 e = p;
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果Key不一致，判断是否为红黑树节点，是则插入数据
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果Key不一致，也不是红黑树节点
else {
//循环比对当前链表内的Key
//如果不存在，则直接插入，如果存在一致，则替换
for (int binCount = 0; ; ++binCount) {
//如果不存在，则直接插入
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
//判断扩容阈值
if (++size > threshold)
resize();
//在HashMap中这里是空实现
afterNodeInsertion(evict);
return null;
}
}
6.删除（remove、removeNode）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
//key:删除条件KEY
public V remove(Object key) {
//e:被删除的节点
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab:当前数组
//n:当前数组长度
//index:key对应的在数组中的下标
//p:key对应在数组中的数据 ,也就是tab[index]
Node<K,V>[] tab; Node<K,V> p; int n, index;
//如果tab不等于空，并且对应index下标位置有数据，则判断通过
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node：将要被删除的节点
Node<K,V> node = null, e; K k; V v;
//继续判断，hash相同，key相同，则被删除节点就是当前下标数据，也就是 node=tab[index]
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//如果当前位置Node节点不满足条件，则继续判断
else if ((e = p.next) != null) {
//如果当前节点是红黑树，则获取节点数据，赋值给node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//否则，循环从链表中读取，找到后，赋值给node
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//判断被删除节点不为空，执行删除逻辑
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//删除红黑树节点
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//删除Node节点(将原有位置数据的引用，指向链表中下一个数据，实现删除逻辑)
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
}
7.读取（get、getNode）
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
//e:读取结果
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//tab:当前数组
//n:当前数组长度
//first:key对应在数组中的数据 , 也就是tab[index]
//k:first的key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//数组不为空，并且first不等于空，继续执行
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//first的 hash与key 和 传入的一致，证明 first就是查询结果，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//比对结果不一致，继续判断
if ((e = first.next) != null) {
//如果first位置的Node是红黑树，直接获取数据
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果first位置的Node是链表，遍历链表获取数据
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
}
2.理论总结
1.核心：数组+ 链表或者红黑树
- 核心：数组
Node<K,V>[] table + 链表或者红黑树
- 因为这种存储结构，所以，HashMap的查询效率高：第一次查询是 O(1) , 第二次是 O(n)
- 1.初始化：new：确定 扩容因子
loadFactor 和 临界点 threshold,并没有初始化数组，初始化数组是在第一次查询数据时 resize()内实现的
2.put 操作：首次插入：无冲突情况
- 2.put 操作：首次插入：无冲突情况
- 1.计算KEY的Hash值 ; 例如 “a” 的HashCode 是 97
- 2.判断临界点
threshold 是否扩容，更新临界点
- 3.创建Node（链表结构） ，存放位置
i = (数组长度 - 1) & hash
- 4.再次判断并更新临界点
3.put 操作：继续操作：出现突情况时
- 3.put 操作：继续操作：出现突情况时
- 当 存放位置
i = (数组长度 - 1) & hash 已经存在数据时
- 先判断节点类型，链表还是红黑树
- 是链表，遍历链表
- 如果当前节点的下一个节点不存在，直接创建插入Node，如果存在判断KEY是否相同，相同就覆盖，不同就继续循环
- 创建插入Node后，判断长度，是否转为 红黑树
-
binCount >= TREEIFY_THRESHOLD - 1 链表长度大于8 并且
-
(n = tab.length) < MIN_TREEIFY_CAPACITY 并且 数组长度大于64
- 是红黑树，创建节点插入即可
4.删除：remove
- 4.删除：remove
- 1.计算 KEY 的 Hash值， 找到数组中的位置
- 2.判断KEY是否相同，相同直接删除，不同就判断当前 链表/红黑树 中下一个节点的数据
- 3.删除：将当前位置指向
next数据，实现从链表中删除数据的功能
5.获取：get
- 5.获取：get
- 1.计算 KEY 的 Hash值， 找到数组中的位置
- 2.判断，数组不为空，并且first不等于空，继续执行，为空直接返回
NULL
- 3.如果first位置的Node是红黑树，
getTreeNode（） 获取数据
- 4.如果first位置的Node是链表，遍历链表获取数据
6.补充
- 默认扩容的临界值初始16
- 扩容因子（扩容时的倍数），默认0.75f
- 链表转红黑树（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
- 红黑树转链表的阈值（当链表长度小于6，并且数组长度小于64时， 红黑树数据结构，转为链表）
- Node节点是一个Map链表结构，特点是
next
- TreeNode 是一个 LinkedHashMap ,特点是
parent 父节点 left right prev（上一页）
《目录：Java-JDBC学习》
《幕》
- 留白 —<老吉>
- ~ 今 ~ ❀ ~ ❀❀❀❀❀❀❀❀❀❀ ❀❀❀❀❀❀❀❀❀❀ ❀❀❀❀❀❀❀
