文档章节

聊聊LinkedHashMap

xpbob
 xpbob
发布于 2018/11/12 13:55
字数 981
阅读 495
收藏 9

LinkedHashMap简介

LinkedHashMap是一个根据某种规则有序的hashmap。根据名字,我们也可以看出这个集合是有hash散列的功能的同时也有顺序。hashmap是无法根据某种顺序来访问数据的,例如放入集合的元素先后的顺序。list都有这个功能,可以根据放入集合的先后来访问具体的数据。这里大家也肯定是有疑问的,例如都已经使用了hash了,为什么还要去保证顺序访问。这个在后面的场景中解释。

LinkedHashMap的实现

当刚遇到这个集合的时候,我也疑惑,能同时满足条件的数据结构究竟是怎么样的。如果没有思考这个问题,还请看到这里好好想想。 ---------滑稽分割-------- 答案确实是没有这样的数据结构。他是两种结构的组合。一种是我们熟悉的hashmap。另外一种就是链表。数据存入集合的时候,先根据hashmap的流程存放入数组中。然后再根据链表的原则,进行链接。 如果看源码,也会发现其实没有多少方法。基本都是继承自hashmap的。

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);
        }
    }

可以看出。相比hashmap的节点。linkedhashmap主要增加before, after。可以组成一个双向链表。
节点加入

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;//获取最后一个节点
        tail = p;//tail指向新加入的节点
        if (last == null)//链表为空
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
    //新建节点的时候把节点加入了双向链表
   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

删除情况也是类似。
节点访问

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)//是否根据某种顺序
            afterNodeAccess(e);//把访问节点加入到尾节点
        return e.value;
    }
    

afterNodeAccess中主要是把访问的节点从原来的位置摘除,加入到尾节点,成为链表的最后一个元素。

使用场景

顺序遍历和快速定位
LinkedHashMap适合有加入顺序和快速定位的场景。我自己开发中遇到过一个场景,就是把配置顺序读取,需要按照读取的顺序访问,而且还需要根据值key直接获取值。这个场景就需要使用LinkedHashMap。
缓存
LinkedHashMap另外一个强大的功能就是做缓存。不过我们要继承一下。去重写一个方法。

   protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {//默认是没有操作
        return false;
    }

这个方法在插入之后会被调用到。

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {//删除第一个元素
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

LinkedHashMap支持两种缓存策略。FIFO和LRU。大家应该也猜到控制策略的地方就是accessOrder。默认为false。就是FIFO。设置为true时就是LRU。因为在访问的时候会调整链表结构,调用afterNodeAccess会把访问的节点放入队列最后。所以每次删除first就可以达到效果。我一般会选择继承LinkedHashMap。然后重写removeEldestEntry,例如可以元素个数达到200范围true。这里需要根据具体场景来编写。

© 著作权归作者所有

xpbob

xpbob

粉丝 99
博文 98
码字总数 80029
作品 0
高级程序员
私信 提问
聊聊springboot2的LoggersEndpoint

序 本文主要研究下springboot2的LoggersEndpoint 实例 GET /actuator/loggers GET /actuator/loggers/com.example POST LoggersEndpointAutoConfiguration spring-boot-actuator-autoconfigu......

go4it
2018/04/25
117
0
聊聊dubbo的LRUCache

序 本文主要研究一下dubbo的LRUCache LRUCache dubbo-2.7.2/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LRUCache.java LRUCache继承了LinkedHashMap,其initialCapacity为1......

go4it
06/20
9
0
性能优化(2.3)-LruCache源码解析

主目录见:Android高级进阶知识(这是总目录索引)  今天我们来聊聊缓存策略相关的内容,LruCache应该说是三级缓存策略会使用到的内存缓存策略。今天我们就来扒一扒这里面的原理,同时也温故...

ZJ_Rocky
2017/11/16
0
0
聊聊feign的HystrixInvocationHandler

序 本文主要研究一下feign的HystrixInvocationHandler HystrixInvocationHandler feign-hystrix-10.2.3-sources.jar!/feign/hystrix/HystrixInvocationHandler.java HystrixInvocationHandle......

go4it
07/19
37
0
聊聊spring.cloud.gateway.default-filters

序 本文主要研究下spring.cloud.gateway.default-filters 配置 default-filters,配置的是FilterDefinition对象 FilterDefinition spring-cloud-gateway-core-2.0.0.RC1-sources.jar!/org/sp......

go4it
2018/06/01
511
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
48分钟前
71
1
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
9
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部