总结

• HashMap是基于哈希表的Map接口的非同步实现，

• 允许使用null值和null键(HashMap最多只允许一条记录的键为null，允许多条记录的值为null。)。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

• HashMap中不允许出现重复的键（Key）

• Hashmap是非线程安全的，

• 其迭代器是fail-fast的

• HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体，（JDK1.8增加了红黑树部分,会将时间复杂度从O(n)降为O(logn)）。

• 数据存储：先根据key的hashCode（使用key的hashCode()方法获取）重新计算hash值，根据hash值算出这个元素在数组中的位置（即下标）， 如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

• 数据读取：首先根据key的hashCode，找到其数组中对应位置的数据(可能只有一个数据，也可能是多个数据，其表现形式是一个链表)，然后通过key的equals方法在对应位置的链表中找到需要的元素。

• hashMap的默认初始容量是16个，其会有一个负载因子，用于当hashMap中的数据量等于容量*负载因子时，hashMap会进行扩容，扩大的容量是原本的2倍。负载因子的默认初始值为0.75

深入探讨HashMap的底层结构、原理、扩容机制

常见面试题

1、为什么HashMap的容量会小于数组长度？

答：HashMap是通过hash值计算出index，从而最快速的访问 。如果容量大于数组很多的话再加上散列算法不是非常优秀的情况下很容易出现链表过长的情况，虽然现在出现了红黑树，但是速度依旧不如直接定位到某个数组位置直接获取元素的速度快，所以最理想的情况是数组的每个位置放入一个元素，这样定位最快，从而访问也最快，集合容量小于数组长度的原因在于尽量去分散元素的分布，相当于是拉长了分布的范围，尽量减少集中到一起的概率，从而提高访问的速度，同时，负载因子只要小于 1 ，就不存在容量等于数组长度的情况 。

2、扩容期间在未迁移到的hash桶插入数据会发生什么？

答：只要插入的位置扩容线程还未迁移到，就可以插入，当迁移到该插入的位置时，就会阻塞等待插入操作完成再继续迁移 。

3、正在迁移的hash桶遇到 get 操作会发生什么？

答：在扩容过程期间形成的 hn 和 ln链 是使用的类似于复制引用的方式，也就是说 ln 和 hn 链是复制出来的，而非原来的链表迁移过去的，所以原来 hash 桶上的链表并没有受到影响，因此从迁移开始到迁移结束这段时间都是可以正常访问原数组 hash 桶上面的链表，迁移结束后放置上fwd，往后的访问请求就直接转发到扩容后的数组去了 。

4、如果 lastRun 节点正好在一条全部都为高位或者全部都为低位的链表上，会不会形成死循环？

答：在数组长度为64之前会导致一直扩容，但是到了64或者以上后就会转换为红黑树，因此不会一直死循环 。

5、我们都知道，ConcurrentHashMap并发情况下，各线程中的数据可能不是最新的，那为什么 get 方法不需要加锁？

答：get操作全程不需要加锁是因为Node的成员val是用volatile修饰的 。

6、ConcurrentHashMap扩容完成后为什么要再检查一遍？

答：为了避免遗漏hash桶。扩容是分段进行的，当前线程扩容完，其他线程可能还没有扩容完成，需要再检查一次，而且会帮忙一起扩容。。

7、ConcurrentHashMap 的数组上插入节点的操作是否为原子操作，为什么要使用 CAS 的方式？

CAS保证原子操作，其实是使用了自旋 + CAS实现的乐观锁方式

存储结构-字段

从结构实现来讲，HashMap是:数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。

image.png

这里需要讲明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？

数据底层具体存储的是什么

(1) 从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。

static class Node implements Map.Entry {
 final int hash; //用来定位数组索引位置
 final K key;
 V value;
 Node next; //链表的下一个node
 Node(int hash, K key, V value, Node next) { ... }
 public final K getKey(){ ... }
 public final V getValue() { ... }
 public final String toString() { ... }
 public final int hashCode() { ... }
 public final V setValue(V newValue) { ... }
 public final boolean equals(Object o) { ... }
}

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

这样的存储方式有什么优点呢？

(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：
map.put("优知","IT进阶站");

系统将调用”优知”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：

 int threshold; // 所能容纳的key-value对极限 
 final float loadFactor; // 负载因子
 int modCount; 
 int size;

首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。

这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论，想了解更多红黑树数据结构的工作原理。

功能实现-方法

HashMap的内部功能实现很多，本文主要从：

1).根据key获取哈希桶数组索引位置

2).put方法的详细执行

3).扩容过程三个具有代表性的点深入展开讲解。

确定哈希桶数组索引位置

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

方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
 int h;
 // h = key.hashCode() 为第一步 取hashCode值
 // h ^ (h >>> 16) 为第二步 高位参与运算
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
 return h & (length-1); //第三步 取模运算
}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明下，n为table的长度。

image.png

数据存储

当我们往HashMap中put元素的时候，先根据key的hashCode（使用key的hashCode()方法获取）重新计算hash值(具体的算法这里就不讲解了，hash的算法中包含了很多优化的点，是存储的数据能够数组的每一位尽量只有一个值，而不是一个链表，这样能够提高查询效率)，根据hash值算出这个元素在数组中的位置（即下标）， 如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。

image.png

①.判断键值对数组==null是否为空或数组的长度==0（判断是否初始化），否则执行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，如果超过，进行扩容。

数据读取

hashMap的数据读取相对简单，首先根据key的hashCode，找到其数组中对应位置的数据(可能只有一个数据，也可能是多个数据，其表现形式是一个链表)，然后通过key的equals方法在对应位置的链表中找到需要的元素。

扩容

hashMap的默认初始容量是16个，其会有一个负载因子，用于当hashMap中的数据量等于容量*负载因子时，hashMap会进行扩容，扩大的容量是原本的2倍。负载因子的默认初始值为0.75，这个值是经过折中的取值，其也是合理的，所以如非特殊需求，不建议修改该因子，

因为每次扩容都会对原本的数据进行重新的hash计算其在新数组中的位置，所以扩容是非常消耗性能的，所以为了尽量少的避免多次扩容，我们如果知道数据的大概量，我们可以在创建时进行指定初始容量大小。

我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大。

 void resize(int newCapacity) { //传入新的容量
   Entry[] oldTable = table; //引用扩容前的Entry数组
  int oldCapacity = oldTable.length; 
  if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
  threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
  return;
  }
  
  Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
 transfer(newTable); //！！将数据转移到新的Entry数组里
 table = newTable; //HashMap的table属性引用新的Entry数组
 threshold = (int)(newCapacity * loadFactor);//修改阈值
 }

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

 1 void transfer(Entry[] newTable) {
 2 Entry[] src = table; //src引用了旧的Entry数组
 3 int newCapacity = newTable.length;
 4 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5 Entry e = src[j]; //取得旧Entry数组的每个元素
 6 if (e != null) {
 7 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
 8 do {
 9 Entry next = e.next;
10 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
11 e.next = newTable[i]; //标记[1]
12 newTable[i] = e; //将元素放在数组上
13 e = next; //访问下一个Entry链上的元素
14 } while (e != null);
15 }
16 }
17 }

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。

那么为什么说HashMap是线程不安全的，下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解，仍然使用JDK1.7的环境)：

public class HashMapInfiniteLoop { 
 private static HashMap map = new HashMap(2，0.75f); 
 public static void main(String[] args) { 
 map.put(5， "C"); 
 new Thread("Thread1") { 
 public void run() { 
 map.put(7, "B"); 
 System.out.println(map); 
 }; 
 }.start(); 
 new Thread("Thread2") { 
 public void run() { 
 map.put(3, "A); 
 System.out.println(map); 
 }; 
 }.start(); 
 } 
}

其中，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。结果如下图。

image.png

注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。

线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。

image.png

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。

JDK1.8与JDK1.7的性能对比

HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7，下面我们从两个方面用例子证明这一点。

红黑树

即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论，可以参考这篇博文来详细认识红黑树

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

HashMap实现原理及源码分析