1. 整体架构

HashMap 底层的数据结构主要是： 数组 + 链表 + 红黑树 。其中当链表的长度大于等于 8 时且数组长度大于 64 时，链表会转化成红黑树，当红黑树的节点个数小于等于 6 时，红黑树会转化成链表，整体的数据结构如下：

HashMap 解析 - 图1

图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树。

1.1 类注释

从源码的类注释中，我们可以得到以下几个关键的点：

  1. 允许 null 值，不同于 HashTable，HashMap 是线程不安全的；
  2. load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值虽然减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长）。
  3. 如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
  4. HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；
  5. 在迭代过程中，如果 HashMap 的结构被修改，会快速失败。
  6. HashMap 的构造函数中并没有对 HashMap 进行初始化，所以 HashMap 是按照 lazy load 的原则，是在首次使用的时候才会被初始化。

    1.2 重要属性

    ```java // 初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30;

// 负载因子默认值 static final float DEFAULT_LOAD_FACTOR = 0.75f;

// bin(桶)容量大于等于8时，链表转化成红黑树 static final int TREEIFY_THRESHOLD = 8;

// bin(桶)容量小于等于6时，红黑树转化成链表 static final int UNTREEIFY_THRESHOLD = 6;

// 数组容量最小64时才会转会成红黑树 static final int MIN_TREEIFY_CAPACITY = 64;

// 用于fail-fast的，记录HashMap结构发生变化(数量变化或rehash)的数目 transient int modCount;

// HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化) transient int size;

// 扩容的门槛，如果初始化时，给定数组大小的话，会通过 tableSizeFor 方法计算，得到一个接近于 2 的幂次方的数组大小 // 如果是通过 resize 方法进行扩容后，大小 = 数组容量 * 0.75 int threshold;

// 存放数据的数组 transient Node[] table;

// bin node 节点 static class Node implements Map.Entry {//Map.Entry是个接口

//红黑树的节点 static final class TreeNode extends LinkedHashMap.Entry {

  1. <a name="3d76e716"></a>
  2. # 2. HashMap 的数据插入原理？
  3. HashMap 的 putVal() 方法的逻辑大概是这样：
  5. 1. 如果 HashMap 未被初始化过，则初始化；
  6. 1. 对 Key 求 Hash 值，根据 Hash 值计算下标；
  7. 1. 如果没有碰撞，就直接生成新的节点放在数组当前索引位置上；
  8. 1. 如果碰撞了，如果是红黑树就以红黑树的方式新增，如果是链表就链接到尾部；
  9. 1. 如果链表长度大于等于阈值 8，并且整个数组大小大于 64时，就把链表转成红黑树。当数组大小小于 64 时，只会触发扩容，不会转化成红黑树。如果链表长度低于 6，就把红黑树转回链表；
  11. 先来看看 HashMap 最复杂的新增相关的源码：
  12. ```java
  13. public V put(K key, V value) {
  14.     return putVal(hash(key), key, value, false, true);
  15. }
  17. // 入参 hash：通过 hash 算法计算出来的值。
  18. // 入参 onlyIfAbsent：false 表示即使 key 已经存在了，仍然会用新值覆盖原来的值，默认为 false
  19. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  20.                boolean evict) {
  21.     // n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值
  22.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  24.     // 如果数组为空，初始化
  25.     if ((tab = table) == null || (n = tab.length) == 0)
  26.         n = (tab = resize()).length;
  28.     // 这里的 hash 是由 hash() 得到的，后面我们会看 hash() 的实现。
  29.     // 使用 (n - 1) & hash 来计算当前节点的数组下标，n 为数组长度，通常为2的n次方。
  30.     // 如果当前数组下标位置是空的，没有冲突，就直接生成新的节点在当前索引位置上。
  31.     if ((p = tab[i = (n - 1) & hash]) == null)
  32.         tab[i] = newNode(hash, key, value, null);
  34.     // 发生 hash 冲突
  35.     else {
  36.         // e 用于保存当前节点
  37.         Node<K,V> e; K k;
  38.         // 如果当前索引位置节点和要插入节点的 key 和 hash 值都相等，直接把 Node 赋给临时变量
  39.         if (p.hash == hash &&
  40.             ((k = p.key) == key || (key != null && key.equals(k))))
  41.             e = p;
  42.         // 如果是红黑树，使用红黑树的方式新增
  43.         else if (p instanceof TreeNode)
  44.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  45.         // 如果是链表，把新节点放到链表的尾端
  46.         else {
  47.             for (int binCount = 0; ; ++binCount) {
  48.                 // e = p.next 表示从头开始，遍历链表
  49.                 // p.next == null 表明 p 是链表的尾节点
  50.                 if ((e = p.next) == null) {
  51.                     // 把新节点放到链表的.尾部 
  52.                     p.next = newNode(hash, key, value, null);
  53.                      // 当链表的长度大于等于 8 时，链表转红黑树
  54.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  55.                         treeifyBin(tab, hash);
  56.                     break;
  57.                 }
  58.                 // 链表遍历过程中，发现有元素和新增的元素相等，结束循环
  59.                 if (e.hash == hash &&
  60.                     ((k = e.key) == key || (key != null && key.equals(k))))
  61.                     break;
  62.                 //更改循环的当前元素
  63.                 p = e;
  64.             }
  65.         }
  66.        // e != null 说明新节点的新增位置已经找到了
  67.         if (e != null) {
  68.             V oldValue = e.value;
  69.             // 当 onlyIfAbsent 为 false 时，才会覆盖值 
  70.             if (!onlyIfAbsent || oldValue == null)
  71.                 e.value = value;
  72.             // 当前节点移动到队尾
  73.             afterNodeAccess(e);
  74.             return oldValue;
  75.         }
  76.     }
  77.     // 记录 HashMap 的数据结构发生了变化
  78.     ++modCount;
  79.     // 如果 HashMap 的实际大小大于扩容的门槛，开始扩容
  80.     if (++size > threshold) // 多个线程走到这，可能重复resize()
  81.         resize();
  82.     // 删除不经常使用的元素
  83.     afterNodeInsertion(evict);
  84.     return null;
  85. }

3. HashMap 怎么设定初始容量大小？

如果在new HashMap()时不传值，默认大小是16，负载因子是0.75，table 数组会在第一次插入元素时初始化。如果自己传入初始大小，那么 table 数组初始化大小为大于传入大小的 2 的整数次方。例如如果传 10，table 数组大小为 16。

4. HashMap 的哈希函数是怎么设计的？

static final int hash(Object key) {
    int h;
    // 这行代码的意思就是把高低 16 位做异或，
    // 让 hashCode 高位的值也参与了哈希运算，减少了碰撞的概率。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这个问题得从源头说起。在求元素插入时对应的数组下标时，是使用(n - 1) & hash计算的，这主要是为了使用位运算来替代取余运算而诞生的一个公式，因为计算机进行位运算的速度更快。当数组 table 的长度总是 2 的 n 次方时，可以满足(n - 1) & hash = n % hash这个公式。这时候n - 1正好相当于一个低位掩码，与操作后的结果是把哈希值的高位全部归零，只保留低位值。

但这时候问题来了，就算散列值分布再松散，只取最后几位的话，碰撞也会很严重。这时扰动函数的价值就体现出来了，哈希值将自己的高半区和低半区做异或，混合了原始哈希码的高位和低位，以此来加大低位的随机性。而且这样混合后的低位参杂了高位的部分特征，这样高位的信息也被变相保存了下来。

5. 为解决 hash 冲突，大概有哪些办法？

  1. 好的 hash 算法，细问的话复述一下上题的 hash 算法;
  2. 自动扩容，当数组大小快满的时候，采取自动扩容，可以减少 hash 冲突;
  3. hash 冲突发生时，采用链表来解决;
  4. hash 冲突严重时，链表会自动转化成红黑树，提高遍历速度。

    6. JDK1.8 中的一些优化

    数组 + 链表 的结构改成了 数组 + 链表或红黑树。

  • 原因：防止链表过长，将链表的时间复杂度从O(n)降低至O(logn)。

    链表的插入方式从头插法改成了尾插法。

  • 原因：因为 JDK 1.7 采用头插法进行扩容时，头插法会让链表发生反转，多线程环境下会产生环。

  • 解释：在 JDK 1.7 中，当两个线程同时插入节点时，一个线程采用头插法插入成功，而另一个线程因为容量不够插入失败，于是对数组进行扩容。重新 hash 后继续采用头插法放置元素，将后遍历到的节点放入了头部，这样就形成了环。
    HashMap 解析 - 图2

    扩容的时候 JDK 1.7 需要对原数组中的元素重新 hash 定位在新数组的位置，而1.8采用更简单的判断逻辑，位置不变 或 原索引位置+旧容量大小。

  • 原因：这是由于扩容是扩大为原数组大小的 2 倍，用于计算数组位置的掩码仅仅只是高位多了一个 1，
    HashMap 解析 - 图3
    如上图的例子，分两种情况：

  • 若 key 的 hashcode 高位第四位为0，那么数组扩容后 key 在数组中的位置不变。

  • 若 key 的 hashcode 高位第四位为1，那么数组扩容后原始数在数组中的位置为 原索引位置+旧容量大小。

    在插入时，JDK 1.7先判断是否需要扩容再插入，JDK 1.8先插入再判断是否需要扩容。

    JDK 1.7 的 hash() 方法扰动了四次，而JDK 1.8只扰动了一次。

  • 原因：1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

    7. 为什么数组和红黑树相互转换的阈值是 8 和 6？

    如果链表中的节点个数太多了，遍历是比较耗时的，需要 O(n) 的时间复杂度。若转化成红黑树，可以使遍历的时间复杂度降低至 O(logn)，但红黑树比较占空间而且转换也需要一定的时间。所以 8 这个数其实是一个平衡点。我们通过泊松分布公式计算，在 hash 函数设计合理的情况下，发生 hash 碰撞 8 次的概率为百万分之6。所以说正常情况下，链表都不会转化成红黑树，这样设计的目的，是为了防止非正常情况下，比如 hash 算法出了问题时，导致链表的节点个数大于等于 8 时，仍然能够快速遍历。

当节点的个数小于等于 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数小于等于 6 时，遍历链表也很快，所以红黑树会重新变成链表。选择 6 可以避免 hash 碰撞次数在 8 附近徘徊时，一直发生链表和红黑树的转化。

8. HashMap 为什么不是线程安全的，怎么解决？

在多线程环境下，JDK 1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。

看上面的putVal()方法的源码，可以发现当A线程执行到代码第6行判断index位置为空后正好挂起，B线程开始执行第7行，往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把B线程的数据给覆盖了。

Java中有 Hashtable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

  1. Hashtable 是直接在操作方法上加 synchronized 关键字，锁住整个数组，粒度比较大；
  2. Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
  3. ConcurrentHashMap 使用分段锁，降低了锁粒度，让并发度大大提高。

    9. 遍历 HashMap 的三种方式

    ```java import java.util.HashMap; import java.util.Map;

public class IterateHashMap { public static void main(String[] args) { Map map = new HashMap<>(); map.put(1, “C”); map.put(2, “C++”); map.put(3, “Java”); map.put(4, “Spring”); map.put(5, “Mybatis”);

    // 1.遍历entrySet
    for (Map.Entry<Integer, String> entry : map.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
    System.out.println("-------------");

    // 2.遍历keySet
    for (Integer key : map.keySet()) {
        System.out.println(key + ":" + map.get(key));
    }
    System.out.println("-------------");

    // 3.使用Lambda表达式遍历
    map.forEach((key, value) -> {
        System.out.println(key + ":" + value);
    });
}

} ```