简略介绍

必须要学习的源码--HashMap

什么是 HashMap？

HashMap 是Java日常开发常用的一个调集类。Map调集即Key-Value的调集，前面加个Hash，即散列，无序的。所以HashMap是一个用于存储Key-Value键值对的无序调集，每一个键值对也叫做Entry。

HashMap 的特性

这儿咱们先做答复，处理几个面试常问的HashMap问题，借此办法来开端了解HashMap的特性。

HashMap的底层是怎么完结的？&& HashMap的扩容机制？

在JDK1.8之前，HashMap选用数组+链表完结，即运用拉链法处理hash抵触。可是当坐落一个桶中的元素较多，即hash值持平的元素较多时，经过key值查找要遍历链表，时刻杂乱度为O(N)，功率较低。因而JDK1.8中，HashMap选用数组+链表+红黑树完结，当链表长度超过阈值（8）时，将链表转换为红黑树（将链表转换成红黑树前会判别，假如当时数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），查找的时刻杂乱度为O(logN)，这样大大削减了查找时刻。

为什么说HashMap是线程不安全的？

HashMap在put的时分，刺进的元素超过了容量（由负载因子决议）的规模就会触发扩容操作，便是rehash，这个会从头将原数组的内容从头hash到新的扩容数组中，在多线程的环境下，存在一起其他的元素也在进行put操作，假如hash值相同，或许呈现一起在同一数组下用链表标明，形成闭环，导致在get时会呈现死循环，所以HashMap是线程不安全的。

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

为了能让 HashMap 存取高效，尽量较少磕碰，也便是要尽量把数据分配均匀。Hash 值的规模值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只需哈希函数映射得比较均匀松懈，一般使用是很难呈现磕碰的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要寄存的方位也便是对应的数组下标。这个数组下标的核算办法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

其他的特性？

  • HashMap 允许 null 键和 null 值
  • HashMap 默许的初始化巨细为 16。之后每次扩大，容量变为原来的 2 倍。

HashMap 源码剖析

这儿咱们首要的阅览材料是JDK1.8的HashMap源码

底层数据结构

在网上找到一张很好的图

必须要学习的源码--HashMap

能够说HashMap便是一个桶数组，当桶内数据超过八个之后，桶内存储结构会由链表变成红黑树。

大体结构咱们了解了，接下来是详细编码了

类的特点：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  // 序列号
  private static final long serialVersionUID = 362498820763181265L;
  // 默许的初始容量是16
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  // 最大容量
  static final int MAXIMUM_CAPACITY = 1 << 30;
  // 默许的填充因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  // 当桶(bucket)上的结点数大于这个值时会转成红黑树
  static final int TREEIFY_THRESHOLD = 8;
  // 当桶(bucket)上的结点数小于这个值时树转链表
  static final int UNTREEIFY_THRESHOLD = 6;
  // 桶中结构转化为红黑树对应的table的最小容量
  static final int MIN_TREEIFY_CAPACITY = 64;
  // 存储元素的数组，总是2的幂次倍
  transient Node<k,v>[] table;
  // 寄存详细元素的集
  transient Set<map.entry<k,v>> entrySet;
  // 寄存元素的个数，留意这个不等于数组的长度。
  transient int size;
  // 每次扩容和更改map结构的计数器
  transient int modCount;
  // 临界值(容量*填充因子) 当实际巨细超过临界值时，会进行扩容
  int threshold;
  // 加载因子
  final float loadFactor;
}

HashMap内部链表节点类的完结：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
​
    Node(int hash, K key, V value, Node<K,V> next) {
      this.hash = hash;
      this.key = key;
      this.value = value;
      this.next = next;
     }
​
    public final K getKey()     { return key; }
    public final V getValue()    { return value; }
    public final String toString() { return key + "=" + value; }
​
    public final int hashCode() {
      return Objects.hashCode(key) ^ Objects.hashCode(value);
     }
​
    public final V setValue(V newValue) {
      V oldValue = value;
      value = newValue;
      return oldValue;
     }
​
    public final boolean equals(Object o) {
      if (o == this)
        return true;
      if (o instanceof Map.Entry) {
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        if (Objects.equals(key, e.getKey()) &&
          Objects.equals(value, e.getValue()))
          return true;
       }
      return false;
     }
   }

HashMap内部红黑树节点类型的完结

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent; // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;  // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
      super(hash, key, val, next);
     }
​
    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
      for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
          return r;
        r = p;
       }
     }
​
    /**
     * Ensures that the given root is the first node of its bin.
     */
    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
     }
​
    /**
     * Finds the node starting at root p with the given hash and key.
     * The kc argument caches comparableClassFor(key) upon first use
     * comparing keys.
     */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
     }
​
    /**
     * Calls find for root node.
     */
    final TreeNode<K,V> getTreeNode(int h, Object k) {
     }
​
    /**
     * Tie-breaking utility for ordering insertions when equal
     * hashCodes and non-comparable. We don't require a total
     * order, just a consistent insertion rule to maintain
     * equivalence across rebalancings. Tie-breaking further than
     * necessary simplifies testing a bit.
     */
    static int tieBreakOrder(Object a, Object b) {
     }
​
    /**
     * Forms tree of the nodes linked from this node.
     */
    final void treeify(Node<K,V>[] tab) {
     }
​
    /**
     * Returns a list of non-TreeNodes replacing those linked from
     * this node.
     */
    final Node<K,V> untreeify(HashMap<K,V> map) {
     }
​
    /**
     * Tree version of putVal.
     */
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                    int h, K k, V v) {
     }
​
    /**
     * Removes the given node, that must be present before this call.
     * This is messier than typical red-black deletion code because we
     * cannot swap the contents of an interior node with a leaf
     * successor that is pinned by "next" pointers that are accessible
     * independently during traversal. So instead we swap the tree
     * linkages. If the current tree appears to have too few nodes,
     * the bin is converted back to a plain bin. (The test triggers
     * somewhere between 2 and 6 nodes, depending on tree structure).
     */
    final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                 boolean movable) {
     }
​
    /**
     * Splits nodes in a tree bin into lower and upper tree bins,
     * or untreeifies if now too small. Called only from resize;
     * see above discussion about split bits and indices.
     *
     * @param map the map
     * @param tab the table for recording bin heads
     * @param index the index of the table being split
     * @param bit the bit of hash to split on
     */
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
     }
​
    /* ------------------------------------------------------------ */
    // Red-black tree methods, all adapted from CLR
​
    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                       TreeNode<K,V> p) {
     }
​
    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                        TreeNode<K,V> p) {
     }
​
    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                          TreeNode<K,V> x) {
     }
​
    static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                          TreeNode<K,V> x) {
     }
​
    /**
     * Recursive invariant check
     */
    static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
     }
   }

初始容量、负载因子、阈值

一般状况下咱们都会运用无参构造 HashMap。但当咱们对时刻和空间杂乱读有要求的时分，咱们需求手动调参，以让 HashMap 满意咱们的要求。可供咱们调整的参数有两个，一个是初始容量 initialCapacity，另一个负载因子 loadFactor。设定这两个参数会影响到阈值的巨细。初始阈值 threshold 由 initialCapacity 经过移位操作核算得出。他们的效果别离如下：

称号 用处
initialCapacity HashMap 初始容量
loadFactor 负载因子
threshold 阈值（当时 HashMap 所能包容键值对数量的最大值，超过这个值，则需扩容）

相关代码如下：

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
​
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
​
​
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
int threshold;
​
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;

咱们首要从阈值（threshold）开端剖析

经过看代码咱们知道了HashMap初始容量是16，负载因子是0.75，而阈值咱们从注释中知道是由容量乘以负载因子核算得来的。

本着求实的情绪，咱们查看下HashMap的构造函数：

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                      initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                      loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

tableSizeFor办法：

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;
}

看到这个tableSizeFor办法，似乎与上面说的 threshold=capacity * load factor 有收支。

这个算法的效果便是找到大于或等于 cap 的最小2的幂。进程便是将二进制数从左往右数的第一个1开端右边全部变成1，最终再加上1，便是成果了。

比如咱们传入的cap为31，观察n的改变进程：

1 1110(30) -> 1 1111 -> 10 0000(31 + 1) -> 32

现实也是如此：

必须要学习的源码--HashMap

以上便是初始阈值(threshold)的核算进程了。接着咱们看看负载因子(loadFactor)。

先问几个问题：

  • 什么是负载因子？

    依据上面的学习咱们知道阈值（threshold） = 负载因子（loadFactor） * 容量（capacity）

    loadFactor 是负载因子，标明 HashMap 满的程度，默许值为 0.75f，也便是说默许状况下，当 HashMap 中元素个数达到了容量的 3/4 的时分就会进行主动扩容。

  • 为什么要扩容？

    HashMap 在扩容到进程中不仅要对其容量进行扩大，还需求进行 rehash！所以，这个进程其实是很耗时的，而且 Map 中元素越多越耗时。

    rehash 的进程相当于对其间一切的元素从头做一遍 hash，从头核算要分配到那个桶中。

    那么为什么要扩容？HashMap 不是一个数组链表吗？不扩容的话，也是能够无限存储的呀。为啥要扩容？

    原因就在于哈希磕碰！

    哈希磕碰：两个不同的输入值，依据同一哈希函数核算出的哈希值相同的现象叫做磕碰。

    为了处理哈希抵触，HashMap运用了链地址法。

    必须要学习的源码--HashMap

    HashMap是依据链表的数组的数据结构完结的。

    咱们知道抵触以后拉链法会向对应链表后边添加元素，一旦抵触多了数组的链表就会退化成链表，查找功率大大降低。

    所以为了确保HashMap的查找功率，咱们需求扩容，来确保HashMap的抵触不要太高。

所以负载因子实际是反应了 HashMap 桶数组的运用状况：

  • 调低负载因子，HashMap 所能包容的键值对数量变少。扩容时，从头将键值对存储进新的桶数组里，键与键之间发生的磕碰会下降，链表长度变短。此刻，HashMap 的CRUD操作功率会变高，这便是典型的拿空间换时刻。
  • 添加负载因子（负载因子能够大于1），HashMap所能包容的键值对数量变多，空间利用率高，但磕碰率也高。这意味着链表长度变长，功率也随之降低，这种状况是拿时刻换空间。

正常来说默许的0.75就现已是很合理的解了，假如有特殊需求，能够依照上面讲的进行调整。

hash办法（扰动函数）

HashMap 经过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后经过(n - 1) & hash判别当时元素寄存的方位（这儿的n指的是数组的长度），假如当时方位存在元素的话，就判别该元素与要存入的元素的 hash 值以及 key 是否相同，假如相同的话，直接掩盖，不相同就经过拉链法处理抵触。

jdk1.8 的 hash 办法

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

  • 解释

    key.hashCode()是Keyt自带的hashCode()办法，回来一个int的散列值，规模从-2147483648到2147483648。可是这样的散列值是不能直接拿来用的，用之前需求对数组的长度做取模运算。得到的余数才是索引值。

    int index = hash & (arrays.length-1);

    那么这也就理解了为什么HashMap的数组长度是2的整数幂。

    比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。能够看出一个奇数二进制最终一位必然位1，当与一个hash值进行与运算时，最终一位或许是0也或许是1。但偶数与一个hash值进行与运算最终一位必然为0，形成有些方位永久映射不上值。(想尽办法的扰动)

    可是，即使散列函数很松懈，可是最终成果咱们只取后边几位，磕碰依旧是很严重的。这个时分咱们的hash函数的价值体现出来了。

    咱们将hashCode与自己右移16位的成果(刚好32bit的一半)进行异或操作。便是为了混合哈希值的高位和低位，添加低位的随机性，而且混合后的值也变相保持了高位的特征。

比照 jdk1.7 的hash办法

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
​
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

1.7的hash算法扰动了4次，所以相比于1.8的算法是比较慢的。

get办法 (查找)

查找的进口办法在get, 首要逻辑在getNode办法

查找操作，先定位键值对地点的桶方位，然后再对链表或许红黑树进行查找。

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}
​
​
final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  // 1. 定位键值对地点桶的方位
  if ((tab = table) != null && (n = tab.length) > 0 &&
     (first = tab[(n - 1) & hash]) != null) {
    if (first.hash == hash && // always check first node
       ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    if ((e = first.next) != null) {
      // 2. 假如first是TreeNode类型，则运用红黑树查找办法
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      // 2. 不然对链表进行查找
      do {
        if (e.hash == hash &&
           ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
       } while ((e = e.next) != null);
     }
   }
  return null;
}

查找中心在于getNode()办法。里面现已做了注释。

咱们先看到第一步“定位键值对地点桶的方位”，完结代码如下：

first = tab[(n - 1) & hash

这儿经过(n-1)&hash能够算出桶在桶数组中的方位。解释一下，HashMap中桶数组的巨细 length 总是 2 的幂。此刻，(n-1)&hash等价于对length取余。但取余功率没有位运算高，所以(n-1)&hash也是一个小的优化。

假定 hash=143，n=16。核算进程如下：

必须要学习的源码--HashMap

最终成果为15，刚好便是143%16的成果。

put办法 (刺进)

关于刺进操作咱们先剖析大体流程：

首要肯定是先定位要刺进的键值对归于哪个桶，定位到桶后，再判别桶是否为空。假如为空，则将键值对存入即可。假如不为空，则需将键值对接在链表最终一个方位，或许更新键值对。

当然刺进进程还有许多细节。首要HashMap是变长调集，需求考虑扩容问题。其次，在JDK1.8中，HashMap引进了红黑树优化过长链表，所以这儿要考虑优化进程。

刺进操作的进口在put(K,V)，中心在V putVal(int, K, V, boolean, boolean)办法中。

首要咱们看下刺进操作的源码：

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}
​
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
        boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 初始化桶数组 table，table 被延迟到刺进新数据时再进行初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 假如桶中不包括键值对节点引证，则将新键值对节点的引证存入桶中即可
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    // 假如键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
    if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
      
    // 假如桶中的引证类型为 TreeNode，则调用红黑树的刺进办法
    else if (p instanceof TreeNode) 
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 对链表进行遍历，并统计链表长度
      for (int binCount = 0; ; ++binCount) {
        // 链表中不包括要刺进的键值对节点时，则将该节点接在链表的最终
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 假如链表长度大于或等于树化阈值，则进行树化操作
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
         }
        
        // 条件为 true，标明当时链表包括要刺进的键值对，停止遍历
        if (e.hash == hash &&
           ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
       }
     }
    
    // 判别要刺进的键值对是否存在 HashMap 中
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      // onlyIfAbsent 标明是否仅在 oldValue 为 null 的状况下更新键值对的值
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
     }
   }
  ++modCount;
  // 键值对数量超过阈值时，则进行扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

putVal的首要逻辑：

  1. 当桶数组 table 为空时，经过resize(扩容)的办法初始化 table
  1. 假如定位到的数组方位有元素，存在的话假如 key 相同就直接掩盖，假如 key 不相同，就判别 p 是否是一个树节点，假如是就调用putTreeVal将元素添加进入。假如不是就遍历链表刺进(刺进的是链表尾部)。
  1. 假如定位到的数组方位没有元素，则将键值对链入链表中，并依据链表长度决议是否将链表转为红黑树（treeifyBin 树化操作）
  1. 判别键值对数量是否大于阈值，大于的话则进行扩容操作resize

能够看出来resize(扩容)在刺进操作的逻辑中非常重要，接下来咱们就讲HashMap的扩容机制。

扩容机制

resize办法 (扩容首要逻辑)

背景知识：在 HashMap 中，桶数组的长度均是2的幂，阈值巨细为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。

需求留意：进行扩容，会伴随着一次从头 hash 分配，而且会遍历 hash 表中一切的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

HashMap依照当时桶数组长度的2倍进行扩容，扩容之后，要从头核算键值对的方位，并把它们移动到适宜的方位上去。

详细完结：

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  // 假如 table 不为空，标明现已初始化过了
  if (oldCap > 0) {
    // 当 table 容量超过容量最大值，则不再扩容
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
     } 
    // 按旧容量和阈值的2倍核算新容量和阈值的巨细
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
   } else if (oldThr > 0) // initial capacity was placed in threshold
    /*
     * 初始化时，将 threshold 的值赋值给 newCap，
     * HashMap 运用 threshold 变量暂时保存 initialCapacity 参数的值
     */ 
    newCap = oldThr;
  else {        // zero initial threshold signifies using defaults
    /*
     * 调用无参构造办法时，桶数组容量为默许容量，
     * 阈值为默许容量与默许负载因子乘积
     */
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
  
  // newThr 为 0 时，按阈值核算公式进行核算
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
          (int)ft : Integer.MAX_VALUE);
   }
  threshold = newThr;
  // 创立新的桶数组，桶数组的初始化也是在这儿完结的
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    // 假如旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 从头映射时，需求对红黑树进行拆分
           ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          // 遍历链表，并将链表节点按原顺序进行分组
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
             }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
             }
           } while ((e = next) != null);
          // 将分组后的链表映射到新桶中
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
           }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
           }
         }
       }
     }
   }
  return newTab;
}

resize办法的首要逻辑：

  1. 核算新桶数组的容量 newCap 和新阈值 newThr

    // 第一个条件分支
if ( oldCap > 0) {
  // 嵌套条件分支
  if (oldCap >= MAXIMUM_CAPACITY) {...}
  else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
} 
else if (oldThr > 0) {...}
else {...}
​
// 第二个条件分支
if (newThr == 0) {...}

    分支一：

    • oldCap>0：桶数组table现已被初始化，这种状况下，会将 oldThr 赋值给 newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。咱们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。

    • oldThr>0：threshold>0, 且桶数组未被初始化，调用 HashMap(int) 和 HashMap(int, float) 构造办法时会发生这种状况，此种状况下 newCap = oldThr，newThr 在第二个条件分支中算出

    • oldCap == 0 && oldThr == 0：桶数组未被初始化，且 threshold 为 0，调用 HashMap() 构造办法会发生这种状况。

    嵌套分支：

    • oldCap >= MAXIMUM_CAPACITY：桶数组容量大于或等于最大桶容量 2^30，这个时分不再扩容

    • newCap < MAXIMUM_CAPACITY && oldCap > DEFAULT_INITIAL_CAPACITY：新桶数组容量小于最大值，且旧桶数组容量大于 16

    分支二：

    • newThr == 0：第一个条件分支未核算 newThr 或嵌套分支在核算进程中导致 newThr 溢出归零

  2. 依据核算出的 newCap 创立新的桶数组，桶数组 table 也是在这儿进行初始化的

  3. 将键值对节点从头映射到新的桶数组里。假如节点是 TreeNode 类型，则需求拆分红黑树。假如是普通节点，则节点按原顺序进行分组。该种状况下新阈值 newThr = oldThr << 1，移位或许会导致溢出。

    那么如何链表是从头映射呢？

    往底层数据结构中刺进节点时，先经过模运算核算桶方位，接着把节点放入桶中即可。咱们能够将从头映射看作是刺进操作，JDK1.7确实便是这样做的。

    但在JDK1.8中对进程进行了一定优化，从头映射节点需求考虑节点类型。关于树形节点，需先拆分红黑树再映射。关于链表类型节点，则需先对链表进行分组，然后再映射。需求的留意的是，分组后，组内节点相对方位保持不变。

    看个比如：

    必须要学习的源码--HashMap

    假如咱们对上图桶数组进行扩容，扩容后容量 n =16，从头映射进程如下：

    顺次遍历链表，并核算节点 hash & oldCap 的值。

    35&8=0; 27&8!=0; 19&8=0; 43&8!=0;

    假如值为0，将 loHead 和 loTail 指向这个节点。假如后边还有节点 hash & oldCap 为0的话，则将节点链入 loHead 指向的链表中，并将 loTail 指向该节点。假如值为非0的话，则让 hiHead 和 hiTail 指向该节点。完结遍历后，或许会得到两条链表，此刻就完结了链表分组：

    必须要学习的源码--HashMap

    最终将这两条连直接寄存到对应的桶中，完结扩容。

    必须要学习的源码--HashMap

    JDK1.8的HashMap扩容功率是要高于之前版别的。JDK1.7为了防止因hash磕碰引发的拒绝服务进犯，在核算hash进程中引进随机种子，为了增强hash的随机性，使得键值对均匀分布在桶数组中。在扩容进程中，相关办法会依据容量判别是否需求生成新的随机种子，并从头核算一切节点的hash。而在JDK1.8中则经过引进红黑树替代了该办法。从而避免了多次核算hash的操作，提高了扩容功率。

以上咱们就讲完了扩容的主体逻辑。扩容后，红黑树节点和普通节点相同是需求从头映射的。于是咱们接着就说红黑树的分组和从头映射。(split办法的调用能够在resize办法体中找到。)

split办法 (红黑树拆分)

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
​
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  TreeNode<K,V> b = this;
  // Relink into lo and hi lists, preserving order
  TreeNode<K,V> loHead = null, loTail = null;
  TreeNode<K,V> hiHead = null, hiTail = null;
  int lc = 0, hc = 0;
  /* 
   * 红黑树节点依然保留了 next 引证，故仍能够按链表办法遍历红黑树。
   * 下面的循环是对红黑树节点进行分组，与上面相似
   */
  for (TreeNode<K,V> e = b, next; e != null; e = next) {
    next = (TreeNode<K,V>)e.next;
    e.next = null;
    if ((e.hash & bit) == 0) {
      if ((e.prev = loTail) == null)
        loHead = e;
      else
        loTail.next = e;
      loTail = e;
      ++lc;
     }
    else {
      if ((e.prev = hiTail) == null)
        hiHead = e;
      else
        hiTail.next = e;
      hiTail = e;
      ++hc;
     }
   }
​
  if (loHead != null) {
    // 假如 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
    if (lc <= UNTREEIFY_THRESHOLD)
      tab[index] = loHead.untreeify(map);
    else {
      tab[index] = loHead;
      /* 
       * hiHead == null 时，标明扩容后，
       * 一切节点仍在原方位，树结构不变，无需从头树化
       */
      if (hiHead != null) 
        loHead.treeify(tab);
     }
   }
  // 与上面相似
  if (hiHead != null) {
    if (hc <= UNTREEIFY_THRESHOLD)
      tab[index + bit] = hiHead.untreeify(map);
    else {
      tab[index + bit] = hiHead;
      if (loHead != null)
        hiHead.treeify(tab);
     }
   }
}

从头映射红黑树的逻辑和从头映射链表的逻辑根本一致。不同的当地在于，从头映射后，会将红黑树拆分红两条由 TreeNode 组成的链表。假如链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。不然依据条件从头将 TreeNode 链表树化。

举个比如：

必须要学习的源码--HashMap

咱们对该桶数组进行扩容,扩容后需求从头映射上面的红黑树，映射成果如下：

必须要学习的源码--HashMap

treeifyBin办法 (链表树化)

JDK1.8对HashMap完结进行了改进。最大的改进便是引进了红黑树。

关于红黑树能够参阅我的另一篇博客：/post/713683…

树化相关的代码:

static final int TREEIFY_THRESHOLD = 8;
​
/**
 * 当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;
​
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent; // red-black tree links
  TreeNode<K,V> left;
  TreeNode<K,V> right;
  TreeNode<K,V> prev;  // needed to unlink next upon deletion
  boolean red;
  TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
   }
}
​
/**
 * 将普通节点链表转换成树形节点链表
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    // hd 为头节点（head），tl 为尾节点（tail）
    TreeNode<K,V> hd = null, tl = null;
    do {
      // 将普通节点替换成树形节点
      TreeNode<K,V> p = replacementTreeNode(e, null);
      if (tl == null)
        hd = p;
      else {
        p.prev = tl;
        tl.next = p;
       }
      tl = p;
     } while ((e = e.next) != null); // 将普通链表转成由树形节点链表
    if ((tab[index] = hd) != null)
      // 将树形链表转换成红黑树
      hd.treeify(tab);
   }
}
​
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
  return new TreeNode<>(p.hash, p.key, p.value, next);
}

扩容的进程中，树化需求满意两个条件:

  1. 链表长度大于等于 TREEIFY_THRESHOLD

    链表长度大于等于了树化阈值，也便是咱们面试常考的8，才进行树化。

  2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY

    桶数组容量比较小的时分，应当优先扩容，削减hash磕碰的概率。

HashMap在设计之初，没有考虑到以后会引进红黑树进行优化。所以并没有像TreeMap相同，要求键类完结Comparable接口，或提供对应的比较器。但由于树化的进程需求比较两个键对象的巨细，在键类没有完结Comparable接口的状况下，这成了一个问题。HashMap做了三步操作。经过下面三步操作就能知道谁大谁小，最终构造出红黑树了。

  1. 比较键与键之间hash的巨细，假如hash相同，持续往下比较。
  2. 检测键类是否完结了Comparable接口，假如完结调用compareTo办法进行比较
  3. 假如仍未比较出巨细，据需求进行裁定了，裁定办法为tieBreadOrder

untreeify办法 (红黑树链化)

红黑树中依然保留了原链表节点的顺序。有了这个前提，将红黑树转化成链表，仅需将 TreeNode 链表转换成 Node 类型的链表即可。

final Node<K,V> untreeify(HashMap<K,V> map) {
  Node<K,V> hd = null, tl = null;
  // 遍历 TreeNode 链表，并用 Node 替换
  for (Node<K,V> q = this; q != null; q = q.next) {
    // 替换节点类型
    Node<K,V> p = map.replacementNode(q, null);
    if (tl == null)
      hd = p;
    else
      tl.next = p;
    tl = p;
   }
  return hd;
}
​
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
  return new Node<>(p.hash, p.key, p.value, next);
}

remove办法 (删去)

HashMap 的删去操作并不杂乱，进口办法为remove，首要逻辑在removeNode办法。

删去仅需三个步骤即可完结。第一步是定位桶方位，第二步遍历链表并找到键值持平的节点，第三步删去节点。相关源码如下：

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}
​
final Node<K,V> removeNode(int hash, Object key, Object value,
              boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
    // 1. 定位桶方位
     (p = tab[index = (n - 1) & hash]) != null) {
    Node<K,V> node = null, e; K k; V v;
    // 假如键的值与链表第一个节点持平，则将 node 指向该节点
    if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
      node = p;
    else if ((e = p.next) != null) { 
      // 假如是 TreeNode 类型，调用红黑树的查找逻辑定位待删去节点
      if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else {
        // 2. 遍历链表，找到待删去节点
        do {
          if (e.hash == hash &&
             ((k = e.key) == key ||
             (key != null && key.equals(k)))) {
            node = e;
            break;
           }
          p = e;
         } while ((e = e.next) != null);
       }
     }
    
    // 3. 删去节点，并修正链表或红黑树
    if (node != null && (!matchValue || (v = node.value) == value ||
               (value != null && value.equals(v)))) {
      if (node instanceof TreeNode)
         ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      else if (node == p)
        tab[index] = node.next;
      else
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
     }
   }
  return null;
}

HashMap 的运用

HashMap 的几种遍历办法

总共的遍历办法在查阅后发现有7种。

遍历办法首要分红下面的四个方向：

  1. 迭代器（Iterator）办法遍历。

    // 遍历 EntrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
  Map.Entry<Integer, String> entry = iterator.next();
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
}
​
​
// 遍历 KeySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
  Integer key = iterator.next();
  System.out.println(key);
  System.out.println(map.get(key));
}

  1. For Each 办法遍历。

    // 遍历 EntrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
}
​
​
// 遍历 KeySet
for (Integer key : map.keySet()) {
  System.out.println(key);
  System.out.println(map.get(key));
}

  1. Lambda 表达式遍历（JDK 1.8+）。

    // 遍历
map.forEach((key, value) -> {
  System.out.println(key);
  System.out.println(value);
});

  1. Streams API 遍历（JDK 1.8+）。

    // 遍历 单线程
map.entrySet().stream().forEach((entry) -> {
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
});
​
// 遍历 多线程
map.entrySet().parallelStream().forEach((entry) -> {
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
});

entrySet的功能比keySet的功能高，所以咱们还是尽量运用entrySet来遍历HashMap。

小结

HashMap是Java学习者绕不过去的一道坎，无论是敷衍面试或许是实际的使用都要常常和这个数据结构打交道。本文参阅了许多前人的剖析并由自己消化，最终呈现出来。不得不说对源码的深化理解需求很多的功夫，需求融汇诸多思考。所以在我有新的思考之后或许会对文章再做更新，期望能为这思考再加上一层。

参阅文章：

  • segmentfault.com/a/119000001…
  • www.jianshu.com/p/3d66446a0…
  • www.jianshu.com/p/effb601f2…
  • www.jianshu.com/p/2fee1d246…
  • javaguide.cn/java/collec…
  • mp.weixin.qq.com/s/zQBN3UvJD…