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

linkedhashmap 的实现原理

LinkedHashMap是Java中的一个实现了Map接口的哈希表和双

向链表的数据结构，它继承自HashMap，并且保持键值对的插入

顺序。在LinkedHashMap中，每个元素都包含了对前一个元素和

后一个元素的引用，因此可以按照插入顺序、访问顺序或者自定义

顺序进行迭代。

LinkedHashMap的实现原理主要包括哈希表和双向链表两部分，

下面将分别介绍它们的原理和作用。

1. 哈希表：LinkedHashMap的底层数据结构仍然是一个哈希表，

它使用了和HashMap相同的哈希算法来确定元素在哈希表中的位

置。每个元素的键都会被哈希函数映射到哈希表中的一个桶，每个

桶中存放着一个链表或红黑树的根节点，用于解决哈希冲突。通过

哈希表，LinkedHashMap可以实现快速的键值查找和插入操作。

2. 双向链表：LinkedHashMap在哈希表的基础上，使用一个双向

链表来维护元素的插入顺序。在每个元素插入哈希表时，该元素会

被添加到链表的尾部，以保持插入的顺序。同时，

LinkedHashMap还提供了按访问顺序进行迭代的功能，即当访问

一个元素时，该元素会被移动到链表的尾部，从而实现了LRU（最

近最少使用）的功能。

通过哈希表和双向链表的结合，LinkedHashMap可以在常数时间

内完成插入、删除和查找操作。它的实现原理如下：

1. 初始化LinkedHashMap时，会创建一个指定容量的哈希表和一

个空的双向链表。

2. 当插入一个元素时，首先根据键的哈希值计算出在哈希表中的位

置，如果该位置为空，则将元素插入到该位置，并将该元素添加到

双向链表的尾部。如果该位置已经存在其他元素，则将新插入的元

素添加到链表的尾部，并将该元素添加到哈希表中的冲突链表的末

尾。

3. 当删除一个元素时，首先根据键的哈希值找到在哈希表中的位置，

然后从链表中删除该元素，并更新链表的前后指针。如果该位置在

哈希表中存在其他元素，则需要更新冲突链表的指针。

4. 当访问一个元素时，首先根据键的哈希值找到在哈希表中的位置，

然后将该元素移动到链表的尾部，以保持访问顺序。

LinkedHashMap的实现原理保证了元素的插入顺序和访问顺序可

以被快速地维护和更新。在某些应用场景下，我们可能需要保持元

素的插入顺序或者按照最近访问的顺序进行迭代。例如，当实现一

个缓存时，我们可以使用LinkedHashMap来存储缓存的键值对，

并按照最近访问的顺序来淘汰最不常访问的元素，从而提高缓存的

命中率。

总结一下，LinkedHashMap是一个基于哈希表和双向链表的数据

结构，它使用哈希表来实现快速的键值查找和插入操作，并使用双

向链表来维护元素的插入顺序和访问顺序。通过使用

LinkedHashMap，我们可以方便地实现按插入顺序或者访问顺序

进行迭代的功能。