HashMap 是 Java 中一种基于哈希表实现的键值对（key-value）集合，其底层实现原理涉及数组、链表和红黑树等数据结构，以下是：
1. 基本结构
HashMap 底层主要由数组、链表和红黑树组成。在 Java 8 及以后版本中，当链表长度超过一定阈值（默认为 8）时，链表会转换为红黑树，以提高查询效率。
2. 哈希算法
- 哈希函数：HashMap 使用键的
hashCode()方法来计算哈希值，然后通过某种算法将哈希值映射到数组的索引位置。Java 中，HashMap 对哈希值进行扰动运算，以减少哈希冲突。 - 扰动函数：
hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)，这个操作将哈希值的高 16 位和低 16 位进行异或，使得哈希值更加分散，减少冲突。
3. 存储过程
- 计算哈希值：对键调用
hashCode()方法，并通过扰动函数计算最终的哈希值。 - 确定数组索引：使用哈希值与数组长度减 1 进行按位与操作，得到数组索引。
index = hash(key) & (n - 1)，其中n是数组的长度，且n通常为 2 的幂次方，这样可以保证索引的均匀分布。 - 插入元素：
- 如果数组该索引位置为空，则直接创建新的节点（Node）并放入该位置。
- 如果该位置已有节点，则发生哈希冲突，需要处理冲突。
4. 哈希冲突处理
- 链表法：在 Java 8 之前，HashMap 主要使用链表来处理哈希冲突。当多个键的哈希值映射到同一个数组索引时，这些键会被存储在一个链表中。插入元素时，新节点会被添加到链表的头部。
- 红黑树：在 Java 8 及以后版本中，当链表长度超过 8 时，链表会转换为红黑树。红黑树是一种自平衡的二叉搜索树，能够保证在最坏情况下，基本的动态集合操作（如查找、插入和删除）的时间复杂度为 O(log n)，从而提高查询效率。
5. 扩容机制
- 扩容阈值：HashMap 的初始容量和加载因子可以指定，默认初始容量为 16，加载因子为 0.75。当 HashMap 中的元素数量超过容量乘以加载因子时，就会触发扩容。
- 扩容过程：扩容时，会创建一个新的数组，其容量是原数组的两倍。然后，将原数组中的每个元素重新计算哈希值，并放入新数组的相应位置。
6. 代码示例
```java
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
HashMap
map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);
System.out.println(map.get("apple")); // 输出 1
System.out.println(map.get("banana")); // 输出 2
}
}
``
在上述代码中，我们创建了一个 HashMap，并向其中插入了三个键值对。当我们调用get` 方法时，HashMap 会根据键的哈希值找到对应的数组索引，然后在链表或红黑树中查找该键，返回对应的值。
HashMap 的底层实现结合了数组、链表和红黑树，通过哈希算法将键映射到数组的索引位置，使用链表和红黑树处理哈希冲突，并通过扩容机制保证 HashMap 的性能。这种设计使得 HashMap 在大多数情况下能够提供高效的插入、删除和查找操作。
