从JDK7与JDK8对比详细分析HashMap的原理与优化
概述
从本文你可以学习到：
- 在什么情况下会应用HashMap？它有哪些特性？
- HashMap的工作原理是什么？
- get和put的工作原理是什么？equals()和hashCode()各自承担什么功能？
- hash的工作方式是什么？这种设计背后的逻辑是什么？
- 当HashMap的规模超过设定负载因子时该怎么办？
- 采用2的n次方形式作为容量的原因是什么？
在阐述这些问题时
需要注意的是，在某些情况下（如与官方开发平台上的JDK版本存在差异），源码可能会稍有不同；其中遵循《码出高效》这一指导原则（即为了解释某个函数功能而做出的调整），旨在清晰地阐述该函数的作用机制；以便于更好地理解其运行原理；由于平台不支持上传bmp格式的图片文件，请访问我的个人博客（https://allenmistake.github.io/2019/05/13/hashmap/）以获取更为优化的排版布局，并查看详细的图片展示信息
两个重要参数说起
在HashMap中涉及两个关键属性：一个是容量（Capacity），另一个是负载因子（Load factor）。这两个属性对于理解HashMap的工作机制至关重要。
Capacity 即为桶的容量，在哈希表中被定义为存储键的数量上限。负载因子则衡量了桶的最大填充程度。为了优化迭代性能，在设置相关参数时需权衡利弊：切勿将容量设置过大或负载因子设定过低会导致系统资源浪费或性能瓶颈等问题。具体而言，在条目数量达到当前容量乘以负载因子时，则需将桶的容量翻倍以避免溢出风险。
put函数的实现
put函数大致的思路为：
- 将 key 的 hashCode() 值用于计算索引。
- 若无冲突，则直接存于 bucket 中。
- 若发生冲突，则以链表形式存放在 bucket 后面。
- 当冲突导致 chain 长度超过或等于 TREEIFY_THRESHOLD 时，则将其转换为红黑树结构。
- 若有已存在的节点，则替换其 old value（确保 key 的唯一性）。
- 若 bucket 已满（超出 load factor × current capacity），则需 resize。
具体代码的实现如下：
JDK7 的 put
public V put(K key, V value) {
int hash = hash(key);
int i = indexFor(hash, table.length);
//此循环通过 hashCode 返回值找到对应的数组下标位置
//如果 equals 结果为真，则覆盖原值， 如果都为 false ，则添加元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key的 hash 是相同的，那么在进行如下判断
//key 是同一个对象或者 equals 返回为真， 则覆盖原来的Value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果元素的个数达到 threshold 的扩容阈值且数组下标位置已经存在元素，则进行扩容
if ((size++ >= threshold) && (null != table[bucketIndex])){
//扩容 2 倍， size 是实际存放元素的个数，而 length 是数组的容量大小(capacity)
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//插入元素时， 应该插入在头部， 而不是尾部
void createEntry(int hash. K key, V value, int bucketIndex){
//不管原来的数组对应的下标是否为 null ，都作为 Entry 的 BucketIndex 的 next值
Entry<K,V> e = table[bucketIndex]; （***）
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}
AI写代码关于并发的问题 ：
如下所示源码，在createEntry()方法中，将新元素分配至槽池中（此处采用哈希链表而非哈希槽）。这种设计使得新元素在下一次获取时能够更快定位到目标对象。
当两个线程同时进入该方法执行（即(***)处），当前操作会被后续操作覆盖（即当前操作被后续操作覆盖），从而导致目标对象可能丢失（即对象丢失的原因之一）。
为了优化这一场景，建议通过构建一个HashMap集合，并观察其在达到容量后自动扩容时的工作机制（即探究resize()方法的数据迁移机制）。
示例代码及详细图解可参考《码出高效》P204页内容。
JDK8 的 put
public V put(K key, V value) {
// 对key的hashCode()做hash
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;
// tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算index，并对null做处理，这里观察到 index 的计算 i = (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;
// 这个位置有节点，且与新节点相同，进行覆盖
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 这个位置有节点，且节点类型为 TreeNode
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // 检测是否该从链表变成树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
AI写代码可以看出这种机制是先执行size++操作后再进行判断如果数值超过预先设定的阈值从而导致系统会自动触发内存扩展操作以避免超出预设容量限制最终将新节点存储到指定的数据表中相比之下JDK 8采取了不同的策略它会将新节点直接加入内存池中并在内存池中加入新节点后计算其占用大小如果此时占用大小超过了当前内存池的最大容量就会触发内存扩展操作以满足新增数据存储的需求
hash 与 hashCode()
在获取和插入操作中，在计算索引时（如图所示），首先对对象的hashCode属性执行哈希运算得到结果值；接着使用该结果值作为参数继续参与后续的索引计算过程。
关于哈希函数与哈希码之间的关系而言，在此背景下为了解决潜在的冲突问题,JDK7版本采用了四次调整机制,而到了JDK8版本则对该操作进行了优化,仅对高位和低位进行了异或处理,其核心理念都是通过提高各比特位的相关性来降低冲突的可能性
JDK7 中的 hash
final int hash(Object k) {
int h = hashSeed;
//如果key是字符串类型，就使用stringHash32来生成hash值
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//一次散列
h ^= k.hashCode();
//二次散列
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
AI写代码JDK8 中的 hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
AI写代码扩容（超级重要！）
JDK7 的扩容分析
void resize(int newCapacity) {
//创建一个扩容后的新数组
Entry[] newTable = new Entry[newCapacity];
//将当前数组中的键值对存入新数组
//JDK8 移除 hashSeed 计算， 因为计算时会用到 Random.nextInt(), 存在性能问题
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//用新数组替换旧数组
table = newTable;
//注意，MAX时1<<30， 如果1<<31 则成 Integer 的最小值：-2147483648
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
//外部传入参数时，指定新表大小为：2*oldTable.length
int newCapacity = newTable.length;
//遍历现有数组中的每一个单链表的头entry
for (Entry<K,V> e : table) {
//如果此 slot 上存在元素，则进行遍历， 直到 e==null，退出循环
while(null != e) {
Entry<K,V> next = e.next;
//当前元素总是直接放在数组下标的 slot 上，而不是放在链表最后
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//根据新的数组长度，重新计算此entry所在下标i
int i = indexFor(e.hash, newCapacity);
//把原来slot上的元素作为元素的下一个
e.next = newTable[i];
//新迁移过来的节点直接放置在 slot 位置上
newTable[i] = e;
//继续向下遍历
e = next;
}
}
}
AI写代码涉及并发机制的问题：
一旦完成 resize 操作，则当 table 被替换成新的表格（newTable）后，则后续的所有元素可以在新的表格上进行插入操作。然而，在这种情况下存在潜在的风险：如果多个线程同时完成了 resize 操作，并且每个线程都在创建一个新的 Entry 对象（newEntry），这些对象仅存在于各自的运行环境中（即不可见于其他 thread）。然而，在迁移完成后（即其中一个 resize 线程完成），该 resize 线程将更新 table 线程所使用的共享变量，并覆盖其他所有正在执行的操作。因此，在使用 HashMap 处理高并发场景时，请注意新增对象可能导致的数据丢失问题：
- 并发赋值时可能导致覆盖。
- 在已遍历的区间中新增元素会导致数据丢失。
- “新表将被覆盖”。
- 迁移过程中发生迁移丢失现象；当存在并发操作时, next字段会被提前设置为null。
JDK8 的扩容分析
例如我们从 16 扩展为 32 时，具体的变化如下所示：
该元素在重新计算哈希值后，在n增加至原来的两倍的情况下，n-1的mask范围在高位增加了1位（红色），从而会导致索引的变化情况如下
因此，在扩展HashMap的过程中，并无需重新计算哈希值；只需关注原有哈希值所新增的那个比特位是否为1或0即可：若为0，则不会影响索引；若为1，则新的索引值将变为"原有索引+oldCap"。参考下图所示的是16扩展至32倍的内存分配缩放示意图：
这个设计无疑极为巧妙：它不仅成功地避免了重新计算哈希值所需的时间开销，并且通过将新增的一位二进制位取值为0或1的概率视为随机事件，在重新分配冲突节点的过程中实现了精确均匀的分布至新创建的桶中。
final Node<K,V>[] resize() {
//oldTab 为当前表的哈希桶
Node<K,V>[] oldTab = table;
//当前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length
//当前的阈值
int oldThr = threshold;
//初始化新的容量和阈值为0
int newCap, newThr = 0;
//如果当前容量大于0
if (oldCap > 0) {
//超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧的容量大于等于默认初始容量16,那么新的阈值也等于旧的阈值的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//那么新表的容量就等于旧的阈值
else {// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//此时新表的容量为默认的容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值为默认容量16 * 默认加载因子0.75f = 12
}
if (newThr == 0) {//如果新的阈值是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) {
//把每个 bucket 都移动到新的 buckets 中
for (int j = 0; j < oldCap; ++j) {
//取出当前的节点 e
Node<K,V> e;
//如果当前桶中有元素,则将链表赋值给e
if ((e = oldTab[j]) != null) {
//将原哈希桶置空以便GC
oldTab[j] = null;
//如果当前链表中就一个元素，（没有发生哈希碰撞）
if (e.next == null)
//直接将这个元素放置在新的哈希桶里。
//注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
else { // preserve order
//因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量
//低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
//高位链表的头节点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//临时节点 存放e的下一个节点
do {
next = e.next;
//这里又是一个利用位运算 代替常规运算的高效点： 利用哈希值 与 旧的容量，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位
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);
//将低位链表存放在原index处，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
AI写代码此段代码源自博客，经过一些删减和修改。注释过多影响阅读体验。
JDK 7 与 JDK 8 中关于HashMap的对比
JDK 8 实现了红黑树、链表和数组等多种数据结构形式，在桶内元素数量超过一定数量时会自动转换成树结构。
为了提高效率和性能,jdk-8 对哈希值的计算方式进行优化和简化。
在jdk-1.7版本中,表在初始化时会预先分配空间;而在jdk-1.8版本中,哈希冲突发生时才进行空间分配;如果当前表为空,则会重新为表进行初始化并分配空间。
在线性探测冲突解决策略下(编号:7),新键插入时采用头插法;而在拉链冲突解决策略下(编号:8),新键插入时采用尾插法。
在再 sizing操作过程中,旧容量存在的条件下需重新计算索引位置;否则(即旧容量不存在的情况下),哈希表会采用"旧容量"+"索引位置"的方式替代原来的索引值进行处理。
总结
我们现在可以回答开始的几个问题，加深对HashMap的理解：
在哪些情况下会使用HashMap？它有哪些特性？
基于Map接口实现了功能，在存储键值对时允许存储null类型的键和值，并且是非同步设计。其数据结构包含Entry类（包含hash、key、value以及next指针）的对象结构。
你知道HashMap的工作原理吗？
你了解 HashMap 的工作原理吗？ HashMap 是一种基于哈希算法实现的一种特殊字典数据结构。当我们向 HashMap 中插入键值对时, 系统会通过调用 hashCode() 方法计算哈希值以确定存储位置, 进而将其存储于对应的桶中。根据当前桶的占用情况自动调整容量（当超出负载阈限时将容量加倍）。当我们在 HashMap 中获取某个键值对时, 系统会再次计算该键的哈希值以确定对应的桶, 并通过 equals() 方法来验证键是否匹配。值得注意的是, 当两个不同的键具有相同的哈希值时（即发生哈希冲突）, 这些冲突元素会被组织成一个链表结构。而在 Java 8 及以上版本中，默认情况下如果一个桶中的冲突元素数量超过 8（这一限制可以在配置文件中进行修改）, 则会切换为使用红黑树来代替链表结构以提高查询效率。
- 你是否了解get和put的工作原理？它们分别起什么作用呢？
在实现时,我们首先对key执行hashCode()运算,并根据公式计算索引位置:((n-1) & hash),以确定存储的位置.当发生冲突时,则会调用key.equals()方法,在链表或树结构中继续搜索以找到对应的节点.
你了解Java中hashCode()函数的具体实现吗？这种设计背后的原理是什么？自Java语言发布版本J2SE 7开始，默认采用了一种更为高效的设计方案：自定义一个整数变量h并对其进行赋值h = (k.hashCode() ^ ((h >> >16)))；这一设计主要基于以下三个方面的考量：其一是在提升哈希表性能方面具有显著优势；其二是通过混合高位与低位信息可以有效降低潜在冲突的可能性；其三是操作过程中避免造成不必要的性能损失
当HashMap的实际大小达到或超过其负载因子（loadFactor）设定的最大容量时，则会进行一次resize操作，将现有长度翻倍后创建一个新的HashMap，并重新计算所有键值对的哈希码。
为何容量 capcity 设计为2的幂？在计算索引时采用的方法是 (n-1) & hash 的方式，在这种情况下能够确保 n-1 的二进制表示全部由 1 组成。如果 n-1 的二进制表示并非全部由 1 组成，则会存在至少一个二进制位上值为零的情况。这种情况下可能会导致两个原本具有不同 hash 值的对象被分配到同一个桶中出现冲突现象发生。因此必须选择 capcity 作为2的幂才能避免这种情况的发生
更多数据结构
请访问我的博客-数据结构分类