admin 管理员组

文章数量: 1086019


2024年3月6日发(作者：火狐主页)

linkedhashmap底层实现原理

LinkedHashMap是Java中Map接口的一个实现类，它使用链表和哈希表结合的方式存储key-value对，保证元素的顺序与插入顺序一致。LinkedHashMap的底层实现原理如下：

LinkedHashMap中的数据存储结构是一个哈希表和一个双向链表，哈希表中存放的是结点的哈希值和指向双向链表结点的指针，而双向链表中存放的是key-value对。链表中的结点按照插入顺序排列，即越晚插入的结点越靠近链表尾部。

当执行put操作时，先根据key的哈希值存放到哈希表中。如果该位置没有结点，则直接在链表的尾部插入一个新结点，并将该位置指向该结点的指针指向新结点；如果该位置已经有了结点，那么就需要遍历链表，找到与该key相同的结点。如果找到了，则更新这个结点的value；否则，在链表尾部插入一个新的结点并将哈希表中的指针指向它。

LinkedHashMap中维护了一个boolean类型的accessOrder属性，它表示是按照插入顺序还是访问顺序（即最近访问的元素在链表尾部）来排序。如果accessOrder为true，即按照访问顺序排序，那么当执行get、put和putAll操作时，都会将访问的结点移动到链表的尾部。

这样就可以保证最近访问的结点始终在链表尾部，而链表头部则是最早被访问的结点。

LinkedHashMap的迭代器是由链表支持的，所以按照插入顺序或访问顺序的迭代都是高效的。在访问元素时，根据accessOrder判断是否需要将访问的结点移动到链表尾部。显然，迭代按照访问顺序的效率比按照插入顺序的效率低，因为需要频繁地维护链表的结构。

综上所述，LinkedHashMap的底层实现原理是使用哈希表和链表结合的方式，将key-value对按照插入顺序或访问顺序存储在链表中，达到保持元素顺序一致的效果。


本文标签： 链表 结点 顺序 访问 插入

版权声明：本文标题：linkedhashmap底层实现原理 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1709724985a544303.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。