LinkedHashMap 集合源码分析

2024-04-09 02:04

本文主要是介绍LinkedHashMap 集合源码分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LinkedHashMap 集合源码分析

文章目录

  • LinkedHashMap 集合源码分析
  • 一、字段分析
  • 二、内部类分析
  • 三、构造方法分析
  • 四、内部方法分析
  • 五、总结


在这里插入图片描述

  • LinkedHashMap 是 HashMap 的子类,在 HashMap 的基础上维护了双向链表,保证了有序性。默认是不排序的,可在初始化时传入 accessOrder = true,则进行排序

一、字段分析

// 指向LinkedHashMap 维护的双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 指向LinkedHashMap 维护的双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
// 是否排序:默认false:不排序。设为true时:越近访问的节点越靠近尾结点,即头结点 -> 尾结点
// 按 最近访问时间降序排列,即越靠近尾结点,离上次访问时间越近。
final boolean accessOrder;

二、内部类分析

//可以看到是继承了 hashmap 的 node,再次基础上多了 before 和  after,就是用来维护双向链表的
static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}

三、构造方法分析

	//传入默认的初始容量 和 加载因子,默认不排序public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}//闯入默认的初始容量,默认不排序public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}//无参构造,默认不排序public LinkedHashMap() {super();accessOrder = false;}//传入集合m来,使用集合m的所有元素来构建 LinkedHashMap,默认不排序public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}//传入初始容量,加载因子,也可指定进行排序即truepublic LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

四、内部方法分析

  • LinkedHashMap 的添加元素、删除元素,扩容等方法都是直接使用 了 HashMap 的方法。
  • 但在 HashMap 的基础上做了扩展,体现了多态性。主要是三种方法:
    • afterNodeRemoval:将被删除的节点从 LinkedHashMap 维护的双向链表中移除。
    • afterNodeInsertion:用来判断是否删除 LinkedHashMap 维护的双向链表的头结点,即最久未被访问的节点。
    • afterNodeAccess:将传入的node节点放置末尾,即最近访问的元素。
    //将 e 节点从双向链表中删除void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;}//evict:true:删除最久未被访问的元素,即双向链表的头结点void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}//节点e是刚刚访问的节点,判断是否需将其移动至双向链表的尾结点void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}}

五、总结

  • 我们知道 HashMap 并不能保证有序性,而 LinkedHashMap 作为 HashMap 子类解决了排序的问题。在构造时,通过传入afterNodeAccess = true 来设置LinkedHashMap是有序的。
  • 通过维护双向来链表来保证有序性,拥有变量 head 和 tail 分别指向双向链表的头结点和尾结点,越靠近 尾结点,越是最近访问的节点,越是靠近头结点,越是越久未被访问的节点。
  • 可用于实现 LRU 算法:
    • 使用 LinkedHashMap 实现 LRU:

      class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
      }
      
    • 不适用 LinkedHashMap 实现 LRU:

      class LRUCache {static class Node{public int key;public int val;public Node prev;public Node next;public Node(){this.key = -1;this.val = -1;}public Node(int key,int val){this.key = key;this.val = val;}}//最大容量    int capacity;//节点数量int size;//虚拟头节点Node dummyHead;//虚拟尾节点Node dummyTail;Map<Integer,Node> map = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;dummyHead = new Node();dummyTail = new Node();dummyHead.next = dummyTail;dummyTail.prev = dummyHead;}public int get(int key) {if(!map.containsKey(key)){return -1;}Node node = map.get(key);//将该节点从原位置删除remove(node);//将该节点添加到链表尾部addLeast(node);return node.val;}public void put(int key, int value) {Node cur = new Node(key,value);remove(map.get(key));addLeast(cur);}//删除节点public void remove(Node node){if(node == null) return;node.prev.next = node.next;node.next.prev = node.prev;node.next = null;node.prev = null;size --;map.remove(node.key);}//将节点添加到尾部public void addLeast(Node node){Node prev = dummyTail.prev;prev.next = node;node.prev = prev;node.next = dummyTail;dummyTail.prev = node;size ++;map.put(node.key,node);//超过最大容量了if(size > capacity){removeFirst();}}//删除头节点public Node removeFirst(){if(dummyHead.next == dummyTail) return null;Node remove = dummyHead.next;remove(remove);return remove;}
      }

这篇关于LinkedHashMap 集合源码分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886926

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三