• HashMap
  • 基础
    • jdk1.7
      • 特性
    • 不安全的原因
      • 造成死循环的分析过程
    • jdk1.8
      • 特性
      • 不安全的原因
    • PUT操作
    • GET操作
    • HashMap的长度为什么是2的幂次方
    • Hash冲突如何解决
    • 1.7与1.8的底层发生的变化
    • HashMap长度为什么是2的幂次方
    • 负载因子0.75
    • 扰动函数
  • HashMap与HashTable
    • 线程是否安全
    • 效率
    • 对于NUll KEY与NULL VALUE
    • 初始容量以及扩充容量的大小

HashMap

基础

key对应value形式

非线程安全，多线程操作时可能会有数据覆盖问题，因1.7的时候put有个resize过程，由于头插法的关系会导致链表环形造成死循环；在1.8的时候改为尾插法

jdk1.7

特性

由数组+链表组成，链表为了解决hash冲突，使用的是头插法

不安全的原因

多线程环境下，扩容的时候可能会造成环形链表导致死循环或数据丢失

造成死循环的分析过程

假设：

1. hash算法为简单的用key mod链表的大小
2. 最开始hash表的size=2，key=3，7，5，都在table[1]中
3. 然后进行resize，使size变为4

未resize前的结构数据如下：

在单线程的环境下，最后结果如下：

在多线程的环境下，加入有2个线程A和B都在进行put操作。线程A在执行到transfer函数中的第11行代码处挂起

此时线程A的运行结果如下：

线程A挂起后，此时线程B正常执行，并完成resize操作，结果如下

这里需要注意的点：由于线程B以及执行完毕，根据java内存模型，现在newTable和table中的Entry都是主存中的最新值：7.next=3，3.next=null

此时切换到线程A，线程A挂起时内存如下：e=3，next=7，newTable[3]=null，代码执行过程如下：

newTable[3]=e->newTable[3]=3
e=next->e=7

此时结果如下：

继续循环：

e=7
next=e.next ----> next=3【从主存中取值】
e.next=newTable[3] ----> e.next=3【从主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3

结果如下

再次进行循环

e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7 即：3.next=7
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null

注意此次循环：e.next=7,而在上次循环中7.next=3，出现环形链表，此时e=null循环结束

jdk1.8

特性

由数组+链表+红黑树组成，使用的是尾插法；当链表长度大于8且hash桶大于64转为红黑树，hash桶的数量默认为16，负载因子为0.75。扩容的时候，会先检测元素个数，当大于16*0.75=12时，触发扩容成之前哈希桶的2倍，会把之前旧的元素重新hash计算，之后按照链表或者红黑树的方式进行重新排列；当红黑树的节点小于6的时候重新转为链表。

所以当链表元素数目到8个，同时HashMap的数组长度要大于64，链表才会转红黑树，否则都是做扩容

不安全的原因

多线程环境下，容易造成数据覆盖。如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null。

线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。

PUT操作

1. 先计算key的hash值找到对应的桶index；
2. 判断map是否为空，如果为空，进行resize扩容；
3. 如果不为空，根据hash找到数组的index，查看是否为空，如果为空直接插入；
4. 如果index不为空，则判断key的对象hash值与已存在的对象hash值判断是否相等，如果相等直接替换；
5. 如果不等，说明hash碰撞，则以链表的方式放在链表后面；
6. 如果链表大于8，则转为红黑树并执行出入，如果长度低于6，转为链表；
7. 插入成功后，再进行一次判断是否需要扩容

GET操作

1. 通过hash找到key对应的桶，根据桶的性质决定是遍历链表还是红黑树
2. 通过index定位到对应的value，如果相等直接命中
3. 不同，根据首元素判断是红黑树还是链表，进行遍历查找

HashMap的长度为什么是2的幂次方

1. 尽管使用了散列方式，但是散列值不能直接拿来使用。用之前要先对数组长度取模，得到的余数才能用来存放，也就是数组的下标。数组的计算方式就是（n-1）&hash，n为数组的长度
2. 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作，即hash%length==hash&(length-1)的前提是length是2的n次方，并且采用二进制位的&比起%能够提高效率

Hash冲突如何解决

1. 链表法（拉链法）：相同的hash值组成链表
2. 开放地址法：当槽位被占用则查找下一个能存放的槽位

1.7与1.8的底层发生的变化

1. jdk1.7底层是数组+链表，jdk1.8是数组+链表+红黑树，目的是为了提高hashmap的插入和查询效率；
2. jdk1.7采用的头插法，jdk1.8改为尾插法，目的是解决1.7的循环链表造成的死循环；

HashMap长度为什么是2的幂次方

为了能让HashMap存取搞笑，尽量减少碰撞，把数据均匀分配。 取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

length-1使得二进制全是1组成，不会导致空间利用率降低，2^n-1二进制全为1

负载因子0.75

• 如果为1导致查询效率变低，碰撞概率变大
• 如果为0.5导致空间利用率降低

扰动函数

扰动函数增加了随机性，让元素更加均匀的散列，减少碰撞

HashMap与HashTable

线程是否安全

HashMap非线程安全，HashTable是线程安全，由于HashTable内部方法经过sychronized修饰

效率

由于线程安全问题，HashMap相对效率高一点，HashTable基本被淘汰

对于NUll KEY与NULL VALUE

HashMap可以存储空的key与vlaue，但是空的key只能有一个，空的value可以多个；HashTable不允许有空的key与value

初始容量以及扩充容量的大小

1. 创建时如果没有制定容量的初始值，HashTable初始大小为11，之后每次扩容容量变为原来的2n+1；HashMap默认初始值为16，每次扩容变为原来的2倍
2. 创建时候如果制定了初始的值，Hashtable会直接使用你给的大小，HashMap会将其扩容为2的幂次。也就是HashMap总是使用2的幂作为哈希表的大小