开发者社区> 欧阳愠斐> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java进阶-LinkedHashMap 底层分析

简介: 众所周知 HashMap 是一个无序的 Map,因为每次根据 key 的 hashcode 映射到 Entry数组上,所以遍历出来的顺序并不是写入的顺序。
+关注继续查看

众所周知 HashMap 是一个无序的 Map,因为每次根据 key 的 hashcode 映射到 Entry数组上,所以遍历出来的顺序并不是写入的顺序。

因此 JDK 推出一个基于 HashMap 但具有顺序的 LinkedHashMap 来解决有排序需求的场景。

它的底层是继承于 HashMap 实现的,由一个双向链表所构成。

LinkedHashMap 的排序方式有两种:

  • 根据写入顺序排序。
  • 根据访问顺序排序。

其中根据访问顺序排序时,每次 get 都会将访问的值移动到链表末尾,这样重复操作就能的到一个按照访问顺序排序的链表。

数据结构


 

1

2

3

4

5

6

7

8

9

10

11


 

@Test

public void test(){

Map<String, Integer> map = new LinkedHashMap<String, Integer>();

map.put("1",1) ;

map.put("2",2) ;

map.put("3",3) ;

map.put("4",4) ;

map.put("5",5) ;

System.out.println(map.toString());

}

调试可以看到 map 的组成:

打开源码可以看到:


 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21


 

/**

* The head of the doubly linked list.

*/

private transient Entry<K,V> header;

/**

* The iteration ordering method for this linked hash map: <tt>true</tt>

* for access-order, <tt>false</tt> for insertion-order.

*

* @serial

*/

private final boolean accessOrder;

private static class Entry<K,V> extends HashMap.Entry<K,V> {

// These fields comprise the doubly linked list used for iteration.

Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {

super(hash, key, value, next);

}

}

其中 Entry 继承于 HashMap 的 Entry,并新增了上下节点的指针,也就形成了双向链表。

还有一个 header 的成员变量,是这个双向链表的头结点。

上边的 demo 总结成一张图如下:

第一个类似于 HashMap 的结构,利用 Entry 中的 next 指针进行关联。

下边则是 LinkedHashMap 如何达到有序的关键。

就是利用了头节点和其余的各个节点之间通过 Entry 中的 after 和 before 指针进行关联。

其中还有一个 accessOrder 成员变量,默认是 false,默认按照插入顺序排序,为 true 时按照访问顺序排序,也可以调用:


 

1

2

3

4

5

6


 

public LinkedHashMap(int initialCapacity,

float loadFactor,

boolean accessOrder) {

super(initialCapacity, loadFactor);

this.accessOrder = accessOrder;

}

这个构造方法可以显示的传入 accessOrder

构造方法

LinkedHashMap 的构造方法:


 

1

2

3

4


 

public LinkedHashMap() {

super();

accessOrder = false;

}

其实就是调用的 HashMap 的构造方法:

HashMap 实现:


 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15


 

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

this.loadFactor = loadFactor;

threshold = initialCapacity;

//HashMap 只是定义了改方法,具体实现交给了 LinkedHashMap

init();

}

可以看到里面有一个空的 init(),具体是由 LinkedHashMap 来实现的:


 

1

2

3

4

5


 

@Override

void init() {

header = new Entry<>(-1, null, null, null);

header.before = header.after = header;

}

其实也就是对 header 进行了初始化。

put 方法

看 LinkedHashMap 的 put() 方法之前先看看 HashMap 的 put 方法:


 

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

42


 

public V put(K key, V value) {

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

if (key == null)

return putForNullKey(value);

int hash = hash(key);

int i = indexFor(hash, table.length);

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

//空实现,交给 LinkedHashMap 自己实现

e.recordAccess(this);

return oldValue;

}

}

modCount++;

// LinkedHashMap 对其重写

addEntry(hash, key, value, i);

return null;

}

// LinkedHashMap 对其重写

void addEntry(int hash, K key, V value, int bucketIndex) {

if ((size >= threshold) && (null != table[bucketIndex])) {

resize(2 * table.length);

hash = (null != key) ? hash(key) : 0;

bucketIndex = indexFor(hash, table.length);

}

createEntry(hash, key, value, bucketIndex);

}

// LinkedHashMap 对其重写

void createEntry(int hash, K key, V value, int bucketIndex) {

Entry<K,V> e = table[bucketIndex];

table[bucketIndex] = new Entry<>(hash, key, value, e);

size++;

}

主体的实现都是借助于 HashMap 来完成的,只是对其中的 recordAccess(), addEntry(), createEntry() 进行了重写。

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


 

//就是判断是否是根据访问顺序排序,如果是则需要将当前这个 Entry 移动到链表的末尾

void recordAccess(HashMap<K,V> m) {

LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;

if (lm.accessOrder) {

lm.modCount++;

remove();

addBefore(lm.header);

}

}

//调用了 HashMap 的实现,并判断是否需要删除最少使用的 Entry(默认不删除)

void addEntry(int hash, K key, V value, int bucketIndex) {

super.addEntry(hash, key, value, bucketIndex);

// Remove eldest entry if instructed

Entry<K,V> eldest = header.after;

if (removeEldestEntry(eldest)) {

removeEntryForKey(eldest.key);

}

}

void createEntry(int hash, K key, V value, int bucketIndex) {

HashMap.Entry<K,V> old = table[bucketIndex];

Entry<K,V> e = new Entry<>(hash, key, value, old);

//就多了这一步,将新增的 Entry 加入到 header 双向链表中

table[bucketIndex] = e;

e.addBefore(header);

size++;

}

//写入到双向链表中

private void addBefore(Entry<K,V> existingEntry) {

after = existingEntry;

before = existingEntry.before;

before.after = this;

after.before = this;

}

get 方法

LinkedHashMap 的 get() 方法也重写了:


 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21


 

public V get(Object key) {

Entry<K,V> e = (Entry<K,V>)getEntry(key);

if (e == null)

return null;

//多了一个判断是否是按照访问顺序排序,是则将当前的 Entry 移动到链表头部。

e.recordAccess(this);

return e.value;

}

void recordAccess(HashMap<K,V> m) {

LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;

if (lm.accessOrder) {

lm.modCount++;

//删除

remove();

//添加到头部

addBefore(lm.header);

}

}

clear() 清空就要比较简单了:


 

1

2

3

4

5


 

//只需要把指针都指向自己即可,原本那些 Entry 没有引用之后就会被 JVM 自动回收。

public void clear() {

super.clear();

header.before = header.after = header;

}

总结

总的来说 LinkedHashMap 其实就是对 HashMap 进行了拓展,使用了双向链表来保证了顺序性。

因为是继承与 HashMap 的,所以一些 HashMap 存在的问题 LinkedHashMap 也会存在,比如不支持并发等。

1、具有1-5工作经验的,面对目前流行的技术不知从何下手,需要突破技术瓶颈的可以加群。

2、在公司待久了,过得很安逸,但跳槽时面试碰壁。需要在短时间内进修、跳槽拿高薪的可以加群。

3、如果没有工作经验,但基础非常扎实,对java工作机制,常用设计思想,常用java开发框架掌握熟练的,可以加群。

4、觉得自己很牛B,一般需求都能搞定。但是所学的知识点没有系统化,很难在技术领域继续突破的可以加群。

5.群号 468947140,点击链接加入群聊【Java-BATJ企业级资深架构】:https://jq.qq.com/?_wv=1027&k=5yKnHqY

6.阿里Java高级大牛直播讲解知识点,分享知识,知识点都是各位老师多年工作经验的梳理和总结,带着大家全面、科学地建立自己的技术体系和技术认知!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【Java原理探索】从底层角度去分析线程的实现原理
【Java原理探索】从底层角度去分析线程的实现原理
0 0
Java中常用API总结(1)—— Math类(含底层源码阅读)
Java中常用API总结(1)—— Math类(含底层源码阅读)
0 0
Java一文深入理解LinkedList,谈一谈LinkedList底层
日常开发中,保存一组数据使用的最多的是List,List子类用的最多的是 ArrayList, 其次就是 LinkedList 。 我们知道 ArrayList 是以数组实现的,遍历时很快,但是插入、删除时都需要移动后面的元素,效率略差些。
0 0
Java面试必问之线程池的创建使用、线程池的核心参数、线程池的底层工作原理
Java面试必问之线程池的创建使用、线程池的核心参数、线程池的底层工作原理
0 0
阿里P8写出的《深入理解Java虚拟机3》轻松学会JVM底层
前言 Java是目前用户最多、使用范围最广的软件开发技术,Java的技术体系主要由支撑Java程序运行的虚拟机、提供各开发领域接口支持的Java类库、Java编程语言及许许多多的第三E方Java框架(如Spring、 MyBatis等) 构成。在国内,有关Java类库API、Java语言语法及第三方框架的技术资料和书籍非常丰富,相比而言,有关Java虚拟机的资料却显得异常贫乏。
0 0
5分钟让你深入了解Java中的final关键字,从底层开始入手
5分钟让你深入了解Java中的final关键字,从底层开始入手
0 0
关于Java面试中的ArrayList底层结构、底层源码的高频热点面试题解析
关于Java面试中的ArrayList底层结构、底层源码的高频热点面试题解析
0 0
Java底层源码——Arrays.toString(数组) & object.toString() & new String()
Java底层源码——Arrays.toString(数组) & object.toString() & new String()
0 0
Java 修饰符详解:吐血整理,带你从底层语法和开发案例疏通这 11 种常见修饰符
Java 修饰符详解:吐血整理,带你从底层语法和开发案例疏通这 11 种常见修饰符
0 0
终于有清华大佬深入计算机底层总结出这份图解Java底层/网络手册
计算机(computer)俗称电脑,是现代一种用于高速计算的电子计算机器,可以进行数值计算,又可以进行逻辑计算,还具有存储记忆功能。是能够按照程序运行,自动、高速处理海量数据的现代化智能电子设备。 由硬件系统和软件系统所组成,没有安装任何软件的计算机称为裸机。可分为超级计算机、工业控制计算机、网络计算机、个人计算机、嵌入式计算机五类,较先进的计算机有生物计算机、光子计算机、量子计算机等。 从最初由约翰·冯·诺依曼发明之后经过代代的不断改良和迭代增加到现在已经发展了几十年之久,计算机可以说是20世纪最先进的科学发展之一
0 0
+关注
欧阳愠斐
程序员学习交流学习群:908676731
文章
问答
文章排行榜
最热
最新
相关电子书
更多
JAVA 应用排查全景图
立即下载
Java工程师必读手册
立即下载
Java应用提速(速度与激情)
立即下载