爱游戏全站app官网入口-爱游戏官网

hashmap 底层是如何实现的? -爱游戏全站app官网入口

2023-08-10,,

在不同的 jdk 版本下的实现是不同的,在 jdk 1.7 时,hashmap 底层是通过数组 链表实现的;而在 jdk 1.8 时,hashmap 底层是通过数组 链表或红黑树实现的。

具体来说,hashmap 内部维护了一个数组,每个数组元素又是一个链表或者红黑树,每个链表或者红黑树节点存储了一个键值对。当需要存储新的键值对时,hashmap 会根据键的哈希值确定其在数组中的位置,如果该位置已经有了其他键值对,则通过链表或红黑树解决冲突,将新的键值对添加到链表或红黑树的末尾。当链表或红黑树长度达到一定程度后,hashmap 会自动将链表转换为红黑树,以提高查找效率。

如下图所示,hashmap 在 jdk 1.7 中的实现如下图所示:

在 jdk 1.8 时,hashmap 如下图所示:

链表和红黑树互转流程

链表升级为红黑树

在 jdk 1.8 之后,hashmap 默认是先使用数组 链表存储数据,但当满足以下两个条件时:

    链表的数量大于阈值(默认是 8)
    并且数组长度大于 64 时

为了(查询)的性能考虑会将链表升级为红黑树进行存储,具体执行流程如下:

    创建新的红黑树对象,并将链表内所有的键值对全部添加到红黑树中。

    将原来的链表引用指向新创建的红黑树。

红黑树退化为链表

当进行了删除操作,导致红黑树的节点小于等于 6 时,会发生退化,将红黑树转换为链表。这是因为当节点数量较少时,红黑树对性能的提升并不明显,反而占用了更多的内存空间。具体执行流程如下:

    从红黑树的根节点开始,按照中序遍历的顺序将所有节点加入到一个新的链表中。

    将原来的红黑树引用指向新创建的链表。

小结

hashmap 在 jdk 1.7 时,是通过数组 链表实现的,而在 jdk 1.8 时,hashmap 是通过数组 链表或红黑树实现的。在 jdk 1.8 之后,如果链表的数量大于阈值(默认为 8),并且数组长度大于 64 时,为了查询效率会将链表升级为红黑树,但当红黑树的节点小于等于 6 时,为了节省内存空间会将红黑树退化为链表。

本文已收录至《java面试突击》,专注 java 面试 100 年,查看更多:www.javacn.site

hashmap 底层是的?的相关教程结束。

网站地图