首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedHashMap(1)

Java 容器源码分析之 LinkedHashMap(1)

同 HashMap 一样,LinkedHashMap 也是对 Map 接口的一种基于链表和哈希表的实现。实际上, LinkedHashMap 是 HashMap 的子类,其扩展了 HashMap 增加了双向链表的实现。相较于 HashMap 的迭代器中混乱的访问顺序,LinkedHashMap 可以提供可以预测的迭代访问,即按照插入序 (insertion-order) 或访问序 (access-order) 来对哈希表中的元素进行迭代。
1
2
3
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
从类声明中可以看到,LinkedHashMap 确实是继承了 HashMap,因而 HashMap 中的一些基本操作,如哈希计算、扩容、查找等,在 LinkedHashMap 中都和父类 HashMap 是一致的。
但是,和 HashMap 有所区别的是,LinkedHashMap 支持按插入序 (insertion-order) 或访问序 (access-order) 来访问其中的元素。所谓插入顺序,就是 Entry 被添加到 Map 中的顺序,更新一个 Key 关联的 Value 并不会对插入顺序造成影响;而访问顺序则是对所有 Entry 按照最近访问 (least-recently) 到最远访问 (most-recently) 进行排序,读写都会影响到访问顺序,但是对迭代器 (entrySet(), keySet(), values()) 的访问不会影响到访问顺序。访问序的特性使得可以很容易通过 LinkedHashMap 来实现一个 LRU(least-recently-used) Cache,后面会给出一个简单的例子。
之所以 LinkedHashMap 能够支持插入序或访问序的遍历,是因为 LinkedHashMap 在 HashMap 的基础上增加了双向链表的实现,下面会结合 JDK 8 的源码进行简要的分析。
底层结构LinkedHashMap 是 HashMap 的子类,因而 HashMap 中的成员在 LinkedHashMap 中也存在,如底层的 table 数组等,这里就不再说明了。我们重点关注一下 LinkedHashMap 中节点发生的变化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
//LinkedHashMap.Entey 继承自 HashMap.Node,
//而 HashMap.TreeNode 又继承了 LinkedHashMap.Entey
static class Entry<K,V> extends HashMap.Node<K,V> {
    //在父类的基础上增加了before 和 after
    //父类中存在 next
    //双向链表的连接通过before 和 after,哈希表中所有的元素可看作一个双向链表
    //桶内单向链表的连接通过 next
    Entry<K,V> before, after;
    //构造方法
    Entry(int hash, K key, V value, Node<K,V> next) {
        //父类构造方法
        super(hash, key, value, next);
    }
}

private static final long serialVersionUID = 3801124242820219131L;

/**
* The head (eldest) of the doubly linked list.
*/
//head成员为双向链表的头
transient LinkedHashMap.Entry<K,V> head;

/**
* The tail (youngest) of the doubly linked list.
*/
//tail成员为双向链表的尾
transient LinkedHashMap.Entry<K,V> tail;

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
//迭代顺序, true 使用最近被访问的顺序, false为插入顺序
//the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order), well-suited to building LRU caches
final boolean accessOrder;
为了实现双向链表,LinkedHashMap 的节点在父类的基础上增加了 before/after 引用,并且使用 head 和 tail 分别保存双向链表的头和尾。同时,增加了一个标识来保存 LinkedHashMap 的迭代顺序是插入序还是访问序。
由于父类 HashMap 的节点中存在 next 引用,可以将每个桶中的元素都当作一个单链表看待;LinkedHashMap 的每个桶中当然也保留了这个单链表关系,不过这个关系由父类进行管理,LinkedHashMap 中只会对双向链表的关系进行管理。LinkedHashMap 中所有的元素都被串联在一个双向链表中。
返回列表