描述

what

• HashMap是JDK提供的双列集合类，它继承于Map接口。
• HashMap的数据结构是哈希表，作为一种数据结构，哈希表由“桶+链表”组成，而HashMap使用的哈希表，在JDK1.8之前由数组+单向链表，JDK1.8之后的数据结构由【数组+单向链表/红黑树】组成。（链表长度超过8就变成红黑树）

HashMap集合的特点：

• 存取无序
• 可以存null值
• 多线程下不安全

哈希表

HashMap的数据结构如下，以3号为例。3下面的所有内容就是“哈希桶”，也可以看作是一个链表。3这个数为“哈希值”。3号哈希值下有2个key，name3和name12。这就是哈希碰撞。

由于哈希碰撞的情况较少，因此平均的时间复杂度是O(1)

HashMap-JDK1.7

初始容量

• HashMap默认的初始容量为2的四次方即16，HashMap的最大容量为2的30次方

• HashMap的初始容量可以自定义，但必须得是2的幂次方，如果不是2的幂次方，它会自动向上调整。比如你设置的初始容量为17它会调整为32。因为17大于2的四次方，因此要调整为2的五次方。
• 原因：2的幂次方-1换算成2进制的哈希值都包含全1，全1和要存的元素哈希值按位“与”运算能求出数组下标，并且可均匀分布。
  
  new一个hashmap会分配一个空的初始容量的哈希表，当对这个hashmap添加元素时，才会把自定义的初始容量和负载因子赋给hashmap。

put操作

• new一个空的哈希表，哈希表由数组+链表组成。当put时，首先要把指定的初始容量和负载因子给hashmap集合，假设初始容量为16，即数组的长度为16.

• 由源码可知，走完两个判断之后，第一步先执行了一个hash方法。
  

• hash方法的目的是处理比较糙的哈希值，减少哈希碰撞，使所有元素分布在hash表上的位置更加均匀。

• hash方法之后又走了一个indexFor方法，也就是put操作。put的思想是把不同的数均匀的存储在这16个空间中。具体算法为：拿出“初始容量”-1，再求出要放到hashmap的元素的“哈希值”，用“初始容量-1的二进制位”和“元素的哈希值”进行与操作，求出的数在0-15之间，假如求出的值是4就放到数组下标为4的空间中。

• 如果现在又来了一个数，求出的值还是4，同样把这个数放在4里面。
  

为什么用【与】操作，而不用【取模】？
取模的缺点：

• 效率低
• 负数取模后还是负数，需要做2次处理

indexFor方法执行完，走了一个循环并判断，求出的key是否已经存在于hashmap中，如果存在就覆盖value值，如果不存在就执行addEntry方法，添加到链表中

扩容

• addEntry方法第一步便是判断当前map集合是否超过了最大容量，最大容量=初始容量x负载因子(默认为0.75)。超过的话就需要先执行resize方法进行扩容，扩容的大小为原大小的2倍。
• 那什么是最大容量呢？最大容量指的是“数组+链表中所有元素的数量。”
  
  扩容后使用下面的transfer方法重新计算哈希值，再把所有元素放到这个新的哈希表中~
  
  Resize的性能非常低，因此建议new hashmap就分配合适的初始容量，减少扩容的频率~

负载因子

• 负载因子：0.75
• 负载因子相当于一个阀值，如果这个阀值取1就意味着容量都用光了再扩容，这种情况会造成大量的哈希冲突，哈希冲突越多越会降低查找效率。阀值如果取0.5的话，哈希冲突少了，但扩容更频繁了，扩容越频繁，调用transfer方法次数越多，也会降低查找效率。因此0.75是折中办法。
  

死锁问题

• hashmap是不安全的，多线程下可能会发生死锁。多线程扩容时，如果遇到老的哈希值要赋到新的哈希值上。而恰巧一个线程老的哈希值是另一个线程的新哈希值，另一个线程的新哈希值是上一个线程的老哈希值。这样就会形成一个“环”，即出现死锁
• e.next = newTable[i] 导致key(3).next指向了key(7)
• 此时，key(7).next已经指向了key(3)。环形链表就出现了。
  

哈希碰撞-DOS问题

• 哈希碰撞会影响查询性能，这时候如果有“法外狂徒”基于某种类型的hash规则，构造了成千上万个哈希值一样的数据，此时查找的效率就会被大大减慢。如图下图中3个数的哈希值都是2112。
• Dos指拒绝服务，当哈希值增多到服务器短时间内处理不过来时，服务器会因此处于忙碌状态并且不断的被消耗网络资源和系统资源，这就是DOS。
  

HashMap-JDK1.8

链表变成红黑树的原理

• 完全平衡二叉树的查找效率高，链表的增删改效率高，红黑树效率介于二者中间。原因在于HashMap不仅有查找操作，还有增删改操作。
• 并不是链表中的元素个数大于8就转换为红黑树，还会判断一下当前数组的长度，数组长度小于64时，会进行扩容，只有当链表中元素个数>8且数组长度>=64时才会将链表转换为红黑树

阈值

• 阈值为：8
• 使用默认hash计算hashcode符合参数为0.5的泊松分布，可以发现这种方式计算的哈希值超过8的概率已经非常非常小了，所以选择了8作为阈值。
  

put & get方法

put方法：

• JDK1.8的put方法比1.7多了一倍，原因在于它创建了一个TreeBean的方法，把链表构造成树的方法，如果阈值为8，他就会把链表转换成树
  

get方法：

• 判断这个元素存在哪里。如果存在数组中，就从数组中拿出来。如果在树中就在树中拿出来，如果在链表就在链表中拿出来。
  

HashMap-1.7 AS 1.8

• 数据结构
  • JDK1.7：【数组+单向链表】，JDK1.8：【数组+单向链表/红黑树】
• 链表插入方式
  • JDK1.7采用头插法，JDK1.8采用尾插法。
  • 头插法无需遍历链表速度快但多线程扩容时会出现死锁问题。JDK1.8采用尾插法，因为一定会计算链表当前的节点数，也就是一定会去遍历链表，所以采用尾插。
• 算法
  • JDK7的Hash算法比JDK8更复杂。
  • hash越复杂，生成的hashcode越散列，越不容易出现哈希冲突。即JDK7只能通过优化hash算法来提高查询性能。而JDK8使用了红黑树，提高了哈希冲突下的查询性能，因此Hash算法更简单，毕竟哈希算法的复杂度是以消耗CPU为代价的。
• 扩容方式
  • JDK7和JDK8扩容方式不一致
  • JDK8扩容时会先算出当前位置上哪些元素在新数组的低位，哪些元素在新数组的高位，然后一次性转移。而JDK7则一次转移一个元素

ConcurrentHashMap

• 之前我们学过HashTable，它在多线程下是安全的。但HashTable采用全局加锁，导致高并发下效率低下。
• 因此JUC中的ConcurrentHashMap就称为高并发下使用HashMap的关键

1.7

在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。

Segment(分段锁)

• ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

内部结构：

• ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。下图是ConcurrentHashMap的内部结构图：
  
  ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

该结构的优劣势：
优点：

• 写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。
• 所以，通过这种结构，ConcurrentHashMap的并发能力可以大大的提高。

劣势：

• 这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长

1.8

• 在JDK1.8中ConcurrentHashMap采用了数组+链表+红黑树的方式实现。看着好像和普通的hashmap没什么区别，实则这种方式内部使用了大量的CAS操作。
  

• CAS是compare and swap的缩写，即比较并交换。cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。

• CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的，如果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。

• JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。

• Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

1.7与1.8比较

可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。

2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。

3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。

4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。

5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。