简略介绍

什么是 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便是一个桶数组，当桶内数据超过八个之后，桶内存储结构会由链表变成红黑树。

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

类的特点：

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 所能包容键值对数量的最大值，超过这个值，则需扩容）

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。核算进程如下：

最终成果为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的首要逻辑：

当桶数组 table 为空时，经过resize(扩容)的办法初始化 table

假如定位到的数组方位有元素，存在的话假如 key 相同就直接掩盖，假如 key 不相同，就判别 p 是否是一个树节点，假如是就调用putTreeVal将元素添加进入。假如不是就遍历链表刺进(刺进的是链表尾部)。

假如定位到的数组方位没有元素，则将键值对链入链表中，并依据链表长度决议是否将链表转为红黑树（treeifyBin 树化操作）

判别键值对数量是否大于阈值，大于的话则进行扩容操作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办法的首要逻辑：

核算新桶数组的容量 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 溢出归零
依据核算出的 newCap 创立新的桶数组，桶数组 table 也是在这儿进行初始化的
将键值对节点从头映射到新的桶数组里。假如节点是 TreeNode 类型，则需求拆分红黑树。假如是普通节点，则节点按原顺序进行分组。该种状况下新阈值 newThr = oldThr << 1，移位或许会导致溢出。

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

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

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

看个比如：

假如咱们对上图桶数组进行扩容，扩容后容量 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 指向该节点。完结遍历后，或许会得到两条链表，此刻就完结了链表分组：

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

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 链表树化。

举个比如：

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

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

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

链表长度大于等于 TREEIFY_THRESHOLD

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

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

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

比较键与键之间hash的巨细，假如hash相同，持续往下比较。
检测键类是否完结了Comparable接口，假如完结调用compareTo办法进行比较
假如仍未比较出巨细，据需求进行裁定了，裁定办法为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种。

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

迭代器（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));
}

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

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

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

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…

必须要学习的源码–HashMap

简略介绍

什么是 HashMap？

HashMap 的特性

HashMap 源码剖析

底层数据结构

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

hash办法（扰动函数）

get办法 (查找)

put办法 (刺进)

扩容机制

resize办法 (扩容首要逻辑)

split办法 (红黑树拆分)

treeifyBin办法 (链表树化)

untreeify办法 (红黑树链化)

remove办法 (删去)

HashMap 的运用

HashMap 的几种遍历办法

小结

作者信息

推广

必须要学习的源码–HashMap

简略介绍

什么是 HashMap？

HashMap 的特性

HashMap 源码剖析

底层数据结构

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

hash办法（扰动函数）

get办法 (查找)

put办法 (刺进)

扩容机制

resize办法 (扩容首要逻辑)

split办法 (红黑树拆分)

treeifyBin办法 (链表树化)

untreeify办法 (红黑树链化)

remove办法 (删去)

HashMap 的运用

HashMap 的几种遍历办法

小结

相关文章

迁移到云原生：如何使用微服务迁移应用程序

【每日算法】利用二段性找最大 H 指数 ｜Python 主题月

货拉拉出行iOS用户端启动优化实践

数据科学家必备工具：Pandas「一行代码」操作精选

作者信息

推广

【每日算法】利用二段性找最大 H 指数｜Python 主题月