为什么说LinkedHashMap是Java中最大的数据结构? 了解一下?
云栖号:https://yqh.aliyun.com
第一手的上云资讯,不同行业精选的上云企业案例库,基于众多成功案例萃取而成的最佳实践,助力您上云决策!
Map 家族数量众多,其中 HashMap 和 ConcurrentHashMap 用的最多,而 LinkedHashMap 似乎则是不怎么用的,但是他却有着顺序。两种,一种是添加顺序,一种是访问顺序。
LinkedHashMap 继承了 HashMap。那么如果是你,你怎么实现这两个顺序呢?
如果实现添加顺序的话,我们可以在该类中,增加一个链表,每个节点对应 hash 表中的桶。这样,循环遍历的时候,就可以按照链表遍历了。只是会增大内存消耗。
如果实现访问顺序的话,同样也可以使用链表,但每次读取数据时,都需要更新一下链表,将最近一次读取的放到链尾。这样也就能够实现。此时也可以跟进这个特性实现 LRU(Least Recently Used) 缓存。
如何使用?
下面是个小 demo
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(16, 0.75f, true); for (int i = 0; i < 10; i++) { map.put(i, i); } for (Map.Entry entry : map.entrySet()) { System.out.println(entry.getKey() + ":" + entry.getValue()); } map.get(3); System.out.println(); for (Map.Entry entry : map.entrySet()) { System.out.println(entry.getKey() + ":" + entry.getValue()); }
打印结果:
0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9 0:0 1:1 2:2 4:4 5:5 6:6 7:7 8:8 9:9 3:3
首先构造方法是有意思的,比 HashMap 多了一个 accessOrder boolean 参数。表示,按照访问顺序来排序。最新访问的放在链表尾部。
如果是默认的,则是按照添加顺序,即 accessOrder 默认是 false。
源码实现
如果看 LinkedHashMap 内部源码,会发现,内部确实维护了一个链表:
/** * 双向链表的头,最久访问的 */ transient LinkedHashMap.Entry<K,V> head; /** * 双向链表的尾,最新访问的 */ transient LinkedHashMap.Entry<K,V> tail;
而这个 LinkedHashMap.Entry 内部也维护了双向链表必须的元素,before,after:
/** * HashMap.Node subclass for normal LinkedHashMap entries. */ 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); } }
在添加元素的时候,会追加到尾部。
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; } // link at the end of list private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }
在 get 的时候,会根据 accessOrder 属性,修改链表顺序:
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; } void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.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; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
同时注意:这里修改了 modCount,即使是读操作,并发也是不安全的。
如何实现 LRU 缓存?
LRU 缓存:LRU(Least Recently Used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
LinkedHashMap 并没有帮我我们实现具体,需要我们自己实现 。具体实现方法是 removeEldestEntry 方法。
一起来看看原理。
首先,HashMap 在 putVal 方法最后,会调用 afterNodeInsertion 方法,其实就是留给 LinkedHashMap 的。而 LinkedHashMap 的具体实现则是根据一些条件,判断是否需要删除 head 节点。
源码如下:
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); } }
evict 参数表示是否需要删除某个元素,而这个 if 判断需要满足的条件如上:head 不能是 null,调用 removeEldestEntry 方法,返回 true 的话,就删除这个 head。而这个方法默认是返回 false 的,等待着你来重写。
所以,removeEldestEntry 方法的实现通常是这样:
public boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
如果长度大于容量了,那么就需要清除不经常访问的缓存了。afterNodeInsertion 会调用 removeNode 方法,删除掉 head 节点 —— 如果 accessOrder 是 true 的话,这个节点就是最不经常访问的节点。
拾遗
LinkedHashMap 重写了一些 HashMap 的方法,例如 containsValue 方法,这个方法大家猜一猜,怎么重写比较合理?
HashMap 使用了双重循环,先循环外层的 hash 表,再循环内层的 entry 链表。性能可想而知。
但 LinkedHashMap 内部有个元素链表,直接遍历链表就行。相对而言而高很多。
public boolean containsValue(Object value) { for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; }
这也算一种空间换时间的策略吧。
get 方法当然也是要重写的。因为需要根据 accessOrder 更新链表。
总结
雪薇的总结的一下:
LinkedHashMap 内部包含一个双向链表维护顺序,支持两种顺序——添加顺序,访问顺序。
默认就是按照添加顺序来的,如果要改成访问顺序的话,构造方法中的 accessOrder 需要设置成 true。这样,每次调用 get 方法,就会将刚刚访问的元素更新到链表尾部。
关于 LRU,在accessOrder 为 true 的模式下,你可以重写 removeEldestEntry 方法,返回 size() > capacity,这样,就可以删除最不常访问的元素。
原文发布时间:2020-01-09
本文作者:莫那一鲁道
本文来自阿里云云栖号合作伙伴“互联网架构师”,了解相关信息可以关注“互联网架构师”
云栖号:https://yqh.aliyun.com
第一手的上云资讯,不同行业精选的上云企业案例库,基于众多成功案例萃取而成的最佳实践,助力您上云决策!
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
阿里云蚂蚁合约体验链 Quick Start
概述 阿里云蚂蚁区块链提供合约体验链,方便用户快速体验区块链,可以免费快速测试体验区块链的功能。下面分别从门户创建及相关配置获取、依赖包安装和测试代码的配置三个方面介绍逐步介绍合约体验了的使用。 Step By Step 1、服务申请,门户地址 下载申请证书的时候生成的证书等信息到本地,记住配置SSL证书时设置的密码。 2、创建账户 下载user.key到本地。 3、全部下载的信息 4、依赖包安装 sdk解压,在解压的路径下运行如下指令安装jar包到本地仓库 //安装 SDK 到本地仓库 mvn install:install-file -Dfile=mychainx-sdk-0.10.2.6.jar -DgroupId=com.alipay.mychainx -DartifactId=mychainx-sdk -Dversion=0.10.2.6 -Dpackaging=jar -DpomFile=pom.xml //安装 Netty 依赖到本地仓库,注意选择对应平台 netty-tcnative-openssl-static 版本,注意修改 classifier,macOS :os...
- 下一篇
Hyperf 发布 v1.1.14 版本及超全局变量组件
更新内容 本周更新主要为 JSON-RPC 组件做了大量的优化工作和为 AMQP 增加了 KeepaliveIO 功能,同时我们还发布了 hyperf/super-globals 组件,通过安装该组件,底层会自动的 hook 掉 $_GET、$_POST、$_REQUEST、$_SERVER、$_COOKIE、$_SESSION 这些超全局变量,使之可以保留 PHP-FPM 下的用法,又不会导致协程间的数据混淆。同时我们还修复了一些组件的 ?Bug,发布于 1.1.14 版,强烈建议使用到 JSON-RPC、AMQP、Aliyun ACM 和 devtool 的用户更新。 直接访问 官网 hyperf.io 或 文档 hyperf.wiki 查看更新内容。 新增 #1166 为 AMQP 增加 KeepaliveIO 功能; #1208 为 JSON-RPC 的响应增加了 error.data.code 值来传递 Exception Code; #1208 为 Hyperf\Rpc\Contract\TransporterInterface 增加了 recv 方法; #1215 新增...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS关闭SELinux安全模块
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程