HashMap源码分析

写在前面

HashMap的实现原理、扩容机制在jdk1.7以前和jdk1.8以后有着很大的区别，由于我的电脑上的版本是jdk21，所以以下近针对jdk1.8以后。

底层实现

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

transient Node<K,V>[] table;

在jdk1.8中，hashmap是由数组+链表/红黑树构成的。数组中每个位置存放的都是链表或者红黑树。图解如下：

一些重要参数

默认初始化大小：16，这个是指桶的数量，一般都是2的次幂

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

负载因子：0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

桶的树化阈值：8

static final int TREEIFY_THRESHOLD = 8;

桶的链表还原阈值：6

static final int UNTREEIFY_THRESHOLD = 6;

最小树形化容量阈值：64

static final int MIN_TREEIFY_CAPACITY = 64;

扩容阈值Threshold：

初始化Threshold的方法tableSizeFor()

static final int tableSizeFor(int cap) {
    	// 得到比capacity大的最小的2的幂次方数-1的数
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

会得到一个大于等于传入的capacity的最小2次幂。

tips：在初始化的时候，阈值是等于容量的；当放入第一个元素后，重新计算阈值，新的阈值=容量X负载因子。

初始化

当HashMap创建完成之后，并没有初始化table数组，而是在第一次存放元素的时候才会通过resize方法执行初始化操作。

一般不会修改负载因子，这里只说initialCapacity。

有两种情况：

1. 第一种：无参构造。

   

   不指定capacity大小时，默认初始化大小为16。

2. 第二种：指定初始容量的有参构造。

   

   这里有点复杂，简单来说就是找到一个大于等于10的2的次幂进行初始化。

   详细来讲，首先是将capacity赋值为10，计算threshold为16。然后在resize里面oldCap是计算len的，第一次的话必然是0，oldThr的值是直接从threshold赋值的，这里是16。接下来会依次进入下面框起来的两个if语句里，在这里面把oldThr赋值给了newCap，其实就是将我们开始计算的threshold作为了新的capacity，然后根据capacity*loadFactor计算新的threshold。

   

扩容 & 迁移

1. 根据新的容量新建一个数组。

   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

2. 迁移：

   从数组的第一个元素开始向后遍历，根据元素的类型是链表还是红黑树来分情况处理：

   1. 元素既非链表也非红黑树，直接计算新的位置赋值
   2. 元素为单链表，遍历单链表，通过hash & oldCap结果是否0拆分为两个链表，为0时下标仍然为index，结果为1时下标为index + oldCap。
   3. 元素为红黑树，遍历红黑树通过hash & oldCap结果是否0拆分为两条单链表，如果拆分后的链表长度仍满足红黑树要求，则重建红黑树，如不满足，将TreeNode替换为Node，还原成单链表。

put操作

1. 计算hash值

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

2. 判断table是否初始化

   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;

3. 计算元素位置

   p = tab[i = (n - 1) & hash])

4. 目标位置没有元素存在

   if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);

   直接将key、value封装成Node对象之后存放在目标位置。

5. 目标位置有元素存在：需要找到具体的位置（要么key已经存在，找到那个node；要么key不存在，找到要插入的位置）

   case1：目标位置第一个元素的key值就是当前要push的key值

   if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
       e = p;

   case2：不满足case 1，且目标位置是红黑树结构

   if (p instanceof TreeNode)
       e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

   从树中逐级查找是否存在节点满足 “==“ 或 “equals”，如果存在，则将值替换，如果不存在则在原来的树中新增node。

   case3：不满足case 1，且目标位置是链表结构

   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;
           }
           if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
               break;
           p = e;
   }

   则从链表头向后查找满足 “==” 或 “equals” 的元素替换其value，如果找不到则新增节点到链表尾端。此时如果表长度到达桶的树化阈值，则将链表以hash值大小为基准构建红黑树。

   tips：

   如果table的长度还没有达到最小树形化容量阈值，则优先考虑扩容。

6. 一些善后工作

   新增操作会在返回前递增modCount和size并检查扩容阈值threshold，如果size超过了threshold，需要扩容，调resize方法，将容量翻倍。

   ++modCount;
   if (++size > threshold)  resize();

get操作

get操作不像push和remove会涉及到元素增多或者减少，所以没有什么特别的。先计算hash值查找桶，遍历桶对比是否有此key，有的话返回对应的value，没有则返回null。

remove操作

计算hash值，查找元素，进行删除

tips：如果是在红黑树中进行删除的，则需要检查是否要转链表。