HashMap 实现原理详解：哈希表、链表和红黑树

HashMap 是 Java 中常用的数据结构之一，它基于哈希表（Hash Table）实现。以下是 HashMap 的实现原理详解：

存储结构： HashMap 由一个数组和链表或红黑树（JDK 1.8 之后引入）组成。数组用于存储元素，而链表或红黑树用于解决哈希冲突问题。当多个元素经过哈希函数计算后映射到同一个数组索引位置时，会以链表或红黑树的形式存储在该位置。
哈希函数： HashMap 使用哈希函数将键（Key）映射为数组索引。哈希函数的目标是尽可能均匀地将不同的键映射到不同的数组索引上，以便能够快速定位到对应的元素。通常，哈希函数使用键的 hashCode() 方法计算哈希码，然后再通过位运算对数组长度取模来确定索引位置。
哈希冲突解决： 当多个元素经过哈希函数计算后映射到同一个数组索引位置时，就会发生哈希冲突。HashMap 使用链表或红黑树来解决哈希冲突的问题。在 JDK 1.8 之前，使用的是链表解决冲突，当链表长度超过一定阈值（默认为 8）时，链表会转化为红黑树。在 JDK 1.8 及以后的版本中，如果哈希冲突的元素数量小于一定阈值（默认为 8），则使用链表存储，否则使用红黑树。
添加元素： 当向 HashMap 中添加元素时，它会首先计算键的哈希码，然后根据哈希码找到对应的数组索引。如果该索引位置为空，直接将元素插入；如果不为空，则根据键的 equals() 方法判断是否存在相同的键，如果存在则更新对应的值，否则将元素以链表或红黑树的形式插入到该位置。
查找元素： 当查询 HashMap 中的元素时，首先根据键的哈希码找到对应的数组索引，然后遍历链表或红黑树，通过键的 equals() 方法匹配键，如果找到匹配的键，则返回对应的值。

HashMap 的实现原理简单说就是通过哈希函数将键映射到数组索引上，并使用链表或红黑树解决哈希冲突。这样可以保证在大多数情况下，插入、查找和删除操作的时间复杂度都是常数级别的。