【集合】LinkedHashMap 源码分析

雨点打透心脏的1/2处 2022-10-13 05:06 355阅读 0赞

前言

Github:https://github.com/yihonglei/jdk-source-code-reading

HashTable 源码

HashMap 源码

ConcurrentHashMap 源码

一 概述

LinkedHashMap 对数据的操作依赖 HashMap,对 HashMap 进行包装,解决 HashMap 的

无序性。底层基于双向链表 + 数组 + 单向链表 + 红黑树 实现,后三者是 HashMap 的底层

数据结构,依赖双向链表维护顺序性。LinkedHashMap 分为按两种顺序排列,

一种是按照插入的顺序排序,一种是按照访问的顺序排序,并且 LinkedHashMap 支持更好

的 LRU 算法。

二 实例

【Leetcode】LRU 缓存机制,最早插入的是最久不使用的,当缓存满的时候,删除最久

不使用的,为新插入的元素预留存储空间。

  1. package com.jpeony.collection.linked;
  2. import java.util.LinkedHashMap;
  3. import java.util.Map;
  4. /**
  5. * 【题源】https://leetcode-cn.com/problems/lru-cache/
  6. *
  7. * @author yihonglei
  8. */
  9. public class LRUCache extends LinkedHashMap<Integer, Integer> {
  10. int capacity = 0;
  11. public LRUCache(int capacity) {
  12. super(capacity, 0.75f, true);
  13. this.capacity = capacity;
  14. }
  15. /**
  16. * 查询缓存,没有则返回 -1
  17. */
  18. public int get(int key) {
  19. return super.getOrDefault(key, -1);
  20. }
  21. /**
  22. * 插入缓存,当缓存满了,调用 removeEldestEntry() 判断是否要移出最久不使用的元素,
  23. * 需要则调用 removeNode() 移出最久元素,为新元素的插入预留空间。
  24. */
  25. public void put(int key, int value) {
  26. super.put(key, value);
  27. }
  28. /**
  29. * 是否要删除最近元素
  30. */
  31. @Override
  32. protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  33. return size() > capacity;
  34. }
  35. }

三 LinkedHashMap 底层实现

重点分析“按插入顺序排序”和“按访问顺序排序”实现逻辑。

重要属性

  1. public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
  2. /**
  3. * 链表结点
  4. */
  5. static class Entry<K,V> extends HashMap.Node<K,V> {
  6. Entry<K,V> before, after;
  7. Entry(int hash, K key, V value, Node<K,V> next) {
  8. super(hash, key, value, next);
  9. }
  10. }
  11. /**
  12. * 链表头结点
  13. */
  14. transient LinkedHashMap.Entry<K,V> head;
  15. /**
  16. * 链表尾节点
  17. */
  18. transient LinkedHashMap.Entry<K,V> tail;
  19. /**
  20. * true 时 access-order,即按访问顺序遍历,如果为 false,则表示按插入顺序遍历。默认为false。
  21. */
  22. final boolean accessOrder;
  23. }

accessOrder

accessOrder 为 true 时,即按访问顺序排序,如果为 false,则表示按插入顺序排序。

默认为 false。

按插入顺序性排序

LinkedHashMap#put()

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70

put() 顺序的精华在于 LinkedHashMap 重写了 HashMap 的 newNode() 构造器方法。

newNode()

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1

linkNodeLast()

将结点添加到链表尾部,从而保证插入的顺序性。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2

按读取顺序性排序

LinkedHashMap#get()

如果 accessOrder 为 true,表示按照访问的顺序排序,则调用 afterNodeAccess 将访问元素放

到链表尾部,从而实现按照访问的顺序排序。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 3

afterNodeAccess()

其作用就是在访问元素之后,将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺

序的时候才会执行)。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 4

LUR 操作

在插入元素的时候,如果存储满了,删除最久未使用的元素,即头结点。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 5

afterNodeInsertion()

在插入新元素之后,需要回调函数判断是否需要移除一直不用的某些元素。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 6

removeEldestEntry()

这个是需要具体继承 LinkedHashMap 的子类重写的逻辑,你可以写自己的满逻辑。

removeNode()

真正去删除链表的头结点。

四 总结

1、HashMap 是无序的,如果用 HashMap 实现本地缓存,不能很好支持 LRU 淘汰策略,

通过 LinkedHashMap 加个双向链表维护有序性,支持 LRU 这样的快速操作;

2、关于 散列表有很多实现。

HashTable,通过 synchronized 锁哈希表方式实现线程安全,jdk 已经对其放弃维护更新,

价值不大,是线程安全的散列表;

HashMap,通过 数组+链表(解决 hash 冲突),在 jdk1.8 加了 红黑树优化链表时间复杂度退化

O(n) 问题,并从链表的头插入优化到尾插法,解决并发时扩容导致 HashMap 死循环问题的线程

安全问题,是非线程安全的散列表;

SychronizedMap,包装 HashMap 解决线程安全问题,但是性能并不理想;

ConcurrentHashMap,底层基于 数组+链表(解决 hash 冲突),在 jdk1.8 加了 红黑树优化链

表时间复杂度退化 O(n) 问题,通过 分段锁解决线程安全问题,在 jdk1.8 优化为 sychronized +

CAS 解决线程安全问题,是线程安全的散列表;

LinkedHashMap,通过双向链表解决 HashMap 无序问题,非线程安全;

你会发现 jdk 搞这么多散列表干啥子,其实就像业务系统,一开始就是满足一种需求,然后不断

优化需求,搞得越来越多优化,选择适合的,才是最好的。这些散列表实现方式,都是围绕着

散列表的执行性能和线程安全的中心思想进行不断优化升级,并拓展了一些比如顺序性啥的

额外需求,你可能要问顺序性有啥用,如果你要让你自己实现 LRU 缓存淘汰策略,这个时候

顺序性的 LinkedHashMap 数据结构就能最快的满足你的 LRU 算法轻而易举实现缓存淘汰。

发表评论

表情:
评论列表 (有 0 条评论,355人围观)

还没有评论,来说两句吧...

相关阅读