2024年4月3日发(作者：)

linkedhashmap原理

LinkedHashMap原理

LinkedHashMap是Java中的一个数据结构，它继承自HashMap，但是

在HashMap的基础上增加了一个双向链表，用于维护元素的插入顺序

或者访问顺序。在本文中，我们将深入探讨LinkedHashMap的原理和

实现。

一、HashMap的原理

在了解LinkedHashMap之前，我们需要先了解一下HashMap的原理。

HashMap是一种基于哈希表实现的Map接口，它通过将键映射到值的

方式来存储和访问元素。在HashMap中，每个键都会被映射到一个唯

一的哈希值，这个哈希值被用来确定该键在哈希表中的位置。当我们

需要访问一个元素时，HashMap会根据该元素的键计算出它的哈希值，

并在哈希表中查找该键对应的值。

二、LinkedHashMap的原理

LinkedHashMap在HashMap的基础上增加了一个双向链表，用于维护

元素的插入顺序或者访问顺序。在LinkedHashMap中，每个元素都是

一个键值对，其中键是唯一的，值可以重复。当我们向

LinkedHashMap中插入一个元素时，它会被添加到双向链表的尾部。

如果我们需要访问一个元素，LinkedHashMap会根据该元素的键在哈

希表中查找该元素，并将该元素移动到双向链表的尾部。这样，我们

就可以通过双向链表来维护元素的插入顺序或者访问顺序。

三、LinkedHashMap的实现

LinkedHashMap的实现主要分为两个部分：哈希表和双向链表。在哈

希表中，每个元素都是一个Entry对象，它包含了键、值、哈希值和指

向下一个Entry对象的指针。在双向链表中，每个元素都是一个Entry

对象，它包含了键、值、哈希值、指向前一个Entry对象的指针和指向

后一个Entry对象的指针。当我们向LinkedHashMap中插入一个元素时，

它会被添加到哈希表中，并在双向链表的尾部创建一个新的Entry对象。

如果我们需要访问一个元素，LinkedHashMap会根据该元素的键在哈

希表中查找该元素，并将该元素移动到双向链表的尾部。

四、LinkedHashMap的应用

LinkedHashMap在Java中被广泛应用于LRU缓存、LRU页面置换算法

等场景。在LRU缓存中，我们需要维护缓存中元素的访问顺序，当缓

存满了之后，我们需要将最近最少使用的元素从缓存中移除。这个过

程可以通过LinkedHashMap来实现，我们可以将缓存中的元素插入到

LinkedHashMap中，并将访问顺序设置为访问时间的顺序。当缓存满

了之后，我们只需要从LinkedHashMap的头部开始遍历，将最近最少

使用的元素从缓存中移除即可。

总结

LinkedHashMap是Java中的一个数据结构，它继承自HashMap，但是

在HashMap的基础上增加了一个双向链表，用于维护元素的插入顺序

或者访问顺序。在LinkedHashMap中，每个元素都是一个键值对，其

中键是唯一的，值可以重复。LinkedHashMap的实现主要分为两个部

分：哈希表和双向链表。LinkedHashMap在Java中被广泛应用于LRU

缓存、LRU页面置换算法等场景。