扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
这期内容当中小编将会给大家带来有关Java中LinkedHashMap的作用是什么,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
创新互联公司专业提供成都移动云计算中心服务,为用户提供五星数据中心、电信、双线接入解决方案,用户可自行在线购买成都移动云计算中心服务,并享受7*24小时金牌售后服务。
put()
方法的讲解。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node[] tab; HashMap.Node p; int n, i;
// ①、数组 table 为 null 时,调用 resize 方法创建默认大小的数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ②、计算下标,如果该位置上没有值,则填充
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
}
这个公式 i = (n - 1) & hash
计算后的值并不是按照 0、1、2、3、4、5 这样有序的下标将键值对插入到数组当中的,而是有一定的随机性。
那 LinkedHashMap 就是为这个需求应运而生的。LinkedHashMap 继承了 HashMap,所以 HashMap 有的关于键值对的功能,它也有了。
public class LinkedHashMap
extends HashMap
implements Map{}
此外,LinkedHashMap 内部又追加了双向链表,来维护元素的插入顺序。注意下面代码中的 before 和 after,它俩就是用来维护当前元素的前一个元素和后一个元素的顺序的。
static class Entry extends HashMap.Node {
LinkedHashMap.Entry before, after;
Entry(int hash, K key, V value, HashMap.Node next) {
super(hash, key, value, next);
}
}
关于双向链表,同学们可以回头看一遍我写的 LinkedList 那篇文章,会对理解本篇的 LinkedHashMap 有很大的帮助。
在继续下面的内容之前,我先贴一张图片,给大家增添一点乐趣——看我这心操的。UUID 那篇文章的标题里用了“可笑”和“你”,结果就看到了下面这么乐呵的留言。
(到底是知道还是不知道,我搞不清楚了。。。)那 LinkedHashMap 这篇也用了“你”和“可笑”,不知道到时候会不会有人继续对号入座啊,想想就觉得特别欢乐。
在 HashMap 那篇文章里,我有讲解到一点,不知道同学们记不记得,就是 null 会插入到 HashMap 的第一位。
Map hashMap = new HashMap<>();
hashMap.put("沉", "沉默王二");
hashMap.put("默", "沉默王二");
hashMap.put("王", "沉默王二");
hashMap.put("二", "沉默王二");
hashMap.put(null, null);
for (String key : hashMap.keySet()) {
System.out.println(key + " : " + hashMap.get(key));
}
输出的结果是:
null : null
默 : 沉默王二
沉 : 沉默王二
王 : 沉默王二
二 : 沉默王二
虽然 null 最后一位 put 进去的,但在遍历输出的时候,跑到了第一位。
那再来对比看一下 LinkedHashMap。
Map linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");
linkedHashMap.put(null, null);
for (String key : linkedHashMap.keySet()) {
System.out.println(key + " : " + linkedHashMap.get(key));
}
输出结果是:
沉 : 沉默王二
默 : 沉默王二
王 : 沉默王二
二 : 沉默王二
null : null
null 在最后一位插入,在最后一位输出。
输出结果可以再次证明,HashMap 是无序的,LinkedHashMap 是可以维持插入顺序的。
那 LinkedHashMap 是如何做到这一点呢?我相信同学们和我一样,非常希望知道原因。
要想搞清楚,就需要深入研究一下 LinkedHashMap 的源码。LinkedHashMap 并未重写 HashMap 的 put()
方法,而是重写了 put()
方法需要调用的内部方法 newNode()
。
HashMap.Node newNode(int hash, K key, V value, HashMap.Node e) {
LinkedHashMap.Entry p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}
前面说了,LinkedHashMap.Entry 继承了 HashMap.Node,并且追加了两个字段 before 和 after。
那,紧接着来看看 linkNodeLast()
方法:
private void linkNodeLast(LinkedHashMap.Entry p) {
LinkedHashMap.Entry last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
看到了吧,LinkedHashMap 在添加第一个元素的时候,会把 head 赋值为第一个元素,等到第二个元素添加进来的时候,会把第二个元素的 before 赋值为第一个元素,第一个元素的 afer 赋值为第二个元素。
这就保证了键值对是按照插入顺序排列的,明白了吧?
注:我用到的 JDK 版本为 14。
LinkedHashMap 不仅能够维持插入顺序,还能够维持访问顺序。访问包括调用 get()
方法、remove()
方法和 put()
方法。
要维护访问顺序,需要我们在声明 LinkedHashMap 的时候指定三个参数。
LinkedHashMap map = new LinkedHashMap<>(16, .75f, true);
第一个参数和第二个参数,看过 HashMap 的同学们应该很熟悉了,指的是初始容量和负载因子。
第三个参数如果为 true 的话,就表示 LinkedHashMap 要维护访问顺序;否则,维护插入顺序。默认是 false。
Map linkedHashMap = new LinkedHashMap<>(16, .75f, true);
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");
System.out.println(linkedHashMap);
linkedHashMap.get("默");
System.out.println(linkedHashMap);
linkedHashMap.get("王");
System.out.println(linkedHashMap);
输出的结果如下所示:
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二}
{沉=沉默王二, 王=沉默王二, 二=沉默王二, 默=沉默王二}
{沉=沉默王二, 二=沉默王二, 默=沉默王二, 王=沉默王二}
当我们使用 get()
方法访问键位“默”的元素后,输出结果中,默=沉默王二
在最后;当我们访问键位“王”的元素后,输出结果中,王=沉默王二
在最后,默=沉默王二
在倒数第二位。
也就是说,最不经常访问的放在头部,这就有意思了。有意思在哪呢?
我们可以使用 LinkedHashMap 来实现 LRU 缓存,LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。
public class MyLinkedHashMap extends LinkedHashMap {
private static final int MAX_ENTRIES = 5;
public MyLinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}
MyLinkedHashMap 是一个自定义类,它继承了 LinkedHashMap,并且重写了 removeEldestEntry()
方法——使 Map 最多可容纳 5 个元素,超出后就淘汰。
我们来测试一下。
MyLinkedHashMap map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程序员", "一枚有趣的程序员");
System.out.println(map);
map.put("一枚有颜值的程序员", "一枚有颜值的程序员");
System.out.println(map);
map.put("一枚有才华的程序员","一枚有才华的程序员");
System.out.println(map);
输出结果如下所示:
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员}
{王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员, 一枚有才华的程序员=一枚有才华的程序员}
沉=沉默王二
和 默=沉默王二
依次被淘汰出局。
假如在 put “一枚有才华的程序员”之前 get 了键位为“默”的元素:
MyLinkedHashMap map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程序员", "一枚有趣的程序员");
System.out.println(map);
map.put("一枚有颜值的程序员", "一枚有颜值的程序员");
System.out.println(map);
map.get("默");
map.put("一枚有才华的程序员","一枚有才华的程序员");
System.out.println(map);
那输出结果就变了,对吧?
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员}
{二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员, 默=沉默王二, 一枚有才华的程序员=一枚有才华的程序员}
沉=沉默王二
和 王=沉默王二
被淘汰出局了。
那 LinkedHashMap 是如何来维持访问顺序呢?同学们感兴趣的话,可以研究一下下面这三个方法。
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { }
afterNodeAccess()
会在调用 get()
方法的时候被调用,afterNodeInsertion()
会在调用 put()
方法的时候被调用,afterNodeRemoval()
会在调用 remove()
方法的时候被调用。
我来以 afterNodeAccess()
为例来讲解一下。
void afterNodeAccess(HashMap.Node e) { // move node to last
LinkedHashMap.Entry last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)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;
}
}
哪个元素被 get 就把哪个元素放在最后。了解了吧?
那同学们可能还想知道,为什么 LinkedHashMap 能实现 LRU 缓存,把最不经常访问的那个元素淘汰?
在插入元素的时候,需要调用 put()
方法,该方法最后会调用 afterNodeInsertion()
方法,这个方法被 LinkedHashMap 重写了。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
removeEldestEntry()
方法会判断第一个元素是否超出了可容纳的最大范围,如果超出,那就会调用 removeNode()
方法对最不经常访问的那个元素进行删除。
上述就是小编为大家分享的Java中LinkedHashMap的作用是什么了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流