HashMap详解

God约 3995 字大约 13 分钟

1、HashMap 的底层实现原理

JDK1.8 之前

JDK1.8 之前 HashMap 底层数据结构采用的是 数组+链表 。HashMap 拿到 key 的 hashCode，再经过 扰动函数处理过后得到一个 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖；不相同就通过拉链法（链表头插法） 解决冲突！

所谓扰动函数指的是 HashMap 的 hash 方法。HashMap 的使用自己的hash函数是为了防止一些比较差的 hashCode()计算方法，换句话说使用HashMap扰动函数计算得到的hash值可以有效减少碰撞！

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法源码：

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

JDK1.7 的 HashMap 的 hash 方法源码：

static int hash(int h) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

    h ^= k.hashCode(); // 取hashCode值
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
     return h & (length-1);  // 取模运算
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次！

Hash 算法本质上就三步：取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算得到存储的位置。

所谓 “拉链法” ：将数组和链表相结合。创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值采用头插法加到链表中！

JDK1.8 之后

JDK1.8 中，由 ”数组+链表/红黑树” 组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：

当链表长度超过 8，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树 （以减少搜索时间）
当链表长度超过 8，且数组的长度超过 64 才会转红黑树 （以减少搜索时间）

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构！

2、HashMap 数组的长度为什么是 2 的幂次方？

2 的 N 次幂有助于减少碰撞的几率！ 如果 length 为2的幂次方，则 length-1 转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非常的快，而且空间不浪费。我们来举个例子，看下图：

当 length =15时，6 和 7 的结果一样，这样表示他们在 table 存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，4和5的结果也是一样，这样就会导致查询速度降低。

如果我们进一步分析，还会发现空间浪费非常大，以 length=15 为例，在 1、3、5、7、9、11、13、15 这八处没有存放数据。因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。

3、在解决 hash 冲突的时候，为什么不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋、右旋、变色这些操作来保持平衡，这些操作是非常耗费性能的，而单链表不需要。

当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能！

当元素大于 8 个的时候，红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了！

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能！

4、HashMap默认负载因子为什么是 0.75，不是 0.6 或者 0.8 ？

回答这个问题前，我们来先看下HashMap的默认构造函数：

int threshold;             // 容纳键值对的最大值
final float loadFactor;    // 负载因子
int modCount;
int size;

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

默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改， 除非在时间和空间比较特殊的情况下：

如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值
相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1

我们来追溯下作者在源码中的注释（JDK1.7）：

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity,
 so as to minimize the number of rehash operations.
If the initial capacity is greater than the maximum number of entries divided by the load factor,
no rehash operations will ever occur.

翻译过来大概就是：作为一般规则，较高的值会降低空间开销，但是会提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

5、HashMap 的put方法流程？

简要流程如下：

首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
如果数组是空的，则调用 resize 进行初始化；
如果没有哈希冲突直接放在对应的数组下标里；
如果冲突了，且 key 已经存在，就覆盖掉 value；
如果冲突后，且 key 不存在，发现冲突解决方案是红黑树，就将这个节点挂在树上；
如果冲突后，且 key 不存在，发现冲突解决方案是链表：
- 如果链表长度大于 8 ，并且数组容量小于 64，就进行数组扩容，最后节点插入链表
- 如果链表长度大于 8，并且数组容量大于 64，则将链表转换成红黑树，最后节点挂到红黑树上
hashmap之put方法(JDK1.8)

6、HashMap 的扩容方式？

HashMap 的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 时，就需要将当前 16 的容量进行扩容。然而，Java 里的数组是无法自动扩容的，而 HashMap 的做法是生成一个新的数组，其大小为原数组的两倍，并将原数组中的数据拷贝到新数组中！

那扩容的具体步骤是什么？

来看下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<K,V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }
    }

newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部（如果发生了 hash 冲突的话）。

7、HashMap 为什么线程不安全？

我们都知道 HashMap 是线程不安全的，那 HashMap 为什么线程不安全？JDK1.8 还有这些问题吗？如何解决这些问题呢？总结起来就以下3点：

多线程下扩容死循环： JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。 JDK 1.8 中解决了该问题！
多线程的put可能导致元素的丢失： 多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在！
put和get并发时，可能导致get为null： 线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在！

下面详细分析如上3点！

多线程下扩容死循环

JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

下面看看多线程情况下， JDK1.7 扩容死循环问题的分析。

新建一个更大尺寸的hash表，然后把数据从老的hash表中迁移到新的hash表中。重点看下transfer方法：

假设HashMap初始化大小为2，hash算法就是用key mod 表的长度，在mod 2以后都冲突在table[1]这里了。负载因子是 1.5 (默认为 0.75 )，由公式threshold=负载因子 * hash表长度可得，threshold=1.5 * 2 =3，size=3，而 size>=threshold 就要扩容，所以 hash表要 resize 成 4。

未resize前的table如下图：

正常的ReHash，得到的结果如下图所示：

我们来看看多线程下的ReHash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组，下面是resize 的过程。

Step1:

假设 线程1 在执行到Entry<K,V> next = e.next;之后，cpu 时间片用完了，被调度挂起，这时线程1的 e 指向节点A，线程1的 next 指向节点B。

线程2继续执行，

Step2:

线程 1 被调度回来执行。

先是执行 newTalbe[i] = e;
然后是e = next，导致了e指向了节点B，
而下一次循环的next = e.next导致了next指向了节点A。

Step3:

线程1 接着工作。把节点B摘下来，放到newTable[i]的第一个，然后把e和next往下移。

Step4: 出现环形链表

e.next = newTable[i] 导致A.next 指向了节点B，此时的B.next 已经指向了节点A，出现环形链表。

如果get一个在此链表中不存在的key时，就会出现死循环了。如 get(11)时，就发生了死循环。

分析见get方法的源码：

for循环中的e = e.next永远不会为空，那么，如果get一个在这个链表中不存在的key时，就会出现死循环了。

多线程的put可能导致元素的丢失

多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

我们来看下JDK 1.8 中 put 方法的部分源码，重点看黄色部分：

我们来演示个例子。

假设线程1和线程2同时执行put，线程1执行put(“1”, “A”)，线程2执行put(“5”, “B”)，hash算法就是用key mod 表的长度，表长度为4，在mod 4 以后都冲突在table[1]这里了。注：下面的例子，只演示了 #1 和#2代码的情况，其他代码也会出现类似情况。

正常情况下，put完成后，table的状态应该是下图中的任意一个。