@[TOC](HashMap工作原理全揭秘 — 核心源码解析)

知识盲点

image.png

概念介绍

HashMap是基于Map接口构建的数据结构，它以键值对的形式存储元素，允许键和值都为null。由于键的唯一性，HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。

注意，HashMap并不是线程安全的。在多线程环境下，如果不进行适当的同步处理，可能会导致数据不一致或其他并发问题。因此，对于需要高并发访问的场景，建议使用线程安全的替代方案，如ConcurrentHashMap。

数据结构

在HashMap的数据结构中，数组和链表是核心组件，但它们在实现上有着根本性的差异。

• 数组是静态的，一旦创建，其大小就无法改变
  • 数组由于其固定的大小，对于大量数据的处理可能会遇到性能瓶颈。
• 链表是动态的，可以根据需要随时添加或删除节点。
  • 链表则可以灵活地扩展，更好地应对数据增长的需求，链表在内存使用上可能更加碎片化，因为需要为新节点分配空间并在不再需要时进行回收。

数组

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O(N）。链表的特点是：寻址困难，插入和删除容易。

数组VS链表

• 数组的特点：查询效率高，插入和删除效率低
• 链表的特点：查询效率低，插入和删除效率高

哈希表

综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？这就是我们要提起的哈希表。哈希表既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

非同步和允许使用null之外，HashMap类与Hashtable大致相同。此类不保证映射的顺序，特别是它不保证该顺序恒久不变发生扩容时，元素位置会重新分配。

不同JVM版本HashMap的展现形式

JDK8之后的版本，HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题（循环死锁问题），使的查询和插入，删除的效率都很高。

image.png

HashMap的散列表是懒加载机制，在第一次put的时候才会创建hash表

HashMap VS HashTable

在多线程环境中，HashMap由于其非线程安全的特性，性能可能更高。相比之下，Hashtable通过在实现方法中添加synchronized关键字确保线程安全，因此在性能上可能稍逊一筹。

如果没有特殊需求，建议在常规使用中选择HashMap，多线程环境下，如果需要线程安全的集合，可以使用Collections.synchronizedMap()方法将HashMap转换为线程安全的集合

特性区别对比

image.png

• 是否允许键为空：值得一提的是，HashMap允许键为null，而Hashtable的键则不可为null。

• 继承结构的不同 ：HashMap是对Map接口的直接实现，而Hashtable不仅实现了Map接口，还继承了Dictionary抽象类。

image.png image.png

• 扩充数据量不同 ：关于初始容量和扩容策略，HashMap的初始容量为16，而Hashtable的初始容量为11。两者的填充因子默认都是0.75。当需要扩容时，HashMap的容量会翻倍，即capacity * 2； 而Hashtable的容量会在原有基础上增加1，即capacity * 2 + 1。

• 数据安全的问题 ：在单线程环境下或对性能要求较高的场景中，HashMap可能是一个更好的选择。而在多线程环境中，如果需要确保线程安全，则应考虑使用Hashtable或通过Collections.synchronizedMap()方法将HashMap转换为线程安全的集合。

hashcode

在HashMap中，当我们要存储一个键值对时，首先会调用对象的hashCode()方法来获取哈希码。这个哈希码的主要目的是为了确定对象在哈希表中的位置。

为了得到一个更均匀的分布，提高查找效率，hashCode()返回的整数会经过一系列的位操作（如右移和异或）来进一步处理。这些操作的主要目的是为了打乱哈希码的高位和低位，使得不同的键产生的哈希码有更好的随机性，从而减少冲突的可能性。

hashCode的作用

hashCode的存在主要是为了查找的快捷性, hashCode是用来在散列存储结构中确定对象的存储地址的 (用hashcode来代表对象在hash表中的位置) 。

hashCode存在的重要的原因之一就是在HashMap（HashSet其实就是HashMap）中使用（其实Object类的hashCode方法注释已经说明了）。

HashMap之所以速度快，因为他使用的是散列表，根据key的hashcode值生成数组下标（通过内存地址直接查找，不需要判断，但是需要多出很多内存，相当于以空间换时间）

equals方法和hashcode的关系

若重写了equals(Object obj)方法，则有必要重写hashCode()方法

image.png

• 若两个对象equals(Object obj)返回true，则hashCode()有必要也返回相同的int数
• 若两个对象equals(Object obj)返回false，则hashCode()不一定返回不同的int数
• 若两个对象hashCode()返回相同int数，则equals(Object obj)不一定返回true
• 若两个对象hashCode()返回不同int数，则equals(Object obj)一定返回false

同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题。

key为null怎么办

key为null的时候，只会放在hashMap的0位置（即key的hashCode为0，对数组长度取余后的下标也是0），不会有链表在HashMap源码中对put方法对null做了处理。

1. key为null的判断后进入putForNullKey(V value)这个方法，里面for循环是在table[0]链表中查找key为null的元素。

2. 如果找到，则将value重新赋值给这个元素的value，并返回原来的value。如果没找到则将这个元素添加到table[0]链表的表头。

执行步骤

• 计算原始哈希码：调用对象的hashCode()方法来获取一个原始的哈希码。
• 计算哈希表索引：对原始哈希码进行位操作（如右移和异或），与Bucket大小进行取模，得到一个最终的哈希表索引。这个索引用于确定对象在哈希表中的位置。

---

核心参数

HashMap的实例有两个参数影响其性能：初始容量和加载因子。

• 容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。
• 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。

迭代collection视图所需的时间与HashMap实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

容量探讨

HashMap的最小树形化容量，这个值的意义是：位桶（bin）处的数据要采用红黑树结构进行存储时，整个Table的最小容量（存储方式由链表转成红黑树的容量的最小阈值）当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于4 * TREEIFY_THRESHOLD(16)

如果很多映射关系要存储在HashMap实例中，则相对于按需执行自动的rehash操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

负载因子探讨

加载因子是用于控制哈希表中元素数量与内部数组大小之间关系的参数。

加载因子过高

加载因子越高，哈希表中的元素数量可以更多，但同时可能导致更多的冲突，从而增加查询成本。

加载因子与空间开销

当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数，通常，默认加载因子(0.75)在时间和空间成本上寻求一种折衷。

当加载因子设置得较高时，哈希表中的元素数量可以更多，从而减少了当内部数组需要扩容时所浪费的空间。这似乎是节省了空间，但实际上，这也意味着更高的冲突可能性。

查询成本与加载因子

当哈希表中的元素数量增加时，发生冲突的可能性也增加。这意味着查找特定键的时间会增加，因为可能需要遍历更长的链表（或红黑树，如果链表长度过长）。因此，高的加载因子会增加查询成本。

减少扩容次数和成本

设置初始容量与加载因子

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，如果初始容量大于最大条目数除以加载因子，则不会发生rehash操作。

• 减少扩容的次数：如果你预计哈希表将包含大量元素，那么选择一个较大的初始容量可能是一个好主意。

• 较大的初始容量：如果初始容量大于（最大条目数除以加载因子），那么不会发生rehash操作。这意味着，为了减少rehash次数，你可能需要选择一个较大的初始容量。

总结

加载因子是一个权衡参数。高的加载因子可以减少空间浪费，但可能会增加查询成本和rehash操作的次数。