HashMap 底层原理详解 - 哈希函数、数组和链表/红黑树

HashMap 的底层实现原理主要涉及两个概念：哈希函数和数组+链表/红黑树。

'哈希函数': HashMap 使用哈希函数将键映射到数组的索引位置上。哈希函数可以将任意大小的数据映射到固定大小的值，这个值就是数组的索引。Java 中的 HashMap 使用的是 hashCode() 方法作为哈希函数，它返回一个 int 类型的哈希值。

'数组+链表/红黑树': 在 HashMap 中，每个索引位置上都是一个数组元素，每个数组元素都是一个链表或红黑树的头节点。当发生哈希冲突时，即不同的键映射到了同一个索引位置上，新的键值对会被添加到链表或红黑树中。当链表长度超过一定阈值（默认为 8）时，链表会被转换为红黑树，以提高查询效率。

'put 操作': 当调用 put() 方法向 HashMap 中添加键值对时，首先会根据键的 hashCode() 计算出数组的索引位置，然后将键值对添加到对应位置的链表或红黑树上。如果发生哈希冲突，即键的 hashCode() 相同，HashMap 会遍历链表或红黑树，通过键的 equals() 方法比较键是否相同，如果相同则更新值，如果不同则添加到链表或红黑树的末尾。

'get 操作': 当调用 get() 方法从 HashMap 中获取值时，首先会根据键的 hashCode() 计算出数组的索引位置，然后遍历链表或红黑树，通过键的 equals() 方法找到对应的键值对。

'resize 操作': 当 HashMap 的元素数量超过数组容量的 75% 时，会进行 resize 操作，即扩容。扩容会创建一个新的数组，并将原来数组中的键值对重新哈希到新数组中。这个操作比较耗时，但可以提高 HashMap 的性能，因为扩容后，数组中的链表或红黑树长度会更短，查询效率会更高。

总结起来，HashMap 的底层实现原理是通过哈希函数将键映射到数组的索引位置上，使用链表或红黑树解决哈希冲突，实现高效的键值对存储和查询。