LinkedHashMap就这么简单【源码剖析】

前言

声明,本文用得是jdk1.8

前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树还有HashMap基础了:

本篇主要讲解LinkedHashMap~

看这篇文章之前最好是有点数据结构的基础:

当然了,如果讲得有错的地方还请大家多多包涵并不吝在评论去指正~

一、LinkedHashMap剖析

LinkedHashMap数据结构图:

ps:图片来源网络,侵删~

首先我们来看看类继承图:

我简单翻译了一下顶部的注释(我英文水平渣,如果有错的地方请多多包涵~欢迎在评论区下指正)

从顶部翻译我们就可以归纳总结出HashMap几点:

  • 底层是散列表和双向链表
  • 允许为null,不同步
  • 插入的顺序是有序的(底层链表致使有序)
  • 装载因子和初始容量对LinkedHashMap影响是很大的~

同时也给我带了几个疑问:

  • access-ordered和insertion-ordered具体的使用和意思
  • 为什么说初始容量对遍历没有影响?

希望可以在看源码的过程中可以解决掉我这两个疑问~那接下来就开始吧~

1.1LinkedHashMap的域

1.2LinkedHashMap重写的方法

下面我列举就这两个比较重要的:

这就印证了我们的LinkedHashMap底层确确实实是散列表和双向链表~

  • 在构建新节点时,构建的是LinkedHashMap.Entry 不再是Node.

1.3构造方法

可以发现,LinkedHashMap有5个构造方法

下面我们来看看构造方法的定义是怎么样的:

从构造方法上我们可以知道的是:LinkedHashMap默认使用的是插入顺序

1.4put方法

原本我是想要找put方法,看看是怎么实现的,后来没找着,就奇了个怪~

再顿了一下,原来LinkedHashMap和HashMap的put方法是一样的!LinkedHashMap继承着HashMap,LinkedHashMap没有重写HashMap的put方法

所以,LinkedHashMap的put方法和HashMap是一样的。

如果没看过HashMap就是这么简单【源码剖析】的同学,可进去看看~

当然了,在创建节点的时候,调用的是LinkedHashMap重写的方法~

1.5get方法

get方法也是多了:判断是否为访问顺序~~~

讲到了这里,感觉我们可以简单测试一波了:

首先我们来看看已插入顺序来进行插入和遍历:

    public static void insertOrder() {

        // 默认是插入顺序
        LinkedHashMap<Integer,String>  insertOrder = new LinkedHashMap();

        String value = "关注公众号Java3y";
        int i = 0;

        insertOrder.put(i++, value);
        insertOrder.put(i++, value);
        insertOrder.put(i++, value);
        insertOrder.put(i++, value);
        insertOrder.put(i++, value);

        //遍历
        Set<Integer> set = insertOrder.keySet();
        for (Integer s : set) {
            String mapValue = insertOrder.get(s);
            System.out.println(s + "---" + mapValue);
        }
    }

测试一波:

接着,我们来测试一下以访问顺序来进行插入和遍历:

    public static void accessOrder() {
        // 设置为访问顺序的方式
        LinkedHashMap<Integer,String> accessOrder = new LinkedHashMap(16, 0.75f, true);

        String value = "关注公众号Java3y";
        int i = 0;
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);


        // 遍历
        Set<Integer> sets = accessOrder.keySet();
        for (Integer key : sets) {
            String mapValue = accessOrder.get(key);
            System.out.println(key + "---" + mapValue);
        }

    }

代码看似是没有问题,但是运行会出错的!

前面在看源码注释的时候我们就发现了:在AccessOrder的情况下,使用get方法也是结构性的修改

为了简单看出他俩的区别,下面我就直接用key来进行看了~

以下是访问顺序的测试

    public static void accessOrder() {
        // 设置为访问顺序的方式
        LinkedHashMap<Integer,String> accessOrder = new LinkedHashMap(16, 0.75f, true);

        String value = "关注公众号Java3y";
        int i = 0;
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);
        accessOrder.put(i++, value);


        // 访问一下key为3的元素再进行遍历
        accessOrder.get(3);

        // 遍历
        Set<Integer> sets = accessOrder.keySet();
        for (Integer key : sets) {

            System.out.println(key );
        }

    }

测试结果:

以下是插入顺序的测试(代码就不贴了,和上面几乎一样):

我们可以这样理解:最常用的将其放在链表的最后,不常用的放在链表的最前~

这个知识点以我的理解而言,它这个访问顺序在LinkedHashMap如果不重写用处并不大~它是用来给别的实现进行扩展

  • 因为最常被使用的元素再遍历的时候却放在了最后边,在LinkedHashMap中我也没找到对应的方法来进行调用~
  • 一个removeEldestEntry(Map.Entry<K,V> eldest)方法,重写它可以删除最久未被使用的元素!!
  • 还有一个是afterNodeInsertion(boolean evict)方法,新增时判断是否需要删除最久未被使用的元素!!

去网上搜了几篇资料,都是讲LRUMap的实现的(也就是对LinkedHashMap进行扩展),有兴趣的同学可参考下列链接:

1.6remove方法

对于remove方法,在LinkedHashMap中也没有重写,它调用的还是父类的HashMap的remove()方法,在LinkedHashMap中重写的是:afterNodeRemoval(Node<K,V> e)这个方法

当然了,在remove的时候会涉及到上面重写的方法:

1.7遍历的方法

Set<Map.Entry<K,V>> entrySet()是被重写的了

看到了这里,我们就知道为啥注释说:初始容量对遍历没有影响

因为它遍历的是LinkedHashMap内部维护的一个双向链表,而不是散列表(当然了,链表双向链表的元素都来源于散列表)

二、总结

LinkedHashMap比HashMap多了一个双向链表的维护,在数据结构而言它要复杂一些,阅读源码起来比较轻松一些,因为大多都由HashMap实现了..

阅读源码的时候我们会发现多态是无处不在的~子类用父类的方法,子类重写了父类的部分方法即可达到不一样的效果!

  • 比如:LinkedHashMap并没有重写put方法,而put方法内部的newNode()方法重写了。LinkedHashMap调用父类的put方法,里面回调的是重写后的newNode(),从而达到目的!

LinkedHashMap可以设置两种遍历顺序:

  • 访问顺序(access-ordered)
  • 插入顺序(insertion-ordered)
  • 默认是插入顺序的

对于访问顺序,它是LRU(最近最少使用)算法的实现,要使用它要么重写LinkedListMap的几个方法(removeEldestEntry(Map.Entry<K,V> eldest)afterNodeInsertion(boolean evict)),要么是扩展成LRUMap来使用,不然设置为访问顺序(access-ordered)的用处不大~

LinkedHashMap遍历的是内部维护的双向链表,所以说初始容量对LinkedHashMap遍历是不受影响的

参考资料:

  • 《Core Java》
  • https://blog.csdn.net/zxt0601/article/details/77429150
  • https://blog.csdn.net/panweiwei1994/article/details/76555359
  • https://zhuanlan.zhihu.com/p/28216267
  • https://blog.csdn.net/fan2012huan/article/details/51097331
  • https://www.cnblogs.com/chinajava/p/5808416.html

明天要是无意外的话,可能会写TreeMap,敬请期待哦~~~~

文章的目录导航:https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang

原文发布于微信公众号 - Java3y(java3y)

原文发表时间:2018-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

通常Java开发人员如何进行数据排序?

在实际工作中和平时学习中,以及分析开源Java项目的大量源代码后,我发现Java开发人员通常使用两种方法。一是使用Collections或 Arrays的 so...

22310
来自专栏对角另一面

lodash源码分析之baseFindIndex中的运算符优先级

本文为读 lodash 源码的第十篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

1878
来自专栏美团技术团队

Java8系列之重新认识HashMap

摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8...

3805
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

842
来自专栏JetpropelledSnake

Python面试题之Python中type和object的关系

下面是jeff kit的回答: 给别人讲解过很多次,但写成文字是第一次。试一试吧,自己主要也是看了这篇文章(Python Types and Objects...

391
来自专栏小灰灰

JDK容器学习之TreeMap (二) : 使用说明

TreeMap 使用说明 TreeMap 的底层数据结构为红黑树,主要是根据key进行排序,相比较于HashMap的数组+链表+红黑树的数据结构而言,两者的应...

1836
来自专栏用户2442861的专栏

典型的Top K算法_找出一个数组里面前K个最大数...或找出1亿个浮点数中最大的10000个...一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,

http://blog.163.com/xychenbaihu@yeah/blog/static/1322296552012821103039741/

542
来自专栏对角另一面

lodash源码分析之baseFindIndex中的运算符优先级

我悟出权力本来就是不讲理的——蟑螂就是海米;也悟出要造反,内心必须强大到足以承受任何后果才行。 ——北岛《城门开》 本文为读 lodash 源码的第十篇,后...

26211
来自专栏Phoenix的Android之旅

为什么HashCode相同的两个对象可能不相等?

面试中曾经有这么一道题目,考察的是开发者对于 equals()和 hashCode()的理解, 题目是这样的,

802
来自专栏xingoo, 一个梦想做发明家的程序员

《Effective Java》—— 对于所有对象都通用的方法

本节主要涉及Object中通用的一些方法,比如equals,hashCode,toString,clone,finalize等等 覆盖equals时请遵守...

1817

扫码关注云+社区