深入理解java HashMap
前言：
? 在java 中我们经常会使用到map放法，其中最常用的莫过于hashmap,hashmap 的重要性不言而喻无论实战还是面试还是提高都必须牢牢掌握的。下面我们以java1.8为例.想真正的去了解hashmap单单看几篇一知半解的文章远远还不够，要结合者文章去翻一下源码，仔细看看一下map put方法的过程。慢慢去了解其中的种种奥妙，你会感叹java jdk作者的能力的。感受一下jdk 源码的巧妙
所属位置
? 首先我们先看一下map 的所属位置，继承在map接口下
什么是hash:
? 百度百科：Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
? 简单讲就是通过一系列算法得到一个hash值的算法，其中得到的这个hash值就叫做hashCode，也就是表示在hash 表中的位置的值
为什么使用haseCode 呢：
? 快 就一个字，hashcode 值就可以看做值的数组下标，通过内存地址直接查找，没有过多的判断。通过内存空间换取时间的一种操作。
存储结构
? 1.8中hashmap 是数组和链表 外加红黑树构成的，当链表的长度大于8的时候，链表会转变成红黑树。这种数据结构的原因主要就是为了解决hash冲突，当不同的key hash 值想同的时候，数组对应的值就会链式存储
链表：
红黑树：
PUT方法
? hashmap中最重要的就是put 的过程，精髓也是put 的过程，这部分的源码自己手写一遍都不为过，先看一下hashmap 的put 方法大致流程图
在put 方法里有两个我们需要关注的，敲重点重点！！！！！！：
一.resize扩容： hashMap 中的数组，即存储数据的散列表，下文我们一table 来称呼
- 首次扩容：当table 为null，执行首次扩容即默认首次长度为16
- 再次扩容：当元素数量超过阈值（容量*负载因子（默认0.75）））时便会触发扩容。每次扩容的容量都是之前容量的2倍
- 扩容先后：首次扩容先resize 后插入数据，非首次先插入数据后resize
- 容量上限：必须小于1<<30，即1073741824
- 数据迁移：我们都知道数组是没办法更改长度的，扩容后将会形成一个新的数组，并且要讲旧数组中数据迁移到新的数组中。jdk 1.8中由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图，因此不需要重新计算hash 值，这也是在1.8中优化的点，1.7中需要重新计算hash值然后存入位置。
- 下面我们来看一下具体的源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//首次初始化后table为Null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//默认构造器的情况下为0
int newCap, newThr = 0;
//1.非首次扩容
if (oldCap > 0) {
//2.当前table容量大于最大值得时候返回当前table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//3.table的容量乘以2，threshold的值也乘以2
newThr = oldThr << 1;
}
......
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
.......
//扩容后数据迁移
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 当前index没有发生hash冲突，直接对2取模，即移位运算hash &（2^n -1）
// 扩容都是按照2的幂次方扩容，因此newCap = 2^n
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
//红黑树 略过
else { // preserve order
// 把当前index对应的链表分成两个链表，减少扩容的迁移量
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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) {
// help gc
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// help gc
hiTail.next = null;
// 扩容长度为当前index位置+旧的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
二.hash冲突：
当产生相同的hash 值并且key 不同的时候，即产生了hash冲突，随机会将不同的key 但是相同的hash 值的数据以链表的形式存储在具体的数组中，其位置就是经过hash 计算产生的hash code ,随后在java 1.8中优化查询的速度，当相同位置的链表的数量长度超过8时会将链表转换成红黑树，就变成了了数组对应红黑树。具体的转换过程过于复杂感兴趣的可以去研究一下他的方法。下面代码就是当put 过程中产生了相同的hash值时的处理。
// 当产生了相同的hash 值时
Node<K,V> e; K k;
//1.确认当前table中存放键值对的Key是否跟要传入的键值对key一致，如果一致则直接替换值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.如果key值不相同即产生了hash 冲突，如果已经是红黑树状结构则进行树的插入操作，过于复杂不写了
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.如果冲突后还是链表状态，则进行链表的插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//4.在插入的过程中如果链表的长度>=7时就将链表转换成红黑树，注意长度下一个就是8 了 所以这里是 8 -1
if (binCount >= 8 - 1)
//转换成树状结构
treeifyBin(tab, hash);
break;
}
//如果节点已经存在就替换old value(保证key的唯?性)
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; //替换新的value并返回旧的value
afterNodeAccess(e);
return oldValue;
}
get方法：
? get 方法就比较简单了就是通过key 的hash code值去数组中获取数据，当不是链表的时候直接返回数组中的Node 中的value 值即可。当链表或者红黑树已经形成了以后则进行遍历查询,没有什么特别需要注意的点，只要明白了put 方法，get 方法自然就明白了
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果当前table没有数据的话返回Null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//根据当前传入的hash值以及参数key获取一个节点即为first,如果匹配的话返回对应的value值
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果参数与first的值不匹配的话
if ((e = first.next) != null) {
//判断是否是红黑树，如果是红黑树的话先判断first是否还有父节点，然后从根节点循环查询是否有对应的值
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;
线程不安全
? 我们常常被问到hashmap 线程安全吗？ 答案是不安全呢，具体为什么呢，其实有以下原因,也就是我们上边讲的在put 时候两个需要重点关注的问题。
- 当两个线程同时put 并且正好产生了hash 冲突的情况下，这样就会将值给覆盖掉，这样就会丢失数据
- 在扩容过程中当发生并发的时候，在复制以及数据迁移的过程中只会有一个oldTable 会被赋值给新的数组，因此会丢失数据。
参考：
https://zhuanlan.zhihu.com/p/21673805
https://www.lagou.com/lgeduarticle/18098.html