问题
- HashMap 底层是如何实现的？在 JDK 1.8 中它都做了哪些优化？
- JDK 1.8 HashMap 扩容时做了哪些优化？
- 加载因子为什么是 0.75？
- 当有哈希冲突时，HashMap 是如何查找并确认元素的？
- HashMap 是如何导致死循环的？
简述
HashMap 采用key/value存储结构，每个key 对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序。
在jdk1.7中HashMap是以数组加链表的形式组成，jdk1.8之后新增了红黑树的组成结构，当链表大于8并且容量大于64时，链表结构会转换红黑树结构。
它的组成结构如下图所示：
源码分析
Map 类图
属性
//默认的初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子(扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当链表长度大于此值且容量大于64时 转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//从红黑树转换成链表的临界值，当元素长度小于此值，会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;
//最小树容量
static final int MIN_TREEIFY_CAPACITY = 64;
//数组，又叫做桶(bucket)
transient Node<K,V>[] table;
//作为entrySet() 缓存
transient Set<Map.Entry<K,V>> entrySet;
//元素的数量
transient int size;
//修改次数，用于在迭代的时候执行快速失败策略，会比较modCount
transient int modCount;
//当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor 默认是 12 = 16 * 0.75
int threshold;
//加载因子
final float loadFactor;
javadoc中对扩容因子的一些解释：
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations
of the HashMap class, including get and put). The expected number of entries in the map and its load factor
should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations.
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations
will ever occur.
-
默认的加载因子值为
0.75在时间和空间成本之间做出了一个很好的权衡 -
如果把值设置的高的话，减少空间开销因为扩容门槛
变高，扩容发生的几率就会变低但此时发生 Hash冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低 -
而当加载因子值比较小的时候，扩容的门槛会比
较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。
所以就取了一个0.5到1.0的平均数0.75作为加载因子
Node内部类
//数组中的元素我们称之为哈希桶，它的定义如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
可以看出每个哈希桶中包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
JDK1.8之所以添加红黑树是因为一旦链表过长，会严重影响HashMap 的性能，而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长时操作比较慢的问题。
TreeNode内部类
TreeNode 是一个树型节点，其中，prev是链表中的节点，用于删除元素的时候可以快速找到它的前置节点
//位于HashMap
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
boolean red;
}
//位于LinkedHashMap中，双向链表
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
HashMap( )构造方法
//空参构造方法，全部使用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//调用HashMap(int initialCapacity, float loadFactor)构造方法，传入默认装载因子。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//判断传入的初始容量和装载因子是否合法，并计算扩容门槛，扩容门槛为传入的初始容量往上取最近的2的n次方。
public HashMap(int initialCapacity, float loadFactor) {
//<1> 检查传入的初始容量是否合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//<2> 检查装载因子是否合法
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//<3> 计算扩容门槛
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
// 扩容门槛为传入的初始容量往上取最近的2的n次方
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;
}
HashMap.get( )方法
public V get(Object key) {
Node<K,V> e;
//调用getNode()方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
//<1> 如果桶中的数量大于0 并且待查找的key所在桶中的第一个元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//<2> 判断要获取的元素是不是第一个元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//如果是的话直接返回第一个元素
return first;
//<3> 不满足<2> 则判断下一个元素是否为空
if ((e = first.next) != null) {
//<3.1> 如果第一个元素是树节点，那就按照树的方式查找调用 TreeNode#getTreeNode( )方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//<3.2> 遍历整个链表查找该元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
(1) 判断桶是否为空，根据key的hash值找到key所在的桶及其第一个元素
(2) 如果第一个元素的key等于待查找的key，直接返回
(3) 如果第一个元素是树节点就按树的方式来查找，否则按链表方式查找
TreeNode.getTreeNode(int h, Object k)方法
HashMap#get()方法中的<3.1> 如果第一个元素是树节点，那么就会调用次方法用树的方式来查找元素
//第一个参数为hash(key)，第二个参数为key
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 从树的根节点开始查找
return ((parent != null) ? root() : this).find(h, k, null);
}
//kc参数是：在第一次使用比较键时的缓存comparableClassFor(key)。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir;
K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//左子树 根据二叉树的特性 左节点永远要比父节点小，
//所以如果根节点的左节点比需要找的key 大的话，以左节点继续向下搜索
if ((ph = p.hash) > h)
p = pl;
//右子树 跟上面同理
else if (ph < h)
p = pr;
//找到了那个节点 直接返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//hash相同但key不同，左子树为空查右子树
else if (pl == null)
p = pr;
// 右子树为空查左子树
else if (pr == null)
p = pl;
// 通过compare方法比较key值的大小决定使用左子树还是右子树
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
// 如果以上条件都不通过，则尝试在右子树查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
//都没有找到则在左子树查找
p = pl;
} while (p != null);
return null;
}
经典二叉查找树的查找过程，先根据hash值比较，再根据key值比较决定是查左子树还是右子树。
左节点的值永远比其父节点的值要小右节点的值永远比其父节点的值要大
put( )方法
添加元素方法
public V put(K key, V value) {
// 调用hash(key)计算出key的hash值
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 如果key为null，则hash值为0，否则调用key的hashCode()方法
// 并让高16位与整个hash异或，这样做是为了使计算出的hash更分散
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//onlyIfAbsent 为false ，如果为true那么不会修改已经存在的值(不会替换)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//<1> 如果数组为空 那么调用resize进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
//resize进行初始化
n = (tab = resize()).length;
//<2> 根据 (n - 1) & hash 计算出 key 应该存放在哪个桶中
// 如果桶中还没有该元素，则调用newNode方法创建并放去第一个位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//<3> 已经存在了
Node<K,V> e;
K k;
//<3.1> 如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//<3.2> 如果第一个元素是树节点，则调用树节点的putTreeVal方法插入该元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//<3.3> 遍历这个桶对应的链表，binCount 用于存储链表中元素的个数
else {
for (int binCount = 0; ; ++binCount) {
//如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果插入新节点后链表长度大于8，则判断是否需要树化，因为第一个元素没有加到binCount中，所以这里-1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果待插入的key在链表中找到了，则退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//<4> 如果找到了对应key的元素
if (e != null) { // existing mapping for key
//<4.1> 记录旧值
V oldValue = e.value;
//<4.2> 根据onlyIfAbsent判断是否要替换，为false
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//<4.3> 在节点被访问后做点什么事，在LinkedHashMap中用到
afterNodeAccess(e);
//<4.4> 返回旧值
return oldValue;
}
}
//<5> 到这里说明没有找到旧值，添加了一个新值，修改次数+1
++modCount;
//<6> 判断是否需要扩容
if (++size > threshold)
resize();
//<7> 在节点插入后做点什么事，在LinkedHashMap中用到
afterNodeInsertion(evict);
//没找到元素返回null
return null;
}
(1) 计算key的hash值
(2) 如果桶（数组）数量为0，则初始化桶
(3) 如果key所在的桶没有元素，则直接插入
(4) 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理；
(5) 如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
(6) 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
(7) 如果找到了对应key的元素，则转后续流程（9）处理
(8) 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
(9) 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
(10) 如果插入了元素，则数量加1并判断是否需要扩容
下面是一整张流程图：
resize( )方法
扩容/初始化 方法
final Node<K,V>[] resize() {
//旧数组
Node<K,V>[] oldTab = table;
//旧容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧扩展门槛
int oldThr = threshold;
int newCap, newThr = 0;
//<1> 如果旧的容量 > 0 说明是扩容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//<1.1> 如果旧容量达到了最大容量，则不再进行扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//<1.2> 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则新容量为就容量的两倍，扩容门槛也扩大为两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//<2> 初始化，在上面的putVal方法中的<1>中有所体现
else if (oldThr > 0) // initial capacity was placed in threshold
// 使用非默认构造方法创建的map，第一次插入元素会走到这里
// 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 调用默认构造方法创建的map，第一次插入元素会走到这里
// 如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//<3> 如果新扩容门槛为0，则计算为容量*装载因子，但不能超过最大容量
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"})
//新建一个新容量的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//把桶赋值为新数组
table = newTab;
//<4> 如果旧桶不为空，则搬移元素到新桶中；为空就是初始化的情况
if (oldTab != null) {
//遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果桶中第一个元素不为空，赋值给e
if ((e = oldTab[j]) != null) {
//清空旧桶，便于GC回收
oldTab[j] = null;
//<4.1> 如果这个桶中只有一个元素，则计算它在新桶中的位置并把它搬移到新桶中
// 因为每次都扩容两倍，所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//<4.2> 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//<4.3> 这个桶有多个元素，并且不是树 则分化成两个链表插入到新的桶中去
// 比如，假如原来容量为4， 3、7、11、15这四个元素都在三号桶中
// 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
// 也就是分化成了两个链表
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;
// (e.hash & oldCap) == 0的元素放在低位链表中 比如，3 & 4 == 0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// (e.hash & oldCap) != 0的元素放在高位链表中 比如，7 & 4 != 0
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//遍历完成分化成两个链表了
//低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
(1) 如果使用默认构造函数，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12
(2) 如果使用的非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
(3) 如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
(4) 创建一个新容量的桶(旧容量的2倍)
(5) 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置；
TreeNode.putTreeVal(…)方法
插入元素到红黑树中
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
// 标记是否找到这个key的节点
boolean searched = false;
// 找到树的根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
// 从树的根节点开始遍历
for (TreeNode<K,V> p = root;;) {
// dir=direction，标记是在左边还是右边
// ph=p.hash，当前节点的hash值
int dir, ph; K pk;
// 当前hash比目标hash大，说明在左边
if ((ph = p.hash) > h)
dir = -1;
// 当前hash比目标hash小，说明在右边
else if (ph < h)
dir = 1;
//两者hash相同且key相等，说明找到了节点，直接返回该节点
// 回到putVal()中判断是否需要修改其value值
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//如果k是Comparable的子类则返回其真实的类，否则返回null
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
//如果k和pk不是同样的类型则返回0，否则返回两者比较的结果
(dir = compareComparables(kc, k, pk)) == 0) {
// 这个条件表示两者hash相同但是其中一个不是Comparable类型或者两者类型不同
// 比如key是Object类型，这时可以传String也可以传Integer，两者hash值可能相同
// 在红黑树中把同样hash值的元素存储在同一颗子树，这里相当于找到了这颗子树的顶点
// 从这个顶点分别遍历其左右子树去寻找有没有跟待插入的key相同的元素
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//遍历左右子树找到了直接返回
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//如果两者类型相同，再根据它们的内存地址计算hash值进行比较
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//如果最后确实没找到对应key的元素，则新建一个节点
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入树节点后平衡 把root节点移动到链表的第一个节点
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
(1) 寻找根节点
(2) 从根节点开始查找
(3) 比较hash值及key值，如果都相同，直接返回，在putVal()方法中决定是否要替换value值
(4) 根据hash值及key值确定在树的左子树还是右子树查找，找到了直接返回
(5) 如果最后没有找到则在树的相应位置插入元素，并做平衡
treeifyBin()方法
如果插入元素后链表的长度大于等于8则判断是否需要树化。 在上面的putVal方法中<3.3>有所体现
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
// 如果桶数量小于64，直接扩容而不用树化
// 因为扩容之后，链表会分化成两个链表，达到减少元素的作用
// 当然也不一定，比如容量为4，里面存的全是除以4余数等于3的元素
// 这样即使扩容也无法减少链表的长度
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.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//如果进入过上面的循环，则从头节点开始树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
TreeNode.treeify()方法
真正树化的方法。
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;
// 第一个元素作为根节点且为黑节点，其它元素依次插入到树中再做平衡
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 从根节点查找元素插入的位置
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)
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;
//插入后平衡，默认插入的是红节点，在balanceInsertion()方法里
root = balanceInsertion(root, x);
break;
}
}
}
}
//把根节点移动到链表的头节点，因为经过平衡之后原来的第一个元素不一定是根节点了
moveRootToFront(tab, root);
}
(1) 从链表的第一个元素开始遍历
(2) 将第一个元素作为根节点
(3) 其它元素依次插入到红黑树中，再做平衡
(4) 将根节点移到链表第一元素的位置（因为平衡的时候根节点会改变）
remove
public V remove(Object key) {
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) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果第一个元素正好就是要找的元素，赋值给node变量后续删除使用
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//如果第一个元素是树节点，则以树的方式查找节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
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);
}
}
// 如果找到了元素，则看参数是否需要匹配value值，如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是树节点，调用树的删除方法（以node调用的，是删除自己）
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果待删除的元素是第一个元素，则把第二个元素移到第一的位置
else if (node == p)
tab[index] = node.next;
else
//否则删除node节点
p.next = node.next;
++modCount;
--size;
//删除节点后置处理
afterNodeRemoval(node);
return node;
}
}
return null;
}
(1) 先查找元素所在的节点
(2) 如果找到的节点是树节点，则按树的移除节点处理
(3) 如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置
(4) 否则按链表删除节点处理
(5) 修改size，调用移除节点后置处理等
TreeNode.removeTreeNode(…)方法
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//如果桶的数量为0直接返回
if (tab == null || (n = tab.length) == 0)
return;
//节点在桶中的索引
int index = (n - 1) & hash;
// 第一个节点，根节点，根左子节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// 后继节点，前置节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
// 如果前置节点为空，说明当前节点是根节点，则把后继节点赋值到第一个节点的位置，相当于删除了当前节点
tab[index] = first = succ;
else
// 否则把前置节点的下个节点设置为当前节点的后继节点，相当于删除了当前节点
pred.next = succ;
// 如果后继节点不为空，则让后继节点的前置节点指向当前节点的前置节点，相当于删除了当前节点
if (succ != null)
succ.prev = pred;
// 如果第一个节点为空，说明没有后继节点了，直接返回
if (first == null)
return;
// 如果根节点的父节点不为空，则重新查找父节点
if (root.parent != null)
root = root.root();
// 如果根节点为空，则需要反树化（将树转化为链表）
// 如果需要移动节点且树的高度比较小，则需要反树化
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// 分割线，以上都是删除链表中的节点，下面才是直接删除红黑树的节点（因为TreeNode本身即是链表节点又是树节点）
// 删除红黑树节点的大致过程是寻找右子树中最小的节点放到删除节点的位置，然后做平衡
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
(1) TreeNode本身既是链表节点也是红黑树节点
(2) 先删除链表节点
(3) 再删除红黑树节点并做平衡
HashMap 死循环分析
以JDK1.7为例，假设HashMap默认大小为2，原本HashMap中有一个元素key(5)，我们再使用两个线程：t1添加元素key(3)，t2添加元素key(7)，
当元素key(3) 和 key(7) 都添加到 HashMap 中之后，线程 t1 在执行到 Entry<K,V> next = e.next; 时，交出了 CPU 的使用权，
源码如下：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null!=e){
Entry<K,V>next=e.next;//线程一执行此处
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
那么此时线程t1中的e指向了key(3)，而next指向了key(7)；之后线程t2重新rehash之后链表的顺序被反转，
链表的位置变成了key(5)→key(7)→ key(3)，其中 “→” 用来表示下一个元素。
当t1重新获得执行权之后，先执行newTalbe[i]=e把key(3)的next设置为key(7)，而下次循环时查询到key(7)的next元素为key(3)，
于是就形成了 key(3) 和 key(7) 的循环引用，因此就导致了死循环的发生，如下图所示：
当然发生死循环的原因是 JDK 1.7 链表插入方式为首部倒序插入，这个问题在 JDK 1.8 得到了改善，变成了尾部正序插入。
总结
-
HashMap 是一种散列表，采用(数组 + 链表 + 红黑树) 的存储结构
-
HashMap 的默认初始容量为16，默认装载因子为0.75f，容量总是2的n次方
-
HashMap扩容时每次容量变为原来的两倍
- JDK 1.7 会
重新计算每个元素的哈希值然后移动到新桶中 - JDK 1.8 通过
高位运算（e.hash & oldCap）来确定元素是否需要移动
- JDK 1.7 会
-
当桶的数量小于64时不会进行树化，只会扩容
-
当桶的数量大于64且单个桶中元素的数量大于8时，进行树化
-
当单个桶中元素数量小于6时，进行反树化退化成链表
-
HashMap是非线程安全的容器
-
HashMap查找添加元素的时间复杂度都为O(1)
-
HashMap在Jdk1.7 中在多线程情况下发生扩容，在cpu切换线程使用权的时候会发生死循环
- Jdk1.7 插入方式为首部倒序插入。
- 假如有两个线程同时插入元素后发生扩容，线程一还没执行rehash反转的时候，cpu切换让线程二执行，然后线程二执行反转后。后变成死循环了
- Jdk1.8 改为顺序尾部插入改善此情况。
-
红黑树具有以下5种性质：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶节点（NIL节点，空节点）是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 红黑树的时间复杂度为O(log n)，与树的高度成正比。
- 红黑树每次的插入、删除操作都需要做平衡，平衡时有可能会改变根节点的位置，颜色转换，左旋，右旋等。