Hashmap源码解析

1. 简介

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

2. 源码分析

2.1 结构

继承关系

属性

内部类

方法

构造方法

// 默认初始容量，使用位运算设置为 2 的 4 次方（16）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

// 最大容量，使用位运算设置为 2 的 30 次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子，用于确定何时进行哈希表的扩容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转化为红黑树的阈值，即链表长度大于等于 8 时，将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转化为链表的阈值，即红黑树节点数量小于等于 6 时，将红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 最小容量，当哈希表的容量小于此值时，不会进行红黑树的转化操作
static final int MIN_TREEIFY_CAPACITY = 64;
    
/* ---------------- Fields -------------- */

// 哈希表数组，存储键值对的桶
transient Node<K, V>[] table;

// 哈希表中的键值对集合的视图
transient Set<Map.Entry<K, V>> entrySet;

// 哈希表中键值对的数量
transient int size;

// 对哈希表进行结构修改的次数，用于实现迭代器的快速失败机制
transient int modCount;

// 哈希表的阈值，当键值对数量超过阈值时，进行扩容
int threshold;

// 哈希表的加载因子
final float loadFactor;

2.2 巧用运算快速定位下标

小知识

按位与 (&)：对应位置上的两个二进制位都为1时，结果位为1，否则为0。

1
2
3

int a = 5;  // 二进制: 0101
int b = 3;  // 二进制: 0011
int result = a & b;  // 结果: 0001 (1)

按位异或 (^)：对应位置上的两个二进制位相异时，结果位为1，相同时为0。

1
2
3

int a = 5;  // 二进制: 0101
int b = 3;  // 二进制: 0011
int result = a ^ b;  // 结果: 0110 (6)

左移 (<<)：将二进制位向左移动指定的位数，右侧用0填充。
1
2
int a = 5; // 二进制: 0101
int result = a << 2; // 结果: 10100 (20)
右移 (>>)：将二进制位向右移动指定的位数，左侧用符号位填充（对于正数，用0填充）。
1
2
int a = 20; // 二进制: 10100
int result = a >> 2; // 结果: 0101 (5)

无符号右移 (>>>)：将二进制位向右移动指定的位数，左侧用0填充。

1 2	int a = -20; // 二进制: 11111111111111111111111111101100（负数的补码表示） int result = a >>> 2; // 结果: 00111111111111111111111111111011 (1073741827)

static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

key的hashCode值

可以省略吗？
就 （n-1）& hash 这个运算来说，实际参与计算的只有低位，高位意义不大。所以对低16位进行扰动能大大降低下标冲突的概率。让高16位与低16位进行 ^ 运算（高位不变，低位变化），既满足要求又足够简单！

为什么要使用 & 运算符？
& ：对应位置上的数都是1时，结果值才是1，&运算符保证了计算出的下标一定小于n-1

2.3 get方法

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;
    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) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

2.4 put方法

流程图

代码

流程说明

HashMap put 过程

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未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hash冲突）
    else {
        Node<K,V> e; K k;
        //快速判断第一个节点table[i]的key是否与插入的key一样，若相同就直接使用插入的值p替换掉旧的值e。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        // 判断插入的是否是红黑树节点
        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);
                    // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

计算 key 的 hash 值。
- 计算方式是 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
检查当前数组是否为空，为空需要进行初始化，初始化容量是 16 ，负载因子默认 0.75。
计算 key 在数组中的坐标。
计算方式：(容量 - 1) & hash.
因为容量总是2的次方，所以-1的值的二进制总是全1。方便与 hash 值进行与运算。
如果计算出的坐标元素为空，创建节点加入，put 结束。
如果当前数组容量大于负载因子设置的容量，进行扩容。
如果计算出的坐标元素有值。
- 如果坐标上的元素值和要加入的值 key 完全一样，覆盖原有值。
- 如果坐标上的元素是红黑树，把要加入的值和 key 加入到红黑树。
- 如果坐标上的元素和要加入的元素不同（尾插法增加）。
  - 如果 next 节点为空，把要加入的值和 key 加入 next 节点。
  - 如果 next 节点不为空，循环查看 next 节点。
    如果发现有 next 节点的 key 和要加入的 key 一样，对应的值替换为新值。
  - 如果循环 next 节点查找超过8层还不为空，把这个位置元素转换为红黑树。

2.5 resize方法

resize流程

先计算新的hash表容量和新的容量阀值，然后初始化一个新的hash表，将旧的键值对重新映射在新的hash表里。如果在旧的hash表里涉及到红黑树，那么在映射到新的hash表中还涉及到红黑树的拆分

final Node<K,V>[] resize() {
      Node<K,V>[] oldTab = table;
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      int oldThr = threshold;
      int newCap, newThr = 0;
      //code-1：扩容
      if (oldCap > 0) {
          if (oldCap >= MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return oldTab;
          }
          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
              newThr = oldThr << 1; // double threshold
      }
      //code-2：设置阈值
      else if (oldThr > 0) // initial capacity was placed in threshold
          newCap = oldThr;
      else {               // zero initial threshold signifies using defaults
          newCap = DEFAULT_INITIAL_CAPACITY;
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }
      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;
      //code-3：旧数据保存在新数组里面
      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 {
                       //如果是多个节点的链表，将原链表拆分为两个链表
                      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);
                      //链表1存于原索引
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }
                      //链表2存于原索引加上原hash桶长度的偏移量
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }

如果超过了数组的最大容量，那么就直接将阈值设置为整数最大值，然后如果没有超过，那就扩容为原来的2倍。

//code-1：扩容
if (oldCap > 0) {
      if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
      }
      else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
          oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
}

//code-2：设置阈值
else if (oldThr > 0) //阈值已经初始化了，就直接使用
      newCap = oldThr;
else {    // 没有初始化阈值那就初始化一个默认的容量和阈值
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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;

扩容后长度为原hash表的2倍，是把hash表分为两半，分为低位和高位，通过（e.hash & oldCap） == 0 来判断，把原链表的键值对，一半放在低位，一半放在高位。
举个例子：容量n = 16，二进制为10000，第5位为1，e.hash & oldCap 是否等于0就取决于e.hash第5 位是0还是1，这就相当于有50%的概率放在新hash表低位（位子不变），50%的概率放在新hash表高位（原始位子+原始容量）。

resize时机

第一次添加元素时，即当HashMap的数组为null或者数组的长度为0时；
链表转红黑树、且数组容量小于64时；
数组容量大于扩容阈值时；

3. 常见问题

3.1 底层数据结构是什么？

数组+链表

3.2 如何扩容？

3.3 如何解决哈希冲突？

拉链法

3.4 HashCode的作用？

总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。

要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？这就是Object.equals方法了。但是，如果每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。

于是，Java采用了哈希表的原理。哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了；不相同，也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。所以这里存在一个冲突解决的问题（很少出现）。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

所以，Java对于eqauls方法和hashCode方法是这样规定的：
1、如果两个对象相等，那么它们的hashCode值一定要相等；
2、如果两个对象的hashCode相等，它们并不一定相等(在同一个链表上)。
简单来讲 hashCode() 是用来查找用的，equals() 是用来判断两个对象是否相等用的。

3.5 HashMap死循环问题

HashMap在多线程环境下，同时进行put操作，并且同时进行扩容时，链表上的元素顺序会反过来，会出现链表环，导致死循环。

注意：jdk8虽然改用了头插法避免了这个问题，但是在jdk8中当某个桶中的元素数量很多时，HashMap 在将元素转化为红黑树之前，需要将桶中的元素进行扩容和重新散列，以减少冲突。但是，如果在扩容和重新散列期间，另一个线程对 HashMap 进行了修改操作（如插入或删除元素），就可能会导致两个线程之间的竞争，进而导致死循环的问题。