005 HashMap

本文主要是介绍005 HashMap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- HashMap详解
- 扩容
- - 创建新数组
  - 遍历原数组
  - 重新计算哈希值
  - 取模运算确定新位置
  - 重新插入元素
  - 完成扩容
  - 优化数据结构
- HashMap与HashSet
- Map比较

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中，数组容量指的是其内部用于存储桶（bucket）的数组的大小。每个桶本质上是一个链表的头节点（在Java 8及以后版本中，当链表长度超过阈值时，链表会转换为红黑树）。扩容操作发生在哈希表中的元素数量（键值对的数量）超过当前数组的容量与负载因子（load factor）的乘积时。

数组容量
数组容量是HashMap内部数组的长度，它决定了哈希表能够直接索引的桶的数量。在HashMap的初始化或构造时，你可以指定一个初始容量（initial capacity），它会影响内部数组的大小。如果没有指定初始容量，HashMap会使用一个默认值（通常是16）。

判断数量
哈希表中的元素数量指的是存储在哈希表中的键值对的总数。这个数量并不直接等于数组的长度，因为数组中存储的是桶，而每个桶可能链接着一个或多个键值对（在链表或红黑树中）。要获取哈希表中的元素数量，你可以使用HashMap的size()方法。

扩容机制（JDK 1.8及以后）
在JDK 1.8及以后的版本中，当哈希表中的元素数量超过数组容量与负载因子的乘积时，哈希表会进行扩容。扩容操作通常会将数组容量翻倍（新的容量通常是原容量的两倍，但也可能是一个更大的值，以确保新的容量是2的幂）。

扩容过程中，哈希表会创建一个新的、更大的数组，并将原数组中的所有键值对重新哈希并插入到新数组中。由于哈希码的计算涉及到数组长度（取模运算），因此扩容后需要重新计算每个键值对的索引位置。

在重新哈希和插入的过程中，如果某个桶中的链表长度超过了树化阈值（TREEIFY_THRESHOLD，默认为8），并且数组容量大于或等于64，那么链表会转换为红黑树以提高性能。这是JDK 1.8引入的一个优化措施，用于处理哈希冲突严重时的情况。

总结
数组容量是HashMap内部数组的大小，它决定了哈希表能够直接索引的桶的数量。哈希表中的元素数量指的是存储在哈希表中的键值对的总数。当元素数量超过容量与负载因子的乘积时，哈希表会进行扩容操作，通常是将数组容量翻倍，并重新哈希和插入所有键值对。在JDK 1.8及以后版本中，链表长度超过一定阈值时可能会转换为红黑树以提高性能。

扩容

当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的扩容
HashMap在JDK 1.8中的扩容过程主要包括以下几个步骤：

确定扩容时机：当HashMap中的元素数量超过负载因子（默认0.75）与当前容量的乘积时，就会触发扩容。
创建新数组：创建一个新的数组，其容量是原数组的两倍。
重新分布元素：遍历原数组，将每个元素重新哈希并分布到新数组中。具体过程是根据元素的key重新计算哈希值，并使用新的容量进行取模运算，以确定元素在新数组中的位置。
链表或红黑树的拆分与再映射：如果某个桶中的数据结构是链表或红黑树，在扩容过程中需要进行拆分和再映射。对于链表，会将其拆分为两个链表，并根据新的哈希值将它们重新映射到新数组的不同桶中。对于红黑树，则可能需要先转换回链表，进行拆分和重新映射后，再根据条件判断是否重新转换为红黑树。
为什么要树化？
在JDK 1.8中，HashMap引入了红黑树来优化性能。当哈希冲突严重时，即多个键映射到同一个桶时，如果单纯使用链表存储，那么查询效率会降低到O(n)。而红黑树作为一种自平衡的二叉搜索树，其查询、插入和删除操作的复杂度都是O(log n)，可以显著提高在大规模数据下的查询性能。

什么时候树化？
在JDK 1.8中，HashMap会在以下情况下将链表转换为红黑树：

当链表的长度达到或超过一个特定阈值（默认为8）时。
并且，当前HashMap的桶数组长度大于或等于64。
如果数组长度小于64，HashMap会优先选择扩容来减少链表长度，而不是立即转换为红黑树。

扩容的时候树化吗？
在HashMap扩容过程中，并不会直接进行树化操作。扩容时主要关注的是重新分布元素到新的数组中。如果在扩容后某个桶中的链表长度满足树化条件（链表长度大于等于8且桶数组长度大于或等于64），那么在该桶中的元素被重新插入后，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即可。

当说到HashMap和HashSet的内部实现时，确实它们都使用了哈希表作为基础数据结构，但在处理哈希冲突和存储元素的方式上存在一些差异。不过，说HashSet使用与HashMap相同的机制来“存储元素”可能有些误导，因为它们存储元素的方式实际上是由它们各自的内部设计决定的。

HashMap的内部实现
HashMap内部使用了一个数组来存储桶（bucket），每个桶其实是一个链表的头节点（或者在某些情况下是红黑树的根节点）。当插入一个键值对时，HashMap首先根据键的哈希码计算出应该存储在哪个桶中。如果多个键具有相同的哈希码（即哈希冲突），那么这些键值对会存储在同一个桶对应的链表中。

在Java 8及以后的版本中，为了优化性能，当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为8）时，链表会转换为红黑树。这种转换通常发生在数组容量也足够大（默认为64）的情况下。红黑树的平均查找时间复杂度为O(log n)，比链表的O(n)要好，因此在链表很长时能够提供更好的性能。

HashSet的内部实现
HashSet底层实际上也是基于HashMap实现的。当你向HashSet中添加一个元素时，HashSet内部会维护一个HashMap，其中元素本身作为键，而值则是一个固定的对象（通常是一个特殊的标记对象，如PRESENT）。由于HashSet只关心元素是否存在，而不关心元素与值之间的映射关系，因此这个值对于HashSet来说并不重要。

HashSet利用HashMap的键的唯一性来保证元素的唯一性。当向HashSet添加元素时，实际上是在HashMap中添加一个键值对，其中键是元素本身，值是一个固定的对象。由于HashMap的键必须是唯一的，因此HashSet中的元素也是唯一的。

处理哈希冲突
在处理哈希冲突方面，HashMap和HashSet（通过其内部的HashMap）都使用了相同的机制：链表或红黑树。当两个或多个元素具有相同的哈希码时，它们会被存储在同一个桶对应的链表或红黑树中。

总结
虽然HashMap和HashSet都基于哈希表，并且都使用链表或红黑树来处理哈希冲突，但它们的用途和实现细节是不同的。HashMap用于存储键值对，而HashSet用于存储不重复的元素集合。HashSet内部通过维护一个HashMap来实现元素的存储和唯一性检查。

Map比较

以下是HashMap与其他几种常见的Map实现（Hashtable、TreeMap、LinkedHashMap和ConcurrentHashMap）之间的简要比较：

HashMap

优点：
提供了高效的键值对存储和检索。
允许使用null键和null值。
在大多数情况下性能表现良好。
缺点：
不是线程安全的。
不保证映射的顺序。

Hashtable

区别：
是线程安全的，提供了同步的Map实现。
不允许使用null键和null值。
优点：
线程安全。
缺点：
性能通常比HashMap差，因为同步操作开销较大。
不允许使用null键和null值。

TreeMap

区别：
基于红黑树实现，可以自然排序或定制排序。
保证映射按照键的自然顺序或定制顺序进行排序。
优点：
提供了有序的映射视图。
可以通过自然顺序或Comparator进行排序。
缺点：
在插入、删除和查找操作上的性能通常不如HashMap。
占用更多的内存，因为红黑树结构比哈希表更复杂。

LinkedHashMap

区别：
是HashMap的一个子类，使用双向链表维护元素的插入顺序或访问顺序。
优点：
提供了有序的映射视图，可以保持插入顺序或访问顺序。
仍然保持了HashMap的高效性能。
缺点：
相比HashMap占用更多的内存，因为需要维护双向链表。
不是线程安全的。

ConcurrentHashMap

区别：
是线程安全的Map实现，专为并发设计。
使用了分段锁（在Java 7及之前）或CAS操作（在Java 8及之后）来提供高并发性能。
优点：
线程安全，支持高并发访问。
在并发场景下性能表现良好。
缺点：
可能比HashMap占用更多的内存，因为需要额外的数据结构来支持并发操作。
在非并发场景下可能性能略低于HashMap。

总结
每种Map实现都有其特定的用途和优缺点。选择哪种Map实现取决于你的具体需求，如是否需要线程安全、是否需要排序、是否需要保持插入或访问顺序，以及性能要求等。在大多数情况下，HashMap是性能最优的选择，但如果你需要线程安全或有序的映射视图，那么可能需要考虑其他Map实现。

这篇关于005 HashMap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！