HashMap源码解析

前言
关键变量
构造函数
- 构造函数总结
添加键值对
- 哈希函数
- 计算键值对要存入的位置
- put函数
- 新增键值对put方法总结
resize函数
- (e.hash & oldCap) == 0判断结点的位置是否会改变
get方法
HashMap的线程不安全问题
- 多线程put导致数据丢失问题
- 并发修改异常
- JDK7时由于resize导致的死循环问题

前言

HashMap相信大家在日常业务中也经常使用，其使用哈希表+链表的数据结构，使得我们可以利用哈希表的特性快速取出数据，又通过链表的形式来避免由于哈希冲突导致数据覆盖问题，我们今天通过JDK18的源码来分析HashMap的各种方法执行原理。

关键变量

我们先来查看HashMap的重要的关键变量，这些变量在我们后面的源码分析中起到重要作用。

// 哈希表默认的初始容量大小，为16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 哈希表最大容量大小，为2^30 static final int MAXIMUM_CAPACITY = 1 << 30;// 负载因子，与哈希表的扩容有关，static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表转换为树的阈值static final int TREEIFY_THRESHOLD = 8;// 红黑树转换为链表的阈值static final int UNTREEIFY_THRESHOLD = 6;// 哈希表transient Node<K,V>[] table;// map集合中的键值对数量transient int size;// 哈希表进行扩容的阈值，当 size>threshold时进行扩容，threshold = cap * loadFactorint threshold;// 负载因子final float loadFactor;// HashMap的结构修改次数，每当对HashMap元素进行插入、删除等就会将修改次数+1，用于确保在使用迭代器迭代HashMap时若存在其他线程修改HashMap结构会直接抛出异常 transient int modCount;

构造函数

// 不传入任何参数时只会设置负载因子为默认负载因子public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}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;}

可以看出这个函数内是对初始容量最初了一些位运算，主要目的是获取大于等于传入的初始容量参数的最小二次幂。

构造函数总结

我们可以发现这三个构造函数内都没有进行哈希表的初始化，只设置了负载因子和表的阈值，负载因子的默认值位0.75或者传入的参数，而阈值为大于传入哈希表容量的最小2的幂次方。

添加键值对

当新添加键值对时，HashMap首先会计算键的哈希值，然后计算要存入的位置。

哈希函数

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

可以看到，哈希函数是通过先计算键值的原始哈希值，然后将原哈希值无符号的向右移十六位再与原哈希值进行异或运算，得到哈希值，这个操作的主要目的是为了让原哈希值的高位和低位混合均匀，都参与运算，减少哈希冲突。

计算键值对要存入的位置

当新添加键值对时，HashMap首先会计算键的哈希值，然后计算要存入的位置，HashMap通过(n - 1) & hash即哈希值通过对表的长度求余来得到要存入键值对的位置。

put函数

    public V put(K key, V value) {// 通过hash函数计算哈希值，进入putval方法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;// 检查哈希表有没有初始化，如果没有初始化调用resize函数进行初始化//并且将tab数组设置为初始化后的哈希表，n设置为哈希表的大小if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 通过(n-1)&hash计算键值对要存入的位置，并且判断哈希表这个位置有没有键值对，如果没有，直接创建结点插入// 并且将p设置为要插入键值对的位置的头结点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// e是需要被覆盖的结点，即其键和要插入的键值对的键相同Node<K,V> e; K k;// 如果头节点的哈希值和要插入的键值对的哈希值相同，并且其键相同，将p复制给eif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果p是红黑树上的结点，进入红黑树的插入方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 此时头结点和要插入的结点的键不同，开始对该链表进行遍历else {for (int binCount = 0; ; ++binCount) {// 如果将要遍历的下一个节点结点为null，那么就插入键值对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;// 如果遍历的结点不为null并且键值和要插入的键不同，将e复制给p将继续循环遍历p = e;}}// 如果e不为null，进行值的更新if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 添加HashMap的修改次数++modCount;// 判断哈希表是否需要进行扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

新增键值对put方法总结

首先调用哈希函数，即计算键的原始哈希值，将原哈希值无符号的向右移16位与原哈希值做异或运算得到哈希值，然后判断哈希表有没有进行初始化，如果没有调用resize方法对初始化哈希表，之后通过哈希值和哈希表大小求余获取要插入哈希表中的位置，取出该位置的头结点，判断是否为null，如果为null直接包装成结点插入，如果不是头节点，判断该结点是否是红黑树的结点，如果是进行红黑树的插入逻辑，如果不是，遍历链表，在遍历的过程中，查看是否有键相同的结点，如果有，则进行结点覆盖即值的更新并且返回被覆盖的值，如果没有，插入键值对，并且判断链表长度有没有达到树化阈值，如果有转换为红黑树，最后判断哈希表中键值对的数量有没有大于法制，如果大于法制，就进行扩容。

resize函数

在我们上面解析源码的过程中，我们发现有两个地方调用了resize函数，第一次是判断哈希表有没有初始化，然后调用resize函数进行初始化，第二次调用resize进行扩容

  final Node<K,V>[] resize() {// 获取原哈希表Node<K,V>[] oldTab = table;// 获取当前哈希表大小int oldCap = (oldTab == null) ? 0 : oldTab.length;// 获取当前哈希表扩容阈值int oldThr = threshold;int newCap, newThr = 0;// 如果原哈希表容量大于0，说明此时进行的是哈希表的扩容操作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}// 原哈希表容量=0，说明还未进行初始化，此时进行的是哈希表初始化的逻辑// 如果原哈希表还未进行初始化但是其阈值大于0，则我们已经在构造函数中初始化了阈值，阈值是大于等于传入初始容量的最小的2的幂次方（可以到我们上面介绍的构造函数中再次查看）else if (oldThr > 0) // initial capacity was placed in threshold// 将阈值赋给新哈希表的容量newCap = oldThr;// 如果原哈希表阈值=0，说明我们在构造函数中只设置了默认负载因子，并没有设置阈值else {               // zero initial threshold signifies using defaults// 设置哈希表的容量为默认容量大小(16)，并且计算哈希表阈值为16*0.75=12newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 在以上的几种情况中，只有oldThr>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;// 如果头节点非空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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}

(e.hash & oldCap) == 0判断结点的位置是否会改变

我们假设一个初始容量为16的哈希表，扩容后的容量为32,
它们二进制位如下: 1 0 0 0 0 和 1 0 0 0 0 0 0
假设一个二进制数 1 0 1 0 1 1，其和 oldCap进行运算：

在这里插入图片描述
我们可以看到只要随机hash的第五位数为0，那么hash&oldCap=0；
我们进行位置运算时需要通过哈希值需要对 0 0 1 1 1 1 和 0 1 1 1 1 1分别进行与运算来获取要插入的位置
由于第五位数为0，哈希值分别与cap-1进行与运算第五位一定为0，而哈希表和新哈希表进行运算的哈希值除第五个二进制位其他二进制位都相同，那么进行运算得到的位置是相同的。

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) {// 如果头结点是红黑树的结点，执行红黑树相关查询逻辑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;}

至于remove方法，和get方法大差不差，大家可以自己尝试读取源码查看