Java 集合系列4、家喻户晓之HashMap（上）
在前面的文章中，我们以及介绍了 List 大家族的相关知识：
- Java 集合系列1、细思极恐之ArrayList
- Java 集合系列2、百密一疏之Vector
- Java 集合系列3、骨骼惊奇之LinkedList
在接下来的文章，则主要为大家介绍一下 Java 集合家庭中另一小分队 Map ，我们先来看看 Map 家庭的整体架构：
在这篇文章中，我们主要介绍一下HashMap：
HashMap 的依赖关系：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- 1、AbstractMap：表明它是一个散列表，基于Key-Value 的存储方式
- 2、Cloneable：支持拷贝功能
- 3、Seriablizable：重写了write/readObject，支持序列化
从依赖关系上面来看， HashMap 并没有 List 集合 那么的复杂，主要是因为在迭代上面，HashMap 区别 key-value 进行迭代，而他们的迭代又依赖与keySet-valueSet 进行，因此，虽然依赖关系上面HashMap 看似简单，但是内部的依赖关系更为复杂。
2、HashMap 成员变量
默认 桶（数组） 容量 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; 负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 链表转树 大小 static final int TREEIFY_THRESHOLD = 8; 树转链表 大小 static final int UNTREEIFY_THRESHOLD = 6; 最小转红黑树容量 static final int MIN_TREEIFY_CAPACITY = 64; 存储数据节点 static class Node<K,V> implements Map.Entry<K,V> 节点数组 transient Node<K,V>[] table; 数据容量 transient int size; 操作次数 transient int modCount; 扩容大小 int threshold;
对比于JDK8之前的HashMap ，成员变量主要的区别在于多了红黑树的相关变量，用于标示我们在什么时候进行 list -> Tree 的转换。
附上Jdk8 中HashMap 的数据结构展示图：
3、HashMap 构造函数
HashMap 提供了四种构造函数：
m
4、HashMap Put 过程
接下来我们主要讲解一下，HashMap 在JDK8中的添加数据过程（引用）：
4.1、put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
上述方法是我们在开发过程中最常使用到的方法，但是却很少人知道，其实内部真正调用的方法是这个 putVal(hash(key), key, value, false, true) 方法。这里稍微介绍一下这几个参数：
- hash 值，用于确定存储位置
- key：存入键值
- value：存入数据
- onlyIfAbsent：是否覆盖原本数据，如果为true 则不覆盖
- onlyIfAbsent：table 是否处于创建模式
4.1.1 hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。 这里引用一张图，易于大家了解相关机制
这里可能会比较疑惑，为什么需要对自身的hashCode 进行运算，这么做可以在数组table 比较小的时候，让高位bit 也能参与到hash 运算中，同时不会又太大的开销。
4.2、putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
由于源码篇幅过长，这里我进行分开讲解，同学们可以对照源码进行阅读
4.2.1 声明成员变量（第一步）
Node<K,V>[] tab; Node<K,V> p; int n, i;
第一部分主要县声明几个需要使用到的成员变量：
- tab：对应table 用于存储数据
- p：我们需要存储的数据，将转化为该对象
- n：数组（table） 长度
- i：数组下标
4.2.2 Table 为 null，初始化Table（第二步）
table 为空说明当前操作为第一次操作，通过上面构造函数的阅读，我们可以了解到，我们并没有对table 进行初始化，因此在第一次put 操作的时候，我们需要先将table 进行初始化。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
从上述代码可以看到，table 的初始化和扩容，都依赖于 resize（） 方法，在后面我们会对该方法进行详细分析。
4.2.3 Hash碰撞确认下标（True）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
在上一步我们以及确认当前table不为空，然后我们需要计算我们对象需要存储的下标了。
如果该下标中并没有数据，我们只需创建一个新的节点，然后将其存入 tab[] 即可。
4.2.4 Hash碰撞确认下标（False）
与上述过程相反，Hash碰撞结果后，发现该下标有保存元素，将其保存到变量 p = tab[i = (n - 1) & hash] ，现在 p 保存的是目标数组下标中的元素。如上图所示(引用)：
4.2.4.1 key 值相同覆盖
在获取到 p 后，我们首先判断它的 key 是否与我们这次插入的key 相同，如果相同，我们将其引用传递给 e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
4.2.4.2 红黑树节点处理
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
由于在JDK 8后，会对过长的链表进行处理，即 链表 -> 红黑树，因此对应的节点也会进行相关的处理。红黑树的节点则为TreeNode，因此在获取到 p 后，如果他跟首位元素不匹配，那么他就有可能为红黑树的内容。所以进行 putTreeVal(this, tab, hash, key, value) 操作。该操作的源码，将会在后续进行细述。
4.2.4.3 链表节点处理
else {
//for 循环遍历链表，binCount 用于记录长度，如果过长则进行树的转化
for (int binCount = 0; ; ++binCount) {
// 如果发现p.next 为空，说明下一个节点为插入节点
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 相同，退出遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//替换 p
p = e;
}
}
链表遍历处理，整个过程就是，遍历所有节点，当发现如果存在key 与插入的key 相同，那么退出遍历，否则在最后插入新的节点。判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
4.2.4.3 判断是否覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
如果 e 不为空，说明在校验 key 的hash 值，发现存在相同的 key，那么将会在这里进行判断是否对其进行覆盖。
4.2.5 容量判断
if (++size > threshold)
resize();
如果 size 大于 threshold 则进行扩容处理。
5、Resize（）扩容
在上面的构造函数，和 put 过程都有调用过 resize（） 方法，那么，我们接下来将会分析一下 resize（） 过程。由于 JDK 8 引入了红黑树，我们先从 JDK 7 开始阅读 resize（） 过程。下面部分内容参考：传送门
5.1 JDK 7 resize()
在 JDK 7 中，扩容主要分为了两个步骤：
- 容器扩展
- 内容拷贝
5.1.1 容器扩展
1 void resize(int newCapacity) { //传入新的容量
2 Entry[] oldTable = table; //引用扩容前的Entry数组
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
5 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
6 return;
7 }
8
9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
10 transfer(newTable); //！！将数据转移到新的Entry数组里
11 table = newTable; //HashMap的table属性引用新的Entry数组
12 threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }
5.1.2 内容拷贝
1 void transfer(Entry[] newTable) {
2 Entry[] src = table; //src引用了旧的Entry数组
3 int newCapacity = newTable.length;
4 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
5 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
6 if (e != null) {
7 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
8 do {
9 Entry<K,V> next = e.next;
10 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
11 e.next = newTable[i]; //标记[1]
12 newTable[i] = e; //将元素放在数组上
13 e = next; //访问下一个Entry链上的元素
14 } while (e != null);
15 }
16 }
17 }
5.1.3 扩容过程展示（引用）
下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。
5.2 JDK 8 resize()
由于扩容部分代码篇幅比较长，童鞋们可以对比着博客与源码进行阅读。 与上述流程相似， JDK 8 中扩容过程主要分成两个部分：
- 容器扩展
- 内容拷贝
5.2.1 容器扩展
Node<K,V>[] oldTab = table; //创建一个对象指向当前数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取旧数组的长度
int oldThr = threshold; //获取旧的阀值
int newCap, newThr = 0;
// 第一步，确认数组长度
if (oldCap > 0) { //如果数组不为空
if (oldCap >= MAXIMUM_CAPACITY) { //当容器大小以及是最大值时
threshold = Integer.MAX_VALUE; //设置阀值为最大值，并且不再做扩容处理
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 容器扩容一倍，并且将阀值设置为原来的一倍
newThr = oldThr << 1; // double threshold
}
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);
}
// 第二步，创建新数组
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
从上面的流程分析，我们可以看到在 JDK 8 HashMap 中，开始使用位运算进行扩容计算，主要优点将会在后续数据拷贝中具体表现。
5.2.2 内容拷贝
在上述容器扩容结束后，如果发现 oldTab 不为空，那么接下来将会进行内容拷贝：
if (oldTab != null) {
//对旧数组进行遍历
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//
if ((e = oldTab[j]) != null) {
//将旧数组中的内容清空
oldTab[j] = null;
//如果 e 没有后续内容，只处理当前值即可
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;
//高位 与运算，确定索引为原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//高位与运算，确认索引为 愿索引+ oldCap
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;
}
}
}
}
}
内容拷贝，在 JDK 8 中优化，主要是：
- 通过高位与运算确认存储地址
- 链表不会出现导致，JDK 8 通过创建新链表方式进行转移
我们来看一下 JDK 8 是如何通过高位与运算确认存储位置的：
6、小结
HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。
(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能。
(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
