在Java中，HashMap 是一个非常重要的集合类，用于存储键值对（Key-Value）。它提供了快速的数据插入、删除和查找功能。本文将深入探讨 HashMap 的底层数据结构，帮助读者更好地理解其工作原理。
一、HashMap的基本概念
HashMap 基于哈希表实现，它存储的内容是键值对（Key-Value），具有很快的查找速度。HashMap 允许空键（null）和空值（null），但最多只能有一个空键。
二、底层数据结构
HashMap 的底层数据结构是一个数组和链表（或红黑树）的组合。这个数组被称为“桶”（bucket），数组中的每个元素都是一个链表（或红黑树）。
数组
HashMap 的核心是一个数组，这个数组的元素类型是 Node[]，其中 Node 是 HashMap 的一个内部类，代表了键值对。数组的每个位置称为一个“桶”，每个桶可以存储一个或多个键值对。链表
当两个或多个键的哈希值相同时，就会发生哈希冲突。在 HashMap 中，哈希冲突是通过链表来解决的。同一个桶中的所有元素都存储在一个链表中。当发生冲突时，新的元素会被添加到链表的头部。红黑树
从Java 8开始，当链表的长度超过一定阈值（默认为8）时，链表会被转换成红黑树。红黑树是一种自平衡的二叉搜索树，它可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。
三、哈希函数
HashMap 使用哈希函数将键的哈希码映射到数组的一个位置上。哈希函数的目的是尽可能均匀地将键分布在哈希表的各个位置上，以减少哈希冲突。
四、哈希冲突的解决方案
链表解决冲突
在Java 8之前，HashMap 完全依赖链表来解决哈希冲突。当链表长度过长时，性能会受到影响。红黑树优化
Java 8引入了红黑树来优化长链表的性能问题。当链表长度超过阈值时，链表会被转换成红黑树。这样可以保证即使在哈希冲突较多的情况下，HashMap 的性能也不会显著下降。
五、扩容机制
HashMap 在初始化时会指定一个容量（默认为16），当元素数量超过容量和加载因子的乘积时，会进行扩容。扩容操作会创建一个新的数组，并将旧数组中的所有元素重新映射到新数组上。这个过程是耗时的，因此合理地初始化 HashMap 的容量可以避免频繁的扩容操作。
六、总结
HashMap 的底层数据结构是一个数组，数组中的每个位置是一个链表或红黑树。这种结构使得 HashMap 在处理哈希冲突时既能够保持高效的查找性能，又能够通过扩容机制适应数据量的增长。了解这些底层原理，有助于我们更好地使用和优化 HashMap。
图解：HashMap的底层数据结构
+----------------+ +----------------+ +----------------+
| | | | | |
| 链表/红黑树 | | 链表/红黑树 | | 链表/红黑树 |
| | | | | |
+----------------+ +----------------+ +----------------+
| | | | | |
| 桶（bucket） |<-->| 桶（bucket） |<-->| 桶（bucket） |
| | | | | |
+----------------+ +----------------+ +----------------+
在这个图中，每个桶可以包含一个链表或红黑树，用于存储具有相同哈希值的键值对。通过这种方式，HashMap 能够有效地处理哈希冲突，并提供快速的数据访问。
