HashMap详解
-
HashMap概述
HashMap是Java集合框架中的一个类，它实现了Map接口，用于存储键值对。HashMap允许使用null键和null值，并且不保证映射的顺序，特别是它不保证顺序会随时间保持不变。 -
数据结构
HashMap内部使用哈希表来实现键值对的存储。哈希表是一个数组，每个数组元素是一个链表（在Java 8及以后版本中，当链表长度超过一定阈值时，链表会转换为红黑树以提高性能）。哈希表通过哈希函数将键转换为数组索引，从而实现对数据的快速访问。 -
哈希函数与哈希冲突
哈希函数：将键转换为一个整数索引，这个索引用于在哈希表中定位元素。Java中的hashCode()方法用于生成哈希码。
哈希冲突：当两个或多个键具有相同的哈希码时，会发生哈希冲突。HashMap通过链表或红黑树来解决哈希冲突，即所有具有相同哈希码的键值对都存储在同一链表或红黑树中。 -
主要操作
put(K key, V value)：将指定的键值对添加到哈希表中。如果键已存在，则更新其对应的值。
get(Object key)：返回指定键所映射的值，如果此映射不包含该键的映射关系，则返回null。
remove(Object key)：从此映射中移除指定键的映射关系（如果存在）。
containsKey(Object key)：如果此映射包含指定键的映射关系，则返回true。 -
扩容与负载因子
扩容：当哈希表中的元素数量超过数组的容量（容量与负载因子的乘积）时，哈希表会进行扩容，以容纳更多的元素。扩容通常是将数组容量翻倍。
负载因子：负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。较高的负载因子可以减少空间开销，但会增加查找成本（链表或红黑树的长度会增加）。默认的负载因子是0.75。 -
线程安全性
HashMap不是线程安全的。如果多个线程同时修改HashMap，可能会导致数据不一致或其他不可预测的行为。如果需要线程安全的Map实现，可以考虑使用ConcurrentHashMap。 -
性能特点
查找、插入和删除操作的时间复杂度通常为O(1)，但在哈希冲突严重的情况下，可能会退化为O(n)，其中n是链表的长度或红黑树的大小。
由于哈希表的特性，HashMap通常比基于数组或链表的Map实现具有更好的性能。 -
与其他Map实现的比较
可以简要比较HashMap与其他Map实现（如Hashtable、TreeMap、LinkedHashMap和ConcurrentHashMap）之间的区别和优缺点。
扩容
当HashMap需要扩容时，它会执行一系列步骤来重新分布元素到新的数组中。以下是该过程的详细讲解：
扩容过程的详细步骤：
创建新数组
HashMap首先会创建一个新的数组（通常称为“桶”数组或“table”），其长度是原数组长度的两倍。这个新数组将用来存储重新分布后的键值对。
遍历原数组
接下来，HashMap会遍历原数组中的每个桶。每个桶可能是一个单链表结构，也可能是一个红黑树结构（当链表长度过长时，会转换为红黑树以提高搜索效率）。
重新计算哈希值
对于原数组中的每个非空桶，HashMap会取出其中的每个键值对，并基于键（key）重新计算哈希值。这个哈希值是通过HashMap内部的哈希函数计算得出的，该函数通常会将键的hashCode进行进一步的散列处理，以减少哈希冲突。
取模运算确定新位置
使用新计算的哈希值和新的数组长度进行取模运算（即 newHash % newCapacity），以确定该键值对在新数组中的位置（桶的索引）。这个取模运算是为了确保元素能够均匀地分布在新数组中，从而减少哈希冲突。
重新插入元素
根据上一步计算出的新位置，HashMap会将键值对插入到新数组的相应桶中。如果新桶中已经有其他元素（即哈希冲突），则新插入的键值对会根据其数据结构（链表或红黑树）的规则被添加到合适的位置。
完成扩容
当原数组中的所有键值对都被重新计算并插入到新数组中后，扩容过程就完成了。此时，HashMap会使用新的数组来替代原来的数组，并继续对外提供服务。
注意事项：
性能影响：扩容是一个相对耗时的操作，因为它涉及到大量的数据迁移和重新哈希计算。因此，在实际应用中，最好能够预先估计HashMap的大小，并设置一个合适的初始容量，以减少扩容的次数。
数据一致性：在扩容过程中，HashMap会确保数据的一致性。即使在多线程环境下（尽管HashMap本身不是线程安全的），扩容操作也是原子的，即要么完全成功，要么完全失败，不会出现中间状态。然而，为了避免并发修改导致的问题，最好在扩容期间不要对HashMap进行写操作。
加载因子的影响：加载因子（load factor）是HashMap中一个重要的参数，它决定了何时触发扩容。较低的加载因子会减少哈希冲突的概率，但可能会增加扩容的频率和内存消耗；而较高的加载因子则可能增加哈希冲突和查找时间。因此，在选择加载因子时需要权衡这些因素。
优化数据结构
在JDK 1.8中，HashMap为了提高性能，在数据结构的实现上做了一些优化。当HashMap中的某个桶（bucket）的元素数量过多时，简单的链表结构会导致查询效率降低，因此HashMap会在链表长度达到一定阈值（默认为8）时将链表转换为红黑树，这是一种自平衡的二叉搜索树，可以显著提高搜索效率。
然而，在HashMap进行扩容时，这些复杂的数据结构需要经过特殊的处理。以下是关于链表与红黑树在扩容过程中的拆分与再映射的详细讲解：
链表的处理
拆分链表：
当HashMap扩容时，如果某个桶中存储的是链表结构，HashMap会遍历这个链表，并对链表中的每个节点进行重新哈希和取模运算，以确定它们在新数组中的位置。这个过程中，原链表可能会被拆分成多个部分，每个部分会被映射到新数组的不同桶中。
重新映射：
对于链表中的每个节点，HashMap会根据其键（key）重新计算哈希值，并使用新的数组长度进行取模运算，以确定该节点应该被放入新数组的哪个桶中。这个过程确保了数据在新数组中的均匀分布，从而减少了哈希冲突。
红黑树的处理
转换回链表：
在扩容开始时，如果某个桶中存储的是红黑树结构，HashMap会首先将这个红黑树转换回链表结构。这是因为在扩容过程中，桶的数量会增加，原本在红黑树中的节点可能会分散到更多的桶中，这可能导致每个桶中的节点数量减少，不再满足红黑树的转换条件（即节点数大于等于8）。
拆分与重新映射：
将红黑树转换回链表后，HashMap会按照链表的处理方式进行拆分和重新映射。即遍历链表中的每个节点，重新计算哈希值并进行取模运算，以确定它们在新数组中的位置。
重新构建红黑树：
当所有节点都被重新映射到新数组中后，HashMap会检查每个桶中的节点数量。如果某个桶中的节点数量再次超过了链表转红黑树的阈值（默认为8），并且满足其他转换条件（如桶的容量大于或等于64），则HashMap会将该桶中的链表重新转换为红黑树。
总结
HashMap在扩容过程中对链表和红黑树的处理是为了确保数据在新数组中的均匀分布，并维持较高的查询效率。通过对链表进行拆分和重新映射，以及对红黑树进行转换、拆分、重新映射和可能的重新构建，HashMap能够在扩容后继续保持其高效的数据结构特点。
HashMap与HashSet
HashMap和HashSet在Java集合框架中都是非常重要的数据结构，它们之间有一些相似之处，但也有一些关键的区别。以下是它们之间的关系和主要差异：
相似之处
基于哈希表：HashMap和HashSet内部都使用哈希表（Hash Table）来存储元素。哈希表通过哈希函数将元素映射到数组的某个位置，从而实现高效的插入、删除和查找操作。
不保证顺序：与TreeMap和TreeSet不同，HashMap和HashSet都不保证元素的顺序。它们按照元素的哈希码进行存储，因此元素的顺序是不确定的。
性能特点：由于都使用了哈希表，HashMap和HashSet在插入、删除和查找操作上的时间复杂度通常都接近O(1)。但是，在哈希冲突严重的情况下，性能可能会受到影响。
关键区别
存储结构：
HashMap存储的是键值对（key-value pairs）。每个键都是唯一的，并且映射到一个值。键和值都可以是任何对象。
HashSet只存储对象本身，没有与之关联的键或值。它用于存储不重复的元素集合。
用途：
HashMap通常用于需要存储键值对的情况，如缓存、映射表等。
HashSet通常用于需要快速判断一个元素是否存在于集合中的情况，如去重、交集、并集等。
方法差异：
HashMap提供了与键值对相关的操作，如put(key, value)、get(key)、containsKey(key)等。
HashSet提供了与集合相关的操作，如add(element)、remove(element)、contains(element)等。
内部实现：
虽然HashMap和HashSet都基于哈希表，但它们的内部实现有所不同。例如，HashMap使用链表或红黑树来处理哈希冲突，而HashSet则使用相同的机制来存储元素。
联系
在Java中，HashSet实际上是通过HashMap来实现的。当你向HashSet中添加一个元素时，实际上是在一个内部HashMap中添加一个键值对，其中键是元素本身，值是一个固定的对象（通常是一个特殊的标记对象）。这种实现方式使得HashSet能够利用HashMap的高效哈希表机制来存储元素，并保持不重复的特性。
但是，这种实现细节对于大多数开发者来说是透明的，通常不需要关心。在大多数情况下，我们只需要根据需求选择使用HashMap还是HashSet即可。
Map比较
以下是HashMap与其他几种常见的Map实现（Hashtable、TreeMap、LinkedHashMap和ConcurrentHashMap）之间的简要比较：
- HashMap
- Hashtable
- TreeMap
- LinkedHashMap
- ConcurrentHashMap
总结
每种Map实现都有其特定的用途和优缺点。选择哪种Map实现取决于你的具体需求，如是否需要线程安全、是否需要排序、是否需要保持插入或访问顺序，以及性能要求等。在大多数情况下，HashMap是性能最优的选择，但如果你需要线程安全或有序的映射视图，那么可能需要考虑其他Map实现。