【集合】LinkedHashMap 源码分析
前言
Github：https://github.com/yihonglei/jdk-source-code-reading
HashTable 源码
HashMap 源码
ConcurrentHashMap 源码
一 概述
LinkedHashMap 对数据的操作依赖 HashMap，对 HashMap 进行包装，解决 HashMap 的
无序性。底层基于双向链表 + 数组 + 单向链表 + 红黑树 实现，后三者是 HashMap 的底层
数据结构，依赖双向链表维护顺序性。LinkedHashMap 分为按两种顺序排列，
一种是按照插入的顺序排序，一种是按照访问的顺序排序，并且 LinkedHashMap 支持更好
的 LRU 算法。
二 实例
【Leetcode】LRU 缓存机制，最早插入的是最久不使用的，当缓存满的时候，删除最久
不使用的，为新插入的元素预留存储空间。
package com.jpeony.collection.linked;import java.util.LinkedHashMap;import java.util.Map;/*** 【题源】https://leetcode-cn.com/problems/lru-cache/** @author yihonglei*/public class LRUCache extends LinkedHashMap<Integer, Integer> {int capacity = 0;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}/*** 查询缓存，没有则返回 -1*/public int get(int key) {return super.getOrDefault(key, -1);}/*** 插入缓存，当缓存满了，调用 removeEldestEntry() 判断是否要移出最久不使用的元素，* 需要则调用 removeNode() 移出最久元素，为新元素的插入预留空间。*/public void put(int key, int value) {super.put(key, value);}/*** 是否要删除最近元素*/@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}}
三 LinkedHashMap 底层实现
重点分析“按插入顺序排序”和“按访问顺序排序”实现逻辑。
重要属性
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {/*** 链表结点*/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);}}/*** 链表头结点*/transient LinkedHashMap.Entry<K,V> head;/*** 链表尾节点*/transient LinkedHashMap.Entry<K,V> tail;/*** true 时 access-order，即按访问顺序遍历，如果为 false，则表示按插入顺序遍历。默认为false。*/final boolean accessOrder;}
accessOrder
accessOrder 为 true 时，即按访问顺序排序，如果为 false，则表示按插入顺序排序。
默认为 false。
按插入顺序性排序
LinkedHashMap#put()
put() 顺序的精华在于 LinkedHashMap 重写了 HashMap 的 newNode() 构造器方法。
newNode()
linkNodeLast()
将结点添加到链表尾部，从而保证插入的顺序性。
按读取顺序性排序
LinkedHashMap#get()
如果 accessOrder 为 true，表示按照访问的顺序排序，则调用 afterNodeAccess 将访问元素放
到链表尾部，从而实现按照访问的顺序排序。
afterNodeAccess()
其作用就是在访问元素之后，将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺
序的时候才会执行)。
LUR 操作
在插入元素的时候，如果存储满了，删除最久未使用的元素，即头结点。
afterNodeInsertion()
在插入新元素之后，需要回调函数判断是否需要移除一直不用的某些元素。
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 算法轻而易举实现缓存淘汰。
约定不等于承诺〃
ゞ 浴缸里的玫瑰
刺骨的言语ヽ痛彻心扉
淩亂°似流年
骑猪看日落
àì夳堔傛蜴生んèń
还没有评论，来说两句吧...