2024-03-14  阅读(43)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://www.skjava.com/mianshi/baodian/detail/4729021383

回答

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 值。

更多阅读<<<

你知道多少种解决 hash 冲突的方法?

ConcurrentHashMap 链表转红黑树为什么是 8

阅读全文
  • 点赞