源码分析——HashMap-白红宇

前言

HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而访问的时间复杂度为常数级，但遍历的顺序却是无序的。 HashMap最多只允许一个key为null，允许多个key的value值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以使用ConcurrentHashMap。以下是它的类关系图：

1. 存储结构

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

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

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

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后，得到数组下标，把数据放在对应下标元素的链表上（具体内容下文会说到）。

在理解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是对空间和时间效率的一个平衡选择。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。

modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

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

1.1. 拉链法的工作原理

HashMap<String, String> map = new HashMap<>(); map.put("K1", "V1"); map.put("K2", "V2"); map.put("K3", "V3");

新建一个 HashMap，默认大小为 16；

插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。

插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。

插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，插在 <K2,V2> 前面。

应该注意到链表的插入是以头插法方式进行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在链表头部。

查找需要分成两步进行：

计算键值对所在的桶；

在链表上顺序查找，时间复杂度显然和链表的长度成正比。

1.2. 构造函数解析

计算数组容量

HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。

以下是 HashMap 中计算数组容量的代码：

static final int tableSizeFor(int cap) {    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;}复制代码

2. 实现原理

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

根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。

2.1. 确定哈希桶数组索引位置

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过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没有这个方法，原理是一样的只不过放到其他方法中去，例如put()     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，但是&比%具有更高的效率。

取模的原理解析

令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：

x   : 00010000x-1 : 00001111复制代码

令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：

y       : 10110010x-1     : 00001111y&(x-1) : 00000010复制代码

这个性质和 y 对 x 取模效果是一样的：

y   : 10110010x   : 00010000y%x : 00000010复制代码

位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。

确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash%capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。

2.2. 分析HashMap的put方法

HashMap的put方法执行过程可以通过下图来理解，通过该图对比源码可以更清楚地研究学习。

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，如果超过，进行扩容。

JDK1.8HashMap的put方法源码如下:

public V put(K key, V value) {      // 对key的hashCode()做hash      return putVal(hash(key), key, value, false, true);  }    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                 boolean evict) {      Node
     
      [] tab; Node
      
        p; int n, i;      // 步骤1：tab为空则创建     if ((tab = table) == null || (n = tab.length) == 0)         n = (tab = resize()).length;     // 步骤2：计算index，并对null做处理      if ((p = tab[i = (n - 1) & hash]) == null)          tab[i] = newNode(hash, key, value, null);     else {         Node
       
         e; K k;         // 步骤3：节点key存在，直接覆盖value         if (p.hash == hash &&             ((k = p.key) == key || (key != null && key.equals(k))))             e = p;         // 步骤4：判断该链为红黑树         else if (p instanceof TreeNode)             e = ((TreeNode
        
         )p).putTreeVal(this, tab, hash, key, value);         // 步骤5：该链为链表         else {             for (int binCount = 0; ; ++binCount) {                 if ((e = p.next) == null) {                     p.next = newNode(hash, key,value,null);                      //链表长度大于8转换为红黑树进行处理                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                           treeifyBin(tab, hash);                     break;                 }                    // key已经存在直接覆盖value                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k)))) 							break;                 p = e;             }         }                  if (e != null) { // existing mapping for key             V oldValue = e.value;             if (!onlyIfAbsent || oldValue == null)                 e.value = value;             afterNodeAccess(e);             return oldValue;         }     }     ++modCount;     // 步骤6：超过最大容量 就扩容     if (++size > threshold)         resize();     afterNodeInsertion(evict);     return null; }复制代码

HashMap 允许插入key为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。

private V putForNullKey(V value) {    for (Entry
     
       e = table[0]; e != null; e = e.next) {        if (e.key == null) {            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    modCount++;    addEntry(0, null, value, 0);    return null;}复制代码

使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部。

在jdk1.8之前是插入头部的，在jdk1.8中是插入尾部的。

void addEntry(int hash, K key, V value, int bucketIndex) {    if ((size >= threshold) && (null != table[bucketIndex])) {        resize(2 * table.length);        hash = (null != key) ? hash(key) : 0;        bucketIndex = indexFor(hash, table.length);    }    createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {    Entry
     
       e = table[bucketIndex];    // 头插法，链表头部指向新的键值对    table[bucketIndex] = new Entry<>(hash, key, value, e);    size++;}Entry(int h, K k, V v, Entry
      
        n) {    value = v;    next = n;    key = k;    hash = h;}复制代码

2.3. 扩容-基本原理

扩容(resize)就是重新计算table桶容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们一个小教室只能坐一个班，如果想更多的学生进来听课，就得换大教室上课。

和扩容相关的参数主要有：capacity、size、threshold 和 load_factor。

参数	含义
capacity	table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。
size	table 的实际使用量。
threshold	size 的临界值，size 必须小于 threshold，如果大于等于，就必须进行扩容操作。
loadFactor	装载因子，table 能够使用的比例，threshold = capacity * loadFactor。

static final int DEFAULT_INITIAL_CAPACITY = 16;static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;transient Entry[] table;transient int size;int threshold;final float loadFactor;transient int modCount;复制代码

从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍。

void addEntry(int hash, K key, V value, int bucketIndex) {    Entry
     
       e = table[bucketIndex];    table[bucketIndex] = new Entry<>(hash, key, value, e);    if (size++ >= threshold)        resize(2 * table.length);}复制代码

扩容使用 resize() 实现，需要注意的是，扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中，因此这一步是很费时的。

我们分析下resize的源码，这里使用的是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数组里。

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

其实上面的数组扩容、重新计算下标值并将旧数据插入到新数组的过程并不难，有意思的一点是JDK1.8在这里对扩容后的元素移动操作做了优化，具体过程如下。

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

具体细节大家不妨可以去看看JDK1.8的源码中resize是怎么写的，这个思路的确十分巧妙。

3. 为什么HashMap线程不安全？

在多线程使用场景中，应该尽量避免使用线程不安全的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。结果如下图。

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

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

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

于是，当我们用线程一调用map.get(11)时，就会发现问题，进入一个死循环了。

4. 与 HashTable 的比较

hashmap不是线程安全的、hashtable是安全的

HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。

HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。

HashTable 继承自 Dictionary 类，而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。

HashTable 的方法是 Synchronized 的，而 HashMap 不是，在多个线程访问 Hashtable 时，不需要自己为它的方法实现同步，而 HashMap 就必须为之提供外同步，或者改为使用ConcurrentHashMap。

Hashtable 和 HashMap 采用的 hash/rehash 算法都大概一样，所以性能不会有很大的差异。

HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。

HashMap 的迭代器是 fail-fast 迭代器。

5. 总结

扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

负载因子是可以修改的，也可以大于1，但是建议不要轻易修改。

HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

JDK1.8引入红黑树很大程度优化了HashMap的性能。

阅读源码是一件十分耗费精力的事情，但从中你可以领悟到JDK作者的巧妙思路，在源码层面去理解为什么HashMap是线程不安全的，HashMap的扩容机制等等，而不是仅仅停留在会用HashMap这个容器的表面理解上。

参考自：