HashMap详解

HashMap：

（看之前建议先去了解一下hash表的结构，hashmap是通过链地址法来解决hash冲突的）
什么是Hashmap？
Hashmap是用来干嘛的？
Hashmap的结构是怎么样的？
我们就基于这几个方面来讲一下。

一、什么是hashmap？

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。
HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

1.为什么要用hashmap？

Hashmap是用来存放键值对的。同时因为它基于hash表的实现，它可以实现快速的增删查改。在理想情况下，可以达到O（1）的查询速度。当然这只是理想状况。

2.搞清楚HashMap

，首先需要知道HashMap是什么，即它的存储结构-字段；其次弄明白它能干什么，即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

数组加链表的好处是什么？ 数组可以快速定位到哪一组链表，而链表的优势就是插入删除。两者结合起来可以有效地避免了链表过长以至于难于查询，也不用数组进行插入删除，这里的数组只是用来查询到哪一组。这就很好地把两者的优势结合起来，把两者的弱点减小了（链表长度大大缩短了，数组不用来增删）。

看完上面这个图我们也应该知道了hashmap的大概结构了吧。首先最重要的就是有个table数组，它里面存放的就是一个个的entry，这每个entry就是一个个链表的head，看上图。当然hashmap还有一些其它属性，下面来看一下：
构造函数：

初始化了一些值。
属性：

还有一个Entry（数组里的元素）

这是用来实际存放键值对的。很显然，这是一个链表型的。

3.装载因子

这里说一下装载因子 loadFactor，它的默认值是0.75. threshold是临界值，当size达到了threshold后，就必须要扩容了。Threshold = 容量*loadFactor。 那为什么不装满再扩容呢？非要弄个loadFactor呢？这就是一个效率的问题了。

当链表的长度超过8以后，对链表的查询就会比较耗费时间了，所以我们既然考虑到hashmap的空间占比，如果loadFactor太少的话，那动不动就扩容，扩容是一个很耗费时间和空间的操作来的，那显然不行。但是如果这个值设置太大的话，那么链表的长度就会很容易超过8，这对链表来说，查询就占用了很多时间了。不过在jdk1.8用了红黑树后，当链表长度超过8的话，就会转换成红黑树，查询就会是O（logn）了，这样在一定程度上可以减少因为loadFactor设置不合理或者hash函数散列分布不均（因为分布不均的话，很容易某一个链表的长度就超过了8，但是由于其它的链表长度比较短，它也不会进行扩容，那如果一直对这个长度超过8的链表进行操作的话，这个hashmap就没用好了，就相当于一个链表了）而带来的链表查询问题。

二、功能实现-方法及解析

先来看一下 hashmap 的put方法

怎么放值？ 回想一下刚才的hashmap结构。是不是要先找到数组下标的位置，然后再遍历链表判断是否有相同的再进行放值？ 那要怎么找下标？去哪个下标里找是否有重复的值？
这就是我们hashcode的作用了。
1.确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):

**这里的Hash算法本质上就是三步：**取key的hashCode值、高位运算、取模运算
可以看出来这个就是基于对象的hashcode再进行一些改进的。这就是为什么之前要严格要求hashcode了。Int有32位，h>>>16然后再异或key.hashCode(),这被称为扰动函数。这样可以让高16位也参与到hashcode的取值过程中，让输入值分布得更加均匀。（因为假如用取模法，length的值是16的话，那就是只有低四位，容易相同）

我们hash算法的目的就是尽量分布均匀。
第三步取模运算，大家可能看得不是很明白，不是要取模嘛？ 为什么是求与？在length是2^n的情况下，这个求与其实就是求模。那为什么要转换成求与呢？这是一个效率的问题
（因为位运算&的运算计算机可以直接得出结果，但是你要求模%的话，就要不断除以一个数，然后取余数）。
那为什么可以用位运算来实现模运算呢？ 原理如下

假设n为3. 2^3就是8， 表示为2进制就是1000。2^3-1=7，表示为2进制就0111。
X&（0111）得出来的就是取X的后三位（二进制的）。 而X%8呢就是先用X/8，相当于二进制的X>>>3右移3位，这时候得出来的结果是X/8的商，我们要的是%，而被移掉的那三位就是我们要求的余数。移掉的三位就是X的最后三位（二进制的），就对应了X&（0111）取得的后三位了。
举例：

记住这个前提是length为2^{n。这就是为什么hashmap的初始值是2}n了。那为什么取了16作为初始值呢，可能是根据大量经验，16是一个空间和时间比较合适的选择吧。

那么我可不可以自己去设置初始值呢？我不要2^n作为初始值呢？表面可以。但是它内部还是会被你这个初始值改为比你设定的初始值大的第一个2的幂。怎么理解？就是(1->1、3->4、7->8、9->16)。
看一下JDK是如何找到比传入的指定值大的第一个2的幂的：
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;
上面的算法目的挺简单，就是：根据用户传入的容量值（代码中的cap），通过计算，得到第一个比他大的2的幂并返回。

请关注上面的几个例子中，蓝色字体部分的变化情况，或许你会发现些规律。5->8、9->16、19->32、37->64都是主要经过了两个阶段。
Step 1，5->7Step 2，7->8Step 1，9->15Step 2，15->16Step 1，19->31Step 2，31->32
对应到以上代码中，Step1：
n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;
对应到以上代码中，Step2：
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Step 2 比较简单，就是做一下极限值的判断，然后把Step 1得到的数值+1。Step 1 怎么理解呢？其实是对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。随便拿一个二进制数，套一遍上面的公式就发现其目的了：
1100 1100 1100 >>>1 = 0110 0110 0110

1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110

1110 1110 1110 >>>2 = 0011 1011 1011

1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111

1111 1111 1111 >>>4 = 1111 1111 1111

1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
通过几次无符号右移和按位或运算，我们把1100 1100 1100转换成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，这就是大于1100 1100 1100的第一个2的幂。好了，我们现在解释清楚了Step 1和Step 2的代码。就是可以把一个数转化成第一个比他自身大的2的幂。但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果数字4套用公式的话。得到的会是 8，不过其实这个问题也被解决了，具体验证办法及JDK的解决方案见全网把Map中的hash()分析的最透彻的文章，别无二家。这里就不再展开了。总之，HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂
这个自己多写几次就明白了，先是移动一位，然后2位，4位，8位，16位，把1都覆盖过去填满了。
那put的过程是怎么样的呢？

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
Put的源码

三、扩容

上面说过，当插入的数据大于临界值就要开始扩容了（为什么要扩容，上面说了，为了链表的查询速度）。由于数组的大小是一开始就定了的，所以我们没有办法动态扩容。所以我们想要扩容的话就要建一个新的数组，然后把旧数组的值移过去。
Jdk1.8加入了红黑树，较复杂，为了理解我们还是看jdk1.7的源码，原理差不多，多了如果链表长度大于8就转为红黑树而已。

上面就是先把旧的table传进，然后判断数组大小已经到了最大了，没有的话就进行扩容（用新的数组换旧的）。修改阙值。

扩容的主体函数。放到新的数组，重要的是怎么放？显然扩容后每个对象的对应的数组下标位置就不同了。求模的数不同了嘛，所以要遍历旧的每个数据。 然后就是e.next = newTable[i]；newTable[i] = e;这两条语句就是说当一个对象放进属于它数组下标时如果下标这时候已经有值了，就把这个对象指向下标的值（简单地说就是指向链表的头），然后就放把这个最新插入的对象变成了每个数组下标的所对应的链表的头了。每一个都是这样，显然这个插入是最后插入的在最前面了。
下面举个例子说明下扩容过程。假设了我们的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的过程。

四、线程不安全

下面先举个hashmap会导致线程不安全的例子。

其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。

好好理解一下这个例子。这个一方面是因为链表的倒序插入，然后导致了e.next指回去了原来的值。不过这只是其中一个例子而已。其实最主要的原因，我认为是这个table不同步的问题，这会导致很多问题，绝不止一个Infinite Loop。我这个一边在读数，然后你那边一边在修改，但是我想要的是原来的数，或者我也想修改，但先被你改了。。等等。就会导致很多问题。
之前看到一个比较有趣的比喻是把这个table比作保险箱，我存了100万美元进去，但是这个保险箱别人也能操作，我存了100万后离开了，打算过几天来拿，然后过几天来拿的时候，发现我的100万美元变成了100万越南币。这谁顶得住？我的保险箱别人也能操作，你总不能祈祷所有看到这个都不会动你的钱的吧？ 这就是线程不安全的原因了。

JDK1.8扩容的改变：1.8对扩容做了一些优化，一个是扩容的位置计算，因为用了2^n作为长度，所以这个位置的计算也简单了。第二个是扩容后的链表不会倒置了。这样就不会导致无限循环了，但是多线程还是别用hashmap，无限循环只是它其中一个问题而已。
下面看下新的扩容位置是怎么想的，算的。
经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

这个怎么说呢？ 大家可以先写一下这个2进制。我们之前说过扩容的位置计算是hash&（length-1）.那我们的length*2以后呢？在2进制中对应的就是前面多了一个1.比如length为16，length-1 = 15，2进制是1111，之前是hash&1111,得出来的是后四位。现在length变成了32，32-1=31，2进制为11111，那就取hash的后五位了。之前的位置取的是后四位，现在是后5位。是不是就多了一位？ 那我们只需要判断这一位是1还是0就可以了。如果是1的话就要在之前的位置加上没扩容之前的length，如果是0的话就不用变（看上图）。

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下:

参考博客：https://www.cnblogs.com/shianliang/p/9233199.html

这里为什么是顺序的呢？就是用了lotail和hitail用来记录链表尾部，然后就插入到尾部之后。这里有意思的是
他用hash对oldCap求与，oldCap是多少，就是上面说都length，不是length-1。比如刚才说得length为16，2进制就是10000，发现了没？ 他就是用了1位，就是我们需要判断为1还是为0的位置来求与，这样得出来的结果只需要判断是否为0就可以了。

看这图理解，不过不是n-1，是n了。
好像1.8还有一些其它的优化吧，剩下自己再看吧。

小结：
1.记住hashmap的结构（数组+链表+红黑树（链表长度大于8））
2.记住装载因子的作用，为什么用0.75.（测试值与其它的一些考虑）
3.Put功能的实现流程，indexfor的计算，用&代替%，只有length为2^n的时候才能用。
4.线程不安全的原因
5.关于1.8的扩容的一些改变和优化
参考博客：https://blog.****.net/qq_40574571/article/details/97612100