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

android linkedhashmap实现原理 -回复

Android LinkedHashMap实现原理

LinkedHashMap是Java中的一种数据结构，它继承自HashMap，并在

HashMap的基础上通过使用双向链表来维护插入顺序或访问顺序。在

Android开发中，LinkedHashMap经常被用来作为缓存的数据结构。本

文将逐步解析Android LinkedHashMap的实现原理。

1. HashMap的实现原理

在讨论LinkedHashMap之前，我们需要先了解一下HashMap的实现原

理。HashMap是基于数组和链表来实现的。其内部维护了一个数组，数

组中的每一个元素又是一个链表的头结点，每一个链表都是一个键值对的

集合，其中键值对的键是通过哈希函数计算得到的。通过将键哈希后取模

得到对应的数组下标，然后将键值对存储在对应下标的链表中。

2. LinkedHashMap的特性

LinkedHashMap是通过继承HashMap来实现的，并添加了对插入顺序

或访问顺序的支持。插入顺序是指元素按照插入的先后顺序排序，而访问

顺序是指元素按照最近访问的顺序排序。

3. LinkedHashMap的内部结构

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

插入顺序或访问顺序。该链表的节点是Entry对象，Entry类继承自

HashMap中的Node类，并添加了两个指针prev和next分别指向前一

个节点和后一个节点。

4. 插入顺序的实现原理

在LinkedHashMap中，通过构造函数中的accessOrder参数可以决定

是按照插入顺序还是访问顺序排序，其默认值为false，表示按照插入顺序

排序。当accessOrder为true时，表示按照访问顺序排序。

在插入元素时，LinkedHashMap会在维护HashMap的基础上维护一个

双向循环链表。每次插入新节点时，会将该节点插入到链表的尾部。同时，

LinkedHashMap会更新HashMap中的存储位置，即修改Node类中的

before和after指针。这样可以保证双向链表的尾结点即为最新插入的节

点，从而实现了按照插入顺序排序。

5. 访问顺序的实现原理

在访问元素时，LinkedHashMap会根据访问顺序重新调整节点在双向链

表中的位置。每次访问一个节点时，会将该节点从原来的位置移动到链表

的尾部。这样可以保证链表的尾结点即为最近访问的节点，从而实现了按

照访问顺序排序。

为了实现访问顺序排序，LinkedHashMap会重写HashMap中的get方

法和put方法。在get方法中，会调用afterNodeAccess方法，该方法

会将访问的节点移动到链表的尾部。而在put方法中，会调用

afterNodeInsertion方法，该方法会将新插入的节点移动到链表的尾部。

6. LinkedHashMap的遍历顺序

LinkedHashMap的遍历顺序可以根据构造函数中的accessOrder参数来

决定，当accessOrder为false时，遍历顺序是按照插入顺序；当

accessOrder为true时，遍历顺序是按照访问顺序。

在遍历LinkedHashMap时，可以通过重写HashMap中的迭代器实现。

LinkedHashMap在迭代器中通过访问头结点来遍历整个链表，从而实现

了按照插入顺序或访问顺序的遍历。

总结：

LinkedHashMap是通过继承HashMap并通过双向链表来实现插入顺序

或访问顺序排序的。它在插入和访问元素时，通过调整双向链表中节点的

位置来实现排序。此外，通过重写HashMap的迭代器实现了按照插入顺

序或访问顺序的遍历。