知识盲点

概念介绍

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

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

数据结构

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

• 数组是静态的，一旦创建，其大小就无法改变

• 数组由于其固定的大小，对于大量数据的处理可能会遇到性能瓶颈。

• 链表是动态的，可以根据需要随时添加或删除节点。

• 链表则可以灵活地扩展，更好地应对数据增长的需求，链表在内存使用上可能更加碎片化，因为需要为新节点分配空间并在不再需要时进行回收。

数组

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

链表

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

数组 VS 链表

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

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

哈希表

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

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

不同 JVM 版本 HashMap 的展现形式

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

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

HashMap VS HashTable

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

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

特性区别对比

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

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

• 
• 

• 扩充数据量不同 ：关于初始容量和扩容策略，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()方法

• 若两个对象 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 操作的次数。