1.HashMap实现原理

简述HashMap的工作原理：

HashMap是基于散列法（又称哈希法）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。使用HashMap进行查询和修改的速度都很快，平均时间复杂度O(1)。HashMap非线程安全，如果需要考虑并发，则需要使用ConcurrentHashMap，且HashMap不保证存储元素的序列；

2.HashMap的底层结构

JDK18之前：数组+链表

JDK1.8之后：数组+链表+红黑树

特点是HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！

在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

3.源码阅读

3.1.HashMap的继承与实现

HashMap实现了Cloneable，可以被克隆。
HashMap实现了Serializable，可以被序列化。
HashMap继承自AbstractMap，实现了Map接口，具有Map的所有功能。

1 2	public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}

具体继承如下所示：

3.2.HashMap的基本属性及内部类

3.2.1 基本属性

/**
  * 哈希数组初始容量
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 /**
  * 哈希数组最大容量
  */
 static final int MAXIMUM_CAPACITY = 1 << 30;

 /**
  * HashMap默认装载因子（负载因子）
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  * 当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容
  */
 static final int TREEIFY_THRESHOLD = 8;

 /**
  * 哈希槽（链）上的红黑树上的元素数量减少到此值时，将红黑树转换为链表
  */
 static final int UNTREEIFY_THRESHOLD = 6;

 /**
  * 当桶的个数达到64的时候才进行树化
  * 即是说当桶数组容量小于该值时，优先进行扩容，而不是树化
  */
 static final int MIN_TREEIFY_CAPACITY = 64;

 /**
  * 哈希数组
  */
 transient Node<K,V>[] table;

 /**
  * entry集合
  */
 transient Set<Map.Entry<K,V>> entrySet;

 /**
  * HashMap的元素数量
  */
 transient int size;

 /**
  *  HashMap结构的修改次数
  */
 transient int modCount;

 /**
  * (The javadoc description is true upon serialization.
  * Additionally, if the table array has not been allocated, this
  * field holds the initial array capacity, or zero signifying
  * DEFAULT_INITIAL_CAPACITY.)
  * HashMap扩容阈值，并没有默认阈值，原因是阈值可由容量乘上负载因子计算而来（注释中有说明）
  * 计算公式：threshold = capacity * loadFactor
  */
 int threshold;

 /**
  * HashMap当前使用的装载因子
  */
 final float loadFactor;

上面举例了一些HashMap的属性字段，比较有意思的是羡慕几个属性字段，在接下来中会单拎出来进行详细讲解。：

哈希数组的初始容量：DEFAULT_INITIAL_CAPACITY
负载因子：loadFactor
链表树化与树化链表的两个阈值：UNTREEIFY_THRESHOLD 和TREEIFY_THRESHOLD

3.2.2 Node内部类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！

3.2.3 TreeNode内部类

TreeNode是一个典型的树型节点，其中，prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。

// 位于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;
}

// 位于LinkedHashMap中，典型的双向链表节点
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

3.3.HashMap的四种构造及参数分析

无参构造，初始化一个哈希数组容量为16，装载因子为0.75的HashMap

/**
 * Constructs an empty {@code HashMap} with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

初始化一个哈希数组容量为initialCapacity，装载因子为0.75的HashMap

/**
 * Constructs an empty {@code HashMap} with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

初始化一个哈希数组容量为initialCapacity，装载因子为loadFactor的HashMap

/**
   * Constructs an empty {@code HashMap} with the specified initial
   * capacity and load factor.
   *
   * @param  initialCapacity the initial capacity
   * @param  loadFactor      the load factor
   * @throws IllegalArgumentException if the initial capacity is negative
   *         or the load factor is nonpositive
   */
  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);
  }

使用指定的HashMap中的元素来初始化一个新的HashMap

/**
 * Constructs a new {@code HashMap} with the same mappings as the
 * specified {@code Map}.  The {@code HashMap} is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified {@code Map}.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将指定HashMap中的元素存入到当前HashMap（允许覆盖）
    putMapEntries(m, false);
}

我们这这里对几个字段进行解释一下：

3.4.查询

3.4.1.查询HashMap大小

该方法返回HashMap的大小，键值对的数目：

1
2
3

public int size() {
    return size;
}

3.4.2 查询HashMap是否为空

1
2
3

public boolean isEmpty() {
    return size == 0;
}

3.4.3.查询HashMap是否存在指定key

1
2
3

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

3.4.4.查询HashMap中是否存在指定value的元素

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        // 进行循环遍历查找value
        for (Node<K,V> e : tab) {
            for (; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

3.5.取值

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

它调用了getNode(int hash, Object key)方法，详细代码如下所示：

final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      // 如果桶的数量大于0，并且所查找的key所在的桶的第一个元素不为空
      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) {
              // 如果第一个元素是树节点，则按树的方式查找
              if (first instanceof TreeNode)
                  return ((TreeNode<K,V>)first).getTreeNode(hash, key);
              do {
                  // 否则就遍历整个链表查找该元素
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
  }

3.6.添加

3.6.1.HashMap的添加过程

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

实际上它调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法，详细代码如下所示：

/*
 * 向当前Map中存入新的元素，并返回旧元素
 *
 * hash         key的哈希值
 * onlyIfAbsent 是否需要维持原状（不覆盖旧值）
 * evict        如果为false，则表处于创建模式。
 *
 * 返回同位元素的旧值（在当前Map中占据相同位置的元素）
 * 如果不存在同位元素，即插入了新元素，则返回null
 * 如果存在同位元素，但同位元素的旧值为null，那么也返回null
 *
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果桶的长度为0，未初始化，则进行初始化并得到长度n
    if ((tab = table) == null || (n = tab.length) == 0)
        // 调用resize进行初始化
        n = (tab = resize()).length;
    // 如果桶中还没有元素，则将要插入的key和value放到第一位
    // 使用(n - 1) & hash 计算元素在哪个桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {  // 桶中此时已存在元素
        Node<K,V> e; K k;
        // 如果待插入的元素的hash值和key值与第一个元素的哈希值和key相同，保存到e用于后续修改value值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) // 如果桶的第一个元素为树节点，则调用树节点的putTreeVal方法插入元素
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
            for (int binCount = 0; ; ++binCount) {
                // 遍历整个链表，没有相同哈希值和key的元素，则在链表最后插入该key和value结点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果插入结点之后的长度大于等于8，则树化
                    // 这里-1的解释为：因为第一个元素没有加到binCount中，所以这里-1
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 进行树化
                        treeifyBin(tab, hash);
                    break;
                }
                // 假如待插入的key在链表中找到，则退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了对应key的元素
        if (e != null) { // existing mapping for key
            V oldValue = e.value;   // 记录旧值
            // 判断是否需要替换旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;    // 替换旧值为新值
            // 在节点被访问后做点什么事，在LinkedHashMap中用到
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 到了此处证明没有找到元素，即添加了新元素，修改次数加1
    ++modCount;
    // 如果哈希数组的容量已超过阈值，则需要对哈希数组扩容
    if (++size > threshold)
        resize();
    // 在节点插入后做点什么事，在LinkedHashMap中用到
    afterNodeInsertion(evict);
    return null;
}

添加方法除了可以单个key-value键值对的添加，还可以将指定HashMap中的元素存入到当前HashMap中（允许覆盖），详细代码如下：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 如果当前HashMap的哈希数组还未初始化
        if (table == null) { // pre-size
            // 根据HashMap中的元素数量反推哈希数组的最低容量要求
            float ft = ((float)s / loadFactor) + 1.0F;  // 注意这里!!!!
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果大于需要扩容的阈值，则重新计算扩容阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        } else {
            // Because of linked-list bucket constraints, we cannot
            // expand all at once, but can reduce total resize
            // effort by repeated doubling now vs later
            // 由于链表存储桶的限制，我们无法一次全部扩展
            // 但可以通过立即加倍与以后加倍来减少总的调整工作量
            // 初始化哈希数组，或者对哈希数组扩容，并返回新的哈希数组
            while (s > threshold && table.length < MAXIMUM_CAPACITY)
                resize();
        }
        // 循环遍历进行添加，允许覆盖
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

3.6.2.HashMap的扩容过程

/*
 * 扩容机制：在初始化时、对哈希数组扩容时两种情况下调用
 *
 */
final Node<K,V>[] resize() {
    // 旧数组
    Node<K,V>[] oldTab = table;
    // 旧容量，或者未初始化时的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧扩容阈值
    int oldThr = threshold;
    // 新容量、新扩容阈值
    int newCap, newThr = 0;
    // 如果哈希数组已经初始化，不是首次进入
    if (oldCap > 0) {
        // 如果旧容量大于最大容量，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果旧容量的两倍（左移一位）小于最大容量，并且大于默认初始容量（16）
        // 则新容量扩大为旧容量的两倍，扩容阈值也扩大为旧阈值的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果哈希数组还未初始化（首次进来）并且实例化HashMap的时候指定了初始容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 则将哈希数组的当前容量初始化为与旧阈值一样大（传入初始容量时候会调用tableSizeFor()方法）
        newCap = oldThr;
    // 如果哈希数组还未初始化（首次进来）并且实例化HashMap的时候没有指定了初始容量
    else {               // zero initial threshold signifies using defaults
        // 则使用默认的初始容量（16）和默认公式计算的阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新扩容阈值为0，则使用公式计算得到新的扩容阈值，并且不可超过最大容量
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 赋值扩容阈值为新扩容阈值
    threshold = newThr;
    // 根据新扩容容量建立一个新容量的数组
    @SuppressWarnings({"rawtypes","unchecked"})
    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;
            // 如果桶中的第一个元素不为空，则赋值给e
            if ((e = oldTab[j]) != null) {
                // 清空旧桶，帮助GC
                oldTab[j] = null;
                // 如果桶中只有一个元素，进行新桶的位置定位，并搬迁
                // 注意：只有第一个元素才可以这样，因为每次扩容都是两倍
                //       则第一个元素搬移到新桶的时候肯定还没有元素
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果该哈希槽上链接了不止一个元素，且该元素是TreeNode类型
                else if (e instanceof TreeNode)
                    // 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去
                    // 拆分红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果这个链表不止一个元素且不是一颗树
                    // 则进行分化成两个链表插到新的桶中
                    // 举例：假如原来容量为4，3、7、11、15这四个元素都在三号桶中
                    // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
                    // 也就是分化成了两个链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // (e.hash & oldCap) == 0的元素放在低位链表中
                        // 比如，3 & 4 == 0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // (e.hash & oldCap) != 0的元素放在高位链表中
                            // 比如，7 & 4 != 0
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历完成得到两个链表
                    // 低位链表在新桶的位置与旧桶一样（即3和11还在三号桶中）
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3.7.移除

/**
 * 根据传入的key进行数据移除元素，并返回刚刚移除的元素的值
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

实际上它调用了removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)方法，详细代码如下所示：

/*
 * 从HashMap中移除指定的元素，并返回刚刚移除的元素（移除失败返回null）
 *
 * matchValue 移除元素时是否需要考虑value的匹配问题
 * movable    移除元素后如果红黑树根结点发生了变化，那么是否需要改变结点在链表上的顺序
 */
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;
    // 如果桶的数量大于0（不空）且待删除的元素所在的桶的第一个元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (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) {
            // 如果该Tab的第一个元素是树节点，则以树的方式进行寻找
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 否则，就以链表的形式进行遍历寻找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果找到了该元素，则进行值比对
        // 根据传递进来的matchValue判断是否需要匹配
        // 如果不需要匹配直接删除，如果需要匹配看是否与传入的value相等
        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);
            // 如果待删除的元素是第一个元素，则将第二个元素移到到第一个元素的位置
            // 注意：上面的代码可知，node==p的情况只有待删除元素node是第一个结点才会发生
            else if (node == p)
                tab[index] = node.next;
            // 如果待删除的元素不是第一个元素，则将中间结点连接断开（单向链表）
            else
                p.next = node.next;
            // 修改次数＋1
            ++modCount;
            // size-1
            --size;
            // 删除结点之后应处理的事情
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

桃花岛杂货铺

Java 集合框架 - HashMap 分析