说一下HashMap的数据结构

在 Java 8 中，HashMap 的内部实现使用了哈希表和链表结合的方式，称为“链-桶”(separate chaining)方法或“链式哈希”。

具体来说，HashMap 内部维护了一个存储链表的数组，称为“桶数组”。当添加元素时，HashMap 会根据元素的哈希值决定该元素应该放在哪个桶里。如果多个元素的哈希值相同，这些元素就会被放到同一个桶里，并形成一个链表。

为了提高查询效率，Java 8 在 HashMap 中引入了红黑树。当一个桶中的链表长度超过了阈值，默认为 8，且当前 HashMap 的大小大于等于 64(即元素个数大于等于 64 * 0.75 = 48)时，该链表将被转化为红黑树。红黑树节点个数小于 6 转为链表。

• 哈希值计算：HashMap 使用键的哈希码来计算哈希值，以确定在哪个桶中存储元素。
• 存储桶： 哈希值用于确定键-值对在数组的哪个位置（桶）存储。每个桶可以包含多个键-值对。
• 链表和红黑树： 当多个键具有相同的哈希值时，它们被存储在同一个桶中的链表或红黑树中。在 Java 8 中，如果链表长度超过了阈值，且当前 HashMap 的大小大于等于 64，链表会被转化为红黑树以提高性能。