HashMap.md

HashMap

[toc]

---

HashMap 底层数据结构是怎样的，为什么需要链表 ，链表的数据结构是怎样的

• HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。
• HashMap需要链表来防止hash冲突，1.8后引入红黑树，链表长度>8而且数组长度>=64。采用链表转红黑树。
• 单向链表的链表对象维护了一个 first 引用，该引用指向节点链表中的第一个节点对象，每个节点对象维护一个 next 引用，next引用指向下一个节点对象

HashMap的Entry 有什么属性，entry 节点在插入链表时是怎么插入的；为什么 1.8 尾插？

• 属性：key，value，hash，next
• entry节点1.7前采用头插法，1.8采用尾插
• JDK1.8的链表插入元素改为了尾插法，则是为了避免出现逆序且链表死循环的问题

hashmap 默认初始化长度是多少？负载因子默认值为什么是 0.75？

• HashMap的默认初始长度是16
• 0.75是对时间和空间的权衡，0.5扩容频繁，空间太大；1，空间利用，时间变慢。

引入红黑树的原因

jdk1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。

针对这种情况，jdk1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

哈希表底层采用何种算法计算hash值?还有哪些算法可以计算出hash值?

底层采用的key的hashCode方法的值结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引。还可以采用:平方取中法，取余数，伪随机数法

当两个对象的 hashCode 相等时会怎么样？

答：会产生哈希碰撞。若 key 值内容相同则替换旧的 value，不然连接到链表后面，链表长度超过阈值 8 就转换为红黑树存储。

什么是哈希碰撞，如何解决哈希碰撞？

答：只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8之后使用链表 + 红黑树解决哈希碰撞。

ConcurrentHashMap初始构造函数设置

ConcurrentHashMap（32）：在1.8之前，就是设置数组长度为32；1.8之后设置长度为64

sizeCtl含义解释

注意：以上这些构造方法中，都涉及到一个变量sizeCtl，这个变量是一个非常重要的变量，而且具有非常丰富的含义，它的值不同，对应的含义也不一样，这里我们先对这个变量不同的值的含义做一下说明，后续源码分析过程中，进一步解释

sizeCtl为0，代表数组未初始化， 且数组的初始容量为16

sizeCtl为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值

sizeCtl为-1，表示数组正在进行初始化

sizeCtl小于0，并且不是-1，表示数组正在扩容， -(1+n)，表示此时有n个线程正在共同完成数组的扩容操作

ConcurrentHashMap如何扩容，1.8之后如何优化的

1. 如果是多cpu，那么每个线程划分任务，最小任务量是16个桶位的迁移
2. 两倍扩容创建新数组，记录线程开始迁移的桶位，从后往前迁移
3. 每迁移一个桶，放入一个fwd节点，hash值为moved，表示正在扩容，迁移过程加锁

jdk1.8多线程扩容效率改进

多线程协助扩容的操作会在两个地方被触发：

① 当添加元素时，发现添加的元素对用的桶位为fwd节点，就会先去协助扩容，然后再添加元素

② 当添加完元素后，判断当前元素个数达到了扩容阈值，此时发现sizeCtl的值小于0，并且新数组不为空，这个时候，会去协助扩容

HashMap详解：

JDK1.7中 HashMap

• 基本结构：构造函数创建，数据存放在默认数组table[16]中，每个元素以链表形式存放。默认16容量，如果指定自动找到指定值大的最小2的幂次方数，长度在计算后一定为2的幂次方数（方便后面位运算计算下标和扩容）。

• 

• put：put数据时key通过hash方法获取keyHash值，然后利用index=keyHash&(table.length-1)方式计算出下标并在数组中找到此元素。遍历该链表，寻找到如果有相同key，返回原有key并进行覆盖。如果没有重复key，则采用头插法table[index]=new Enrry(key,value,hash,table[index])插入元素的头，并将其引用地址放到table[index]中。

  

• 扩容：当当前hashmap容量size>table.length*0.75时，创键一个新数组，扩容后的容量为table.length*2;两个嵌套遍历，外层遍历元素位置；扩容后元素的位置 newIndex=index或者 newIndex=index+table.length；内层遍历链表，转移链表指向到新元素位置；

  • 可能出现死锁问题，因为采用头插法，多线程执行时，第一个线程执行过程中链表逆序。第二个线程拿着第一个链表逆序的引用会导致死循环。
  • 扩容或链表长度会减短，更方便查询

• 多线程下存在线程一删除后，线程二仍在查找的状况，所以hashMap有一个检验机制，每次操作记录操作次数，查询时验证。如果不同则快速失败

JDK1.7中ConcurrentHashMap

• 基本结构：双层数组，外层Segment[]固定，内层HashEntry可扩容。

• put：put时先通过sindex=keyHash&(segment.length-1)寻找外层数组segment的位置，再通过hindex=keyHash&(HashEntry.length-1)寻找内部数组HashEntry的坐标。使用cas技术（乐观锁）保证只有一个线程put成功。

JDK1.8中ConcurrentHashMap

• 安全put：

1. 如果数组还未初始化，先对数组进行初始化；

2. 如果hash计算得到的桶位置没有元素，利用cas将元素添加对每个桶位加锁；

3. 如果hash计算得到的桶位置元素的hash值为MOVED，证明正在扩容，那么协助扩容

4. 以上都不满足：进行元素添加；此时加synchronized锁机制确保线程安全

   1. 判断是链表结构：遍历，如果有重复keyhash，覆盖。如果没有重复，找到最后一个节点增加新节点pred.next = new Node<K,V>(hash, key,value, null);,采用的是尾插法
   2. 判断是红黑树结构：添加到红黑树

5. 如果链表长度大于8，尝试将链表转红黑树

   1. 判断链表长度大于8，如果数组长度小于64，先扩容。
   2. 如果链表长度大于8，数组长度大于64，链表转红黑树。