1.定义
HashMap是实现了Map接口的key-value集合，实现了所有map的操作，允许key和value为null,hashMap不是线程安全的。
从上面的定义提出两个疑问
1.HashMap内部的实现是怎样的?
2.HashMap不是线程安全的，是因为什么?
下文的分析将围绕这两个问题开始，另外本文源码来自与JDK_1.8.0_131
2.结构
2.1 类图结构
image
如上图所示，是HashMap的类图结构，其主要实现、继承了以下接口和类:
1.Map 接口： 定义将键值映射到值的对象，Map规定不能包含重复的键值，每个键最多可以映射一个值,这个接口是用来替换Dictionary类。
2.AbstractMap 类： 提供了一个Map骨架的实现,尽量减少了实现Map接口所需要的工作量
3.Cloneable 接口： 实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制，如果没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。正常情况下，实现了Cloneable接口的类会以公共方法重写Object.clone()
4.Serializable 接口： 实现了该接口标示了类可以被序列化和反序列化，具体的 查询序列化详解
2.2 基本属性及构造方法
2.2.1 基本属性
HashMap的基本属性如代码所示：
//默认的初始化容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大的容量，容量的值必须是2的幂并且小于最大的容量，最大值为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子默认值为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//计数阈值，超过这个值将会使用树形结构替代链表结构
static final int TREEIFY_THRESHOLD = 8;
//由树形结构转换成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//树形结构最小的容量为64
static final int MIN_TREEIFY_CAPACITY = 64;
//链表数组
transient Node<K,V>[] table;
//HashMap中value的集合
transient Set<Map.Entry<K,V>> entrySet;
//HashMap的长度
transient int size;
//调整大小的下一个大小值
int threshold;
//hashtable的加载因子
final float loadFactor;
2.2.2 构造方法
HashMap提供了4个构造方法，如下所示
1.public HashMap(int initialCapacity, float loadFactor)：需要传入自定义的initialCapacity(初始化容量)，loadFactor(加载因子)
2.public HashMap(int initialCapacity)：需要传入自定义的initialCapacity(初始化容量)，实际在平时的使用过程中如果可以大概知道数据量，建议使用这种构造方法，原因是指定了HashMap的容量之后，可以避免没必要的扩容操作，从而减少了浪费。
3.public HashMap()：默认的构造方法，按照初始值创建HashMap
4.public HashMap(Map<? extends K, ? extends V> m)：需要传入一个Map集合
3.原理
3.1 内部结构
image
如上图所示，是HashMap内部实现的结构图，正如2.2.1中介绍的其内部是个Node<K,V>类型的数组。数组中保存的有两种数据结构，第一种是链表，第二种是树形结构(使用的是红黑树，后面的文章中会做详细介绍)，下面通过源码了解下HashMap是如何实现这样的结构的。
3.2 实现
3.2.1 添加元素
如下为HashMap添加元素的put方法的源码，
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* hash:为hash值
* key:保存的key
* value:保存的value
* onlyIfAbsent:如果为true,不改变已经存在的值
* evict:如果为false,表示table处于创造模式
**/
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是否为空或者长度为0，若是则调用resize()新建数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//然后定位当前需要保存的值在数组中位置，如果没有冲突，即当前位置上没有值则新增节点并将其添加
if ((p = tab[i = (n - 1) & hash]) == null)
//这里当hash=0时，即key值为空时，该值将会保存在tab[0]的位置
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断是否为新增的元素是否为第一个元素(hash与key去判断)，如果是则获取第一个元素
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) {
//循环查找，直到链表末尾，添加新节点
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;
}
// 如果hash与key相等 则终止循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 节点的引用向后移动
p = e;
}
}
// 存在key对应的value时，按照条件替换并返回旧值
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();
afterNodeInsertion(evict);
return null;
}
通过源码可以看出，添加一个元素到HashMap中大体上可以分为三个步骤：
1.定位：首先计算出key对应的hash值，在将(tab.length()-1) & hash方式定位出当前添加的key-value在Node<K,V>[] tab中的索引位置(其实这里有个问题，就是为啥(tab.length()-1) & hash这种方式能保证分配的相对均匀，由于tab.length()是2的n次方的,
(tab.length()-1) & hash运算等于对tab.length()进行取模运算，但是&操作相对于%操作，性能肯定是更优的，疑问为什么更优)
2.解决hash冲突：
首先介绍下解决Hash冲突的方式实际上有两种，第一种是开放寻址，指的是当桶中位置被占据时，将通过探寻的方式，来寻找到未被占据的哈希桶，第二种是分离链接，将每个哈希桶当做链表的头，当发生hash冲突时，在链表中进行操作。而HashMap中使用的方式是第二种方式，这一步是HashMap实现的关键，其步骤如下：
-
1.根据定位在tab中的位置，找到根节点，若根节点为空则直接新增节点，若不为空则分为三种情况处理
-
2.判断新加入的key-value，是不是加在根节点，若是则获取
-
3.若不是，则判断是否为TreeNode类型，若是TreeNode类型则新增TreeNode节点
-
4.若不是，则循环处理（这里也有两种情况，一种是添加的key已经存在，则根据条件覆盖原值，另一种是key不存在，则在链表尾部添加节点）,还有点需要注意的是，链表中添加元素会去判断，若链表的长度大于设定的阈值8，会将链表结构转换成树形结构
3.扩容：判断当前HashMap的size是否大于阈值threshold，如果大于了阈值则进行扩容操作，
3.2.2 具体细节
在上面的整体流程中，可以大概理解HashMap是如何工作的，下面将详细介绍一下操作实现的细节：
1.新增节点：这个方法比较简单就是调用Node类的构造方法，创建一个Node节点对象
2.新增TreeNode：这个详细可参考JAVA学习-红黑树详解
3.链表转树形：具体分为两步，第一将所有的节点变成TreeNode类型的，第二构建红黑树，具体代码可以去查看treeifyBin()方法的代码实现。
4.扩容：如下代码是HashMap中的扩容操作的具体实现，从代码中可以看出扩容操作主要分为以下几步：
- 计算新容量：根据老数组的容量确定扩容后的容量值，一般扩容为老容量的2倍
- 创建新数组：根据新的容量创建数组，需要尽量避免扩容的发生，因为产生新的数组必然是会消耗一定的内存空间。
- 元素放置到新数组：循环遍历老数组，将元素重新放置到新数组中，分为3种情况如下所示
-
根节点:定位在新数组中的位置，通过e.hash & (newCap - 1)进行定位，直接放置到根节点的位置
-
树形节点：树形节点其实方式和链表节点是类似的，但是其中会考虑是否将树转换为链表的情况，稍微复杂点，若想了解的更加清楚可以查看源码中的split方法进行学习。
-
链表节点：对于链表节点代码中使用了两个引用去记录，当e.hash & oldCap的结果为0时使用loTail记录，反而使用hiHead，后面根据定位将整条链表赋值给新的数组，值得注意的是这里面并未倒置链表。
其中有几点存在疑问的：- 第一：定位为什么不是j就是j+oldCap?
首先扩容操作之后新的容量变为旧容量的两倍，则若原容量为n=16(10000),n-1=15(01111),则扩容之后n=32(100000),n-1=31(011111),而在HashMap中定位元素的位置是通过(n-1) & hash的方式，可以比较扩容前与扩容后的n-1,实际上就是高位上多了个1，那么现在假设元素hash值高位上为0，则运算后该元素在扩容前后的位置并不会发生变化，而假设元素hash的高位上是1，则运算后该元素在扩容前的位置为h，则扩容后的位置为h+newCap/2,即为h+oldCap，从而可以看出扩容后定位要么是扩容前的位置，要么是扩容前的位置+老的容量
- 第二：e.hash & oldCap这个是来判断什么?
通过问题1，这个问题就很明显了e.hash & oldCap是用来判断hash值高位上的值是0还是1的，可以看出假如是1则&运算后得到的结果肯定为大于0，反而肯定等于0
-
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//获取老的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//扩容的阈值
int newCap, newThr = 0;
if (oldCap > 0) {
//超过最大的容量值为2^30，则返回
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);
}
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;
if (oldTab != null) {
//循环老数组，将老数组中的元素从新放置到新的数组中
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 { // 链表重新装填到新数组中
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;
}
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;
}
3.2.3 查找元素
如下代码是HashMap中查找元素实际调用的代码
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//定位头节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
其实通过上面代码可以清晰看出它的思想，就是去根据hash遍历查找，首先第一步，肯定是找到在数组中头节点的位置即通过(n-1) & hash值定位到其头节点，这种方式也就是在新增元素时的定位操作，下面就是几种情况去处理：
- 1.判断头节点是不是查找的元素，若是则直接返回了，若不是则继续查找。
- 2.判断是否为TreeNode节点，若是则遍历红黑树查找，详细可参考JAVA学习-红黑树详解
- 3.判断是否为链表节点，若是则遍历链表查找
4.总结
通过本文可以了解以下几点：
1.HashMap的内部实现是数组+(链表/红黑树实现的),即回答了本文提出的第一个问题
2.HashMap内部是如何解决hash冲突以及如何进行扩容操作的。
需要注意的是,HashMap不是线程安全的，因此在涉及线程安全的情况下尽量不要使用HashMap，再就是在使用HashMap时可以尽量减少其扩容的操作，在可估算数据量的情况下可以指定HashMap的初始化容量，当然这是相对的，若数据量太大，还是建议别这样做。还有一点就是本文是基于JDK_1.8.0_131,还有很多细节的实现并未做详细的说明，如果想要了解的更多，可以阅读源码进行学习，若发现有存在问题的地方，望指正。
本文主要参考链接如下
Java8系列之重新认识HashMap
网友评论