Java LinkedHashMap工作原理及实现

1. 概述

在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:

运行结果是:

我们可以观察到,和HashMap的运行结果不同,LinkedHashMap的迭代输出的结果保持了插入顺序。是什么样的结构使得LinkedHashMap具有如此特性呢?我们还是一样的看看LinkedHashMap的内部结构,对它有一个感性的认识:

没错,正如官方文档所说:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked listrunning through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

LinkedHashMap是Hash表和链表的实现,并且依靠着双向链表保证了迭代顺序是插入的顺序。

2. 三个重点实现的函数

在HashMap中提到了下面的定义:

LinkedHashMap继承于HashMap,因此也重新实现了这3个函数,顾名思义这三个函数的作用分别是:节点访问后、节点插入后、节点移除后做一些事情。

afterNodeAccess函数

就是说在进行put之后就算是对节点的访问了,那么这个时候就会更新链表,把最近访问的放到最后,保证链表。

afterNodeInsertion函数

如果用户定义了removeEldestEntry的规则,那么便可以执行相应的移除操作。

afterNodeRemoval函数

这个函数是在移除节点后调用的,就是将节点从双向链表中删除。

我们从上面3个函数看出来,基本上都是为了保证双向链表中的节点次序或者双向链表容量所做的一些额外的事情,目的就是保持双向链表中节点的顺序要从eldest到youngest。

3. put和get函数

put函数在LinkedHashMap中未重新实现,只是实现了afterNodeAccessafterNodeInsertion两个回调函数。get函数则重新实现并加入了afterNodeAccess来保证访问顺序,下面是get函数的具体实现:

值得注意的是,在accessOrder模式下,只要执行get或者put等操作的时候,就会产生structural modification。官方文档是这么描述的:

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification.

总之,LinkedHashMap不愧是HashMap的儿子,和老子太像了,当然,青出于蓝而胜于蓝,LinkedHashMap的其他的操作也基本上都是为了维护好那个具有访问顺序的双向链表。:-)

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

C++ explicit禁止单参数构造函数隐式调用

C++中单参数构造函数是可以被隐式调用的,主要有两种情形会隐式调用单参数构造函数: (1)同类型对象的拷贝构造;即用相同类型的其它对象来初始化当前对象。 (...

24850
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day7 Java输入与输出

  本篇主要介绍Java的输入与输出,当然,这里说的是控制台下的输入与输出,窗口程序的设计将会再后续篇章中有详细说明。     Java的输出很简单,调用Sys...

24090
来自专栏java一日一条

Java LinkedHashMap工作原理及实现

在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:

9420
来自专栏我是攻城师

Java基础类String了解一下

当你路过一些商场或者地铁口的时候,有没有被千篇一律的"xx健身,了解一下" 所烦到。

23750
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 六、对象的秘密

30560
来自专栏源哥的专栏

BASE64编码

附录:BASE64编码的原理(节选自http://www.vbzx.net/ArticleView/vbzx_Article_View_1199.asp)

10540
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day10-基础题-继承;抽象类

Java基础-day10-基础题-继承&抽象类 什么是继承?继承有什么好处? 继承是面向对象最显著的一个特性。继承是从已有的类中派生出新的类,新的类能吸收已有类...

38660
来自专栏kevindroid

JNI所需的C语言知识小结

18150
来自专栏C/C++基础

Google C++编程风格指南(四)之类的相关规范

类是C++中基本的代码单元,自然被广泛使用。本节列举了在写一个类时要做什么、不要做什么。

12020
来自专栏函数式编程语言及工具

泛函编程(5)-数据结构(Functional Data Structures)

     编程即是编制对数据进行运算的过程。特殊的运算必须用特定的数据结构来支持有效运算。如果没有数据结构的支持,我们就只能为每条数据申明一个内存地址了,然后使...

22160

扫码关注云+社区

领取腾讯云代金券