【java】HashMap的实现原理

1. 说明

• 1.HashMap是一个基于哈希表的数据结构，它实现了Map接口。
• 2.HashMap允许使用null键和null值，并且不保证映射的顺序。

2. 哈希函数

• 1.HashMap使用哈希函数来计算键的哈希值。
• 2.在Java中，这通常是通过调用键对象的hashCode()方法来实现的。
• 3.hashCode()方法返回一个int类型的哈希码，HashMap使用这个哈希码来确定键在内部数组（也称为“桶”数组）中的位置。

3. 桶数组

• 1.HashMap内部维护了一个Entry数组（或称为“桶”数组），用于存储键值对。
• 2.每个Entry对象包含一个键、一个值以及指向下一个Entry的引用（用于处理哈希冲突时的链表结构）。

4. 哈希冲突解决

• 1.当两个或多个键的哈希值相同时，它们会映射到桶数组中的同一个位置，这称为哈希冲突。
• 2.HashMap通过链表（在Java 8之前）或链表+红黑树（在Java 8及之后）来解决哈希冲突。
• 3.链表：在Java 8之前，当发生哈希冲突时，新的键值对会被添加到冲突位置上的链表的末尾。
• 4.链表+红黑树：在Java 8及之后，为了优化性能，当链表长度超过一定阈值（默认为8）时，链表会转化为红黑树。
• 5.红黑树是一种自平衡的二叉搜索树，它可以在O(log n)的时间内完成查找、插入和删除操作，这比链表的O(n)时间复杂度要好得多。

5. 动态扩容

• 1.HashMap具有动态扩容的能力。
• 2.当桶数组中的元素数量超过负载因子（默认为0.75）与数组长度的乘积时，HashMap会进行扩容操作。
• 3.扩容操作会将数组的长度扩大为原来的两倍（但数组的大小始终是2的幂次方），并重新计算每个键值对在新数组中的位置，然后将它们移动到新数组中。
• 4.扩容操作是一个相对耗时的过程，因为它需要遍历整个HashMap并重新计算每个键值对的位置。
• 5.通过动态扩容，HashMap可以保持较高的查找、插入和删除效率，避免因为数组过满而导致的性能下降。

6. 查找、插入和删除操作

• 1.查找：根据键的哈希值找到对应的桶，然后遍历桶中的链表或红黑树来找到具体的键值对。
• 2.插入：将键值对封装到Entry对象中，根据键的哈希值找到对应的桶，然后处理哈希冲突（添加到链表末尾或红黑树中）。如果链表长度超过阈值，则进行树化操作。如果元素数量超过阈值，则进行扩容操作。
• 3.删除：根据键的哈希值找到对应的桶，然后遍历桶中的链表或红黑树来找到要删除的键值对，并将其从链表或红黑树中移除。如果删除后链表长度小于树化阈值的一半（默认为4），则可能将红黑树转化为链表。