回答
HashMap
实现 Map 接口,底层是基于哈希表实现的,是以 key-value 键值对的形式存在。
哈希表是一个数组和链表结合的数据结构,数组用于快速访问,链表用于解决哈希冲突(链地址法),但这是 jdk 1.8 之前的。
在 JDK1.8 之后,当链表长度大于阈值(默认 8)并且当前数组的长度大于 64 时,链表会转换为红黑树,这样做的目的是提高查询效率。
详解
HashMap 的底层数据结构如下:
- table 数组:
HashMap
的核心是一个动态数组,每个数组的位置称为“桶”(Bucket)。每个桶负责存储键值对(Node)。 - 链表:当不同的 key 通过哈希函数得到相同的数组索引时,会发生哈希冲突。
HashMap
通过链表将冲突的键值对连接起来,每个桶的头节点存储在数组的对应位置。 - 红黑树:从 Java 8 开始,为了优化在高哈希冲突下的性能,提高查询性能,当链表长度超过一定阈值(默认为 8)时,链表会转换为红黑树。
- Node:每个节点都是一个 Node,Node 除了包含必须得 key-value 外,还有下一个** **Node 的引用 next以及 hash 值。
更多阅读<<<