HashMap源码分析系列-构建、扩容以及存放数据源码分析
程序员文章站
2022-06-24 18:50:37
HashMap源码分析系列——HashMap存放数据源码分析文章目录HashMap源码分析系列——HashMap存放数据源码分析前言一、介绍二、基础结构分析前言HashMap是在开发中用的比较多的一个集合，主要是因为HashMap对数据的存放以及读取提供了比较好的性能，并且也提供了比较多的迭代方法。因此，HashMap也慢慢成了面试中常见的一个重点，对于面试者而言，仅仅了解HashMap的常见用法是不够的，也需要对其原理进行一个整体的学习，这样才能应付面试过程中相对困难的题目。一、介绍Hash...
HashMap构建、扩容以及存放数据源码分析
目录
前言
HashMap是在开发中用的比较多的一个集合，主要是因为HashMap对数据的存放以及读取提供了比较好的性能，并且也提供了比较多的迭代方法。因此，HashMap也慢慢成了面试中常见的一个重点，对于面试者而言，仅仅了解HashMap的常见用法是不够的，也需要对其原理进行一个整体的学习，这样才能应付面试过程中相对困难的题目。
1 介绍
HashMap是基于Map接口的一个实现类，此实现提供了所有可选的map操作，并且允许值为null以及键为null。HashMap大致上与HashTable一致，除了HashMap是不支持同步操作的以及允许存放空数据。需要知道的是，HashMap是不保证存放数据的顺序性的。
假定哈希函数将元素正确分散在存储桶中的话，那么HashMap提供了相对恒定的基础操作，如get、put。在此集合上进行迭代所需要的时间，与HashMap存储桶的数量以及大小成比例。因此，如果迭代性能很重要，则不要将初始容量设置过高（或负载因子设置过低），这一点是非常重要的。
HashMap实例的性能会有两个参数对其产生影响：initial capacity以及load factor。两个参数主要说明如下：
- initial capacity：哈希桶的数量，这个参数代表构建HashMap指定的初始容量。
- load factor: 加载因子，衡量散列表在其容量自动增加之前允许多大的容量。
当哈希表中数据的数量超过负载因子与当前容量的乘积时，哈希表将被刷新（内部数据以及结构将被重构建），构建后的新哈希容量将为旧哈希表容量的两倍。
通常，默认负载因子（0.75）在时间和空间成本之间提供了一个很好的折衷方案，较高的值会减少空间的开销，但会增加查找的成本。因此在设置其初始容量时，应该考虑HashMap中预期的条目数以及负载因子，以最大程度地rehash的次数。如果初始容量大于最大条目数除以负载系数，则将不会进行任何hash操作。
2 源码分析
2.1 主要参数
HashMap的默认常量说明如下：
/**
* 默认初始化容量，必须是2的幂次方，这个参数主要是用在new HashMap<>()时，不指定初始容量时使用。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大支持的容量
*/
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;
/**
* 链表转换为红黑树之前，还要判断数组的长度是否大于64，若是，才进行转换。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
基础的Node节点定义如下：
/**
* 基础的节点
*/
static class Node<K,V> implements Map.Entry<K,V> {
/** hash值 */
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; }
/**
* 计算键的hashCode以及值得hashCode, 再进行异或。
*/
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得链表数组，无论我们初始化时是否传参，它在自拓容总是2得次幂。
*/
transient Node<K,V>[] table;
/**
* HashMap实例中得Entry集合
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* HashMap中存储key-value得实例个数
*/
transient int size;
/**
* 在对HashMap进行增删改得时候，都会更新modCount值。此值得作用可以看下java集合得Fast-fail机制。
*/
transient int modCount;
/**
* 要调整大小的下一个值（容量 * 负载因子）
*/
int threshold;
/**
* 加载因子
*/
final float loadFactor;
2.2 构造函数
HashMap的构造函数只要分析如下：
/**
* 使用指定得初始容量以及加载因子构建一个HashMap
*/
public HashMap(int initialCapacity, float loadFactor) {
//如果初始容量小于0，则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始容量大于最大支持得容量（1 << 30），那么就使用最大支持的容量覆盖指定的初始容量
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
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 使用默认初始容量（16）以及默认加载因子创建HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
有关以上的tableSizeFor函数，需要特殊分析。
/**
* 根据容量参数，返回一个2的n次幂的table长度。
*/
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;
}
由于用户在构建HashMap的时候，用户可能输入的容量是是奇数，但HashMap需要保证初始构建的容量必须是2的幂次方，因此这个tableSizeFor就是保证构建的HashMap的初始容量为2的幂次方，那这个方法的作用主要是得到大于输入参数且最近的2的整数次幂的数。如自定义初始容量为3，那么经过这个方法就能获取到容量为4。
这里又引出了一个问题，也就是HashMap为什么让容量一定是2的幂次方？主要是为了加快哈希计算以及减少哈希冲突。
- 加快哈希计算：在HashMap的查询过程中，为了根据key，能够定位到key是存放在哪个槽里面，需要根据hash(key) % n(数组的长度)进行计算。但是由于%计算的性能比较慢，因此Java改用了&来进行替代，为了保证替代的计算方式与原先的保持一致，采用了hash(key) & (n - 1)的计算方式。
- 减少哈希冲突：根据以上得到的计算方式：hash(key) & (n-1),若允许n为奇数， 那经过n-1之后就变成了偶数，那经过&运算后的值也是偶数，这样任何Hash值只会散列到数组的偶数下标位置上，浪费空间并且增加冲突的可能性。如果n为偶数，那么经过n-1之后就变成奇数，再经过&运算后的值，可能是奇数也可能是偶数，这样可以保证散列比较均匀。
2.3 存放数据
put分析
HashMap存放数据主要是调用put方法，其put方法内部是直接调用putVal方法的。
/**
* 指定键值，存放到hashMap中，如果HashMap中已经存在对应的key，这个方法会替换
* 旧值。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash分析
在以上的put方法中，调用了hash(key)方法来计算key的hash值。
/**
* 计算key的hash值，如果key值为空，那么则以0作为hash值。如果key值不为空，
* 那么就将key的hashCode右移16位，也就是将高位右移到16低位，再与原来的hashCode
* 进行异或运算，以此来算出key的hash值。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要经过以上的hash计算，得到一个新的hash值，而不是直接使用key.hashCode()来获取呢？
原因：经过以上2.1节的分析，可以知道根据key的hash值来计算出key的存放索引公式是：h & (n - 1)。当数组的长度较小的时候，n - 1的二进制的高16位全部都是0，这个时候再与hash值进行&操作，那也就只能保留低16位的数据，但不幸的是，大多数key的hashcode的二进制的16位都是相同的，所以h & (n - 1)的运算结果是一致的，这样就存在的hash冲突。
改造：为了减少hash冲突的可能性，对于key的hashCode来说，虽然低16位存在比较多相同的情况，但是他们的高位是不一致的，因此可以将hashCode的高16位右移到低16位(h >>> 16), 再与原hahsCode的低16位进行异或，这样计算出来的hashCode的高位保持不变，低位又混合了高位的数据，这样计算出来的hashCode大概率也是不相同的，降低了hash冲突发生的可能性。
putVal分析
这里特别对putVal方法流程进行说明，它主要处理的是，先根据你需要传入的key，计算key应该存放的在Hash桶的哪个索引上，再判断此索引是否已经存在数据了。Hash桶如果存在数据，那就继续沿着链表进行处理。如果不存在，那么新增处理。
/**
* 实际存放数据到Map中的相关处理。
*
* @param hash 键的hash值
* @param key 键
* @param value 值
* @param onlyIfAbsent 如果为true, 不改变原有的数据
* @param evict 如果为false, 表示table处于创建模式中
* @return 返回存放先前的值。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/*
* tab: 指向当前存放数据的桶
* i: 通过key的hash值以及当前数组的长度运算，求得该key对应存放在数组中得索引
* p: 通过索引i获取存放在数组中的节点
* n: 当前数组的长度
*/
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
* 将tab指向当前数组，并且判断当前的数组是否为空或者当前的数组的长度是否为0（说明HashMap没有存放过数据）
* 若是，那么就对此数组进行初始化，并获取到初始化后数组的长度。
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
* 根据（n-1）& hash的计算公式取得对应的索引并赋值到i，再根据此索引获取对应得节点并赋值到p中,
* 如果节点p为空，那就创建节点，将其存放到数组中。
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/* 进入此模块，说明数组里已经存在对应得节点了，继续往下就是要顺着链表或者树结构找到key对应得值就可以了。
* e: 指向遍历得节点
* k: 指向当前遍历节点的key
*/
Node<K,V> e; K k;
/*
* 判断节点p的hash值是否与key的hash值一致，并且判断p的key与传入的key指向是否一致，或者他们的内容是否一致。
* 若一致，则认为p是本次查找的节点
*/
if (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);
//走到这里，说明P节点要继续沿着链表往下找了
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
/*
* 获取p的节点的下一个节点，赋值到e，并判断e是否未空。
* 如果e为空，说明可以将新增的值插入到p的下一个节点了。
*/
if ((e = p.next) == null) {
//根据传入的key， value以及key的hash值创建节点，将p的下一个节点指向创建的节点
p.next = newNode(hash, key, value, null);
/*
* binCount:作为本次轮询链表节点的次数，判断此链表包含节点的次数是否>=7（8-1）,若符合，
* 就将链表转换红黑树。
*
* 至于为什么要TREEIFY_THRESHOLD - 1呢，是因为在整个for循环，它是从p的下一个节点开始的，
* 因此这里需要算上头节点p。或者换种写法就明白了，如
* if (binCount + 1 >= TREEIFY_THRESHOLD)
* treeifyBin(tab, hash);
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/**
* 代码运行到这里，说明p的下一个节点有可能是本次查询的节点，因此这里继续判断p的下一个节点
* 的hash,key，key地址是否一致，若一致，则p的下一个节点就是本次查找的节点了。
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//仍然找不到，继续轮询
p = e;
}
}
/*
* e不为空，说明Hahs桶已经存在key-value的映射了。
*/
if (e != null) {
//获取e的value，作为旧值
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;
}
resize分析
resize()方法主要是用于hash桶的初始化以及扩容处理。
/**
* 初始化或者将数组进行扩容。如果数组为空，就根据初始容量以及目标的阈值进行分配。
* 因此，由于我们对原来的数组进行了两倍的拓展，那原来的节点可能会移动到与原来数组
* 的索引一致，也可能是原来数组的索引+原来数组的容量，作为新索引位置存放。
*/
final Node<K,V>[] resize() {
//声明oldTab变量，表示拓展前的数组，并指向当前的数组
Node<K,V>[] oldTab = table;
//判断老的数组是否为空，若为空，那么就认为老的容量为0，否则获取老数组的长度作为容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取当前的阈值作为老的阈值
int oldThr = threshold;
//声明新的容量以及阈值
int newCap, newThr = 0;
/*
* 判断旧的数组容量是否大于0。
* 这个判断内的处理，主要就是对oldCap或者oldThr进行翻倍处理。
*/
if (oldCap > 0) {
//如果oldCap超过了最大容量，那就没必要扩容了，直接使用限制的最大容量返回即可。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
* 将oldCap<<1, 也就是oldCap * 2，赋值到newCap作为本次需要拓展的新容量。
* 但经过oldCap * 2之后，newCap的值可能达到了最大限制的容量，或者oldCap的值仍然小于16，
* 那这里就不能简单的对oldThr进行右移处理了。
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//运行到这里，说明oldCap的值为0，但是oldThr的不为0，那就使用oldThr来初始化newCap
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//运行到这里，说明oldCap为0， oldThr也为0
else { // zero initial threshold signifies using defaults
//使用默认的初始容量作为新容量（newCap）
newCap = DEFAULT_INITIAL_CAPACITY;
//新的阈值=默认加载因子 * 默认初始容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*
* 运行到这里，存在以下两种情况：
* 1）(oldCap * 2) < MAXIMUM_CAPACITY & oldCap >= DEFAULT_INITIAL_CAPACITY
* 2）oldCap == 0 && oldThr > 0:
* 符合这两种情况的话，newThr的值都为0
*/
if (newThr == 0) {
//新的数组容量 * 加载因子来计算阈值
float ft = (float)newCap * loadFactor;
//判断新的数组容量（newCap）以及计算出来的阈值 是否小于限制最大值，如果是，则使用计算出来的阈值，否则，使用Interger的最大值作为阈值
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) {
//声明变量e, 以缓存当前遍历的节点
Node<K,V> e;
//获取当前遍历的节点，e指向它。
if ((e = oldTab[j]) != null) {
//将原存放旧数组的节点置空，表示此节点已被迁移了，方便Gc进行处理
oldTab[j] = null;
//如果e的下一个节点为空，说明e只是单纯的一个节点，并非链表以及红黑树，直接计算出e该存放的索引，存放进去即可。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果节点e是否红黑树节点,说明e是一个根节点，并且也存在子节点，那就要将红黑树进行拆分后再迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//loHead、loTail代表低位头节点以及低位尾节点, 用于存放那些迁移到新数组后，节点存放的索引仍然不变的节点
Node<K,V> loHead = null, loTail = null;
//hiHead, hiTail代表高位头节点以及地位尾节点，用于存放那些迁移到新数组后，节点存放的索引变更的节点
Node<K,V> hiHead = null, hiTail = null;
//next记录遍历过程中的下一个节点
Node<K,V> next;
do {
//获取e的下一个节点
next = e.next;
//判断哪些节点该迁移到新数组后的索引位置是否与原数组一样
//这里说明这些节点需要迁移到新数组后的索引位置与旧数组的位置是一致的
if ((e.hash & oldCap) == 0) {
//如果尾节点为空，那么就使用，那么认为e节点既是头节点，又是尾节点
if (loTail == null)
loHead = e;
else
//如果尾节点不为空，那么就继续将e节点在尾节点后连接上
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;
}
关于以上判断节点应迁移到新数组后的哪个索引上，主要是靠e.hash & oldCap这个算法来进行确认的。有关这个算法的说明，可以参考https://blog.csdn.net/u010425839/article/details/106620440/。
treeifyBin分析
在以上putVal方法中，如果链表的个数超过了8个之后，那么就会触发由链表转换为红黑树，转换的处理是在treeifyBin中实现的。
/**
* 根据参数的阈值范围，决定是否将链表转化为红黑树。
* 首先将单链表转换为双链表，再调用treeify以头节点为根节点，构建红黑树。
*
* @params tab 元素数组
* @params hash 要增加的键值对的hash值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果数组为空，或者数组的长度小于6，那么就直接扩容处理就可以了，不需要再转换为红黑树了
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//运行到这里，说明数组的长度是超过6的，并且根据hash计算出其所在数组的索引上的节点不为空
else if ((e = tab[index = (n - 1) & hash]) != null) {
//定义首、尾节点
TreeNode<K,V> hd = null, tl = null;
//以e节点开始进行遍历，逐个将遍历到的节点转换为树节点
do {
//将节点转换为树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果尾节点尚未空，这里就将hd指向p，作为头节点
if (tl == null)
hd = p;
//尾节点不为空，则将当前树节点的前一个节点指向尾节点,同时将尾节点的下一个节点指向当前节点.这里实际是将单向链表转换为双向链表
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
/*
* 到目前为止，也只是把Node对象转换成TreeNode对象，把单向链表转换成了双向链表，因此这里将转换后的双向链表替换原来位置
* 上的单向链表，替换后再进行红黑树的构建
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
3 总结
这一章主要是分析HashMap构建、扩容（resize）、存放数据（putVal）的原理，以及简单分析中间中相关解决hash冲突的算法。这一模块暂时不涉及红黑树的相关源码分析，红黑树相关的源码分析将会另起一篇博客进行记录。
本文地址：https://blog.csdn.net/JLoveforever/article/details/109560540