热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

AndroidLinkedHashMap源码详解

尊重原创,转载请标明出处http:blog.csdn.netabcdef314159在上一篇中我们分析了HashMap的源码,了解HashMap是以数组加链表的形式

尊重原创,转载请标明出处    http://blog.csdn.net/abcdef314159


在上一篇中我们分析了HashMap的源码,了解HashMap是以数组加链表的形式存储的,这一篇我们结合上一篇的内容来分析一下LinkedHashMap的源码,在阅读之前最好能把上一篇的《Android HashMap源码详解》看一遍,尤其是HashMap的结构图要理解清楚,我们来先看一下LinkedHashMap的构造方法,由于比较多,我们随便挑一个

    public LinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }

我们看到上面几个参数initialCapacity是初始化空间大小,loadFactor是加载因子,就是当他的size大于initialCapacity*loadFactor的时候就会扩容,他的默认值是0.75,我们看一下

    /**
     * The default load factor. Note that this implementation ignores the
     * load factor, but cannot do away with it entirely because it's
     * mentioned in the API.
     *
     * 

Note that this constant has no impact on the behavior of the program, * but it is emitted as part of the serialized form. The load factor of * .75 is hardwired into the program, which uses cheap shifts in place of * expensive division. */ static final float DEFAULT_LOAD_FACTOR = .75F;

我们看上面的注释,意思是HashMap已经忽略了加载因子,但又不能完全废除它,其实我们看到HashMap中是没有任何用到,我们来看一下

    public HashMap(int capacity, float loadFactor) {
        this(capacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Load factor: " + loadFactor);
        }

        /*
         * Note that this implementation ignores loadFactor; it always uses
         * a load factor of 3/4. This simplifies the code and generally
         * improves performance.
         */
    }

所以这个loadFactor没有任何作用,我们看下面的注释大概也能明白,HashMap使用的加载因子是3/4,也就是0.75,这个我们在上一篇的 private HashMapEntry[] makeTable(int newCapacity)方法中已经讲过,这里就不在介绍。我们看到LinkedHashMap的构造方法中还有一个参数accessOrder,我们看一下注释

    /**
     * True if access ordered, false if insertion ordered.
     */
    private final boolean accessOrder;

我们知道,LinkedHashMap继承了HashMap,所以他的数据存储还是按照HashMap的存储结构存储的,即数组加链表(单向链表),但LinkedHashMap内部又维护了一个双向的环形链表,它主要是在删除的时候用到,删除最先加入的元素,上面的accessOrder主要对双向环形链表有影响,如果是true则表示双向环形链表按照访问的顺序存储,如果是false则表示按照插入的顺序存储,区别就是如果是插入顺序则双向环形链表的结构是不变的,如果是访问顺序则每次访问的时候比如get方法就会把get到的元素从链表中删除然后重新加到链表的尾部,因为尾部表示最新加入的,删除的时候是从头部开始删除,尾部是最后删除的,符合最近使用原则,LruCache中封装的LinkedHashMap是按照访问顺序存储的,因为LruCache实现的是LRU: 最近最少使用(Least Recently Used)原则。在讲LinkedHashMap的一些常用方法之前我们来先看一个类LinkedEntry

    static class LinkedEntry extends HashMapEntry {
        LinkedEntry nxt;
        LinkedEntry prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry next,
                    LinkedEntry nxt, LinkedEntry prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }

我们看到LinkedEntry继承了HashMapEntry,并且比他多了两个属性,nxt表示链表的下一个元素,prv表示链表的前一个元素,注意这里的nxt和HashMapEntry中的next是不一样的,这里的nxt是指双向环形链表的下一个,而HashMapEntry中的next是指存放数组挂载的下一个,是存放位置上的。我们看到构造方法中有这样一个方法init

    /**
     * A dummy entry in the circular linked list of entries in the map.
     * The first real entry is header.nxt, and the last is header.prv.
     * If the map is empty, header.nxt == header && header.prv == header.
     */
    transient LinkedEntry header;

    @Override void init() {
        header = new LinkedEntry();
    }

他初始化了一个header,这个header是双向环形链表的头,不存放任何数据的,我们看到上面的注释,意思是第一个真正的entry是header的下一个,最后一个entry是header的前一个,如果为null,则他的前一个和后一个都等于header,因为他是个环形链表,所以header的下一个也是最先加入的,header的前一个是最后一个加入的,下面我给大家画个图可能就会明白一些


下面我们来看一下他的一些方法

    public Entry eldest() {
        LinkedEntry eldest = header.nxt;
        return eldest != header ? eldest : null;
    }

得到最老的元素,也是最先存放的元素,由上图我们可以看到最先存放的元素是header的下一个,这个比较好理解,我们在来看其他的一些方法

    @Override void addNewEntry(K key, V value, int hash, int index) {
        LinkedEntry header = this.header;

        // Remove eldest entry if instructed to do so.
        LinkedEntry eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        LinkedEntry oldTail = header.prv;
        LinkedEntry newTail = new LinkedEntry(
                key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;
    }

所有的操作都是先找到header,看到第6行,在添加新的元素的时候如果removeEldestEntry方法返回true,将移除最老的元素,也就是header的下一个元素,removeEldestEntry默认返回为false,我们也可以自己复写他。

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }

如果不移除最老的元素,当添加到一定数量的时候可能会扩容。我们仔细看addNewEntry方法中的最后3行代码,首先是new了一个新的LinkedEntry,然后在加入到table中,最后一行中header.prv = newTail,这回大家可能及明白了header的前一个元素就是新元素,也是最后一个加入的,当然上面的双向链表和存储结构是不冲突的,上面的方法还有一个奇葩的地方,就是加入一个元素之后他的size并没有改变。还有一个void addNewEntryForNullKey(V value)方法,其实和上面差不多,这个就不在叙述,我们在往下看,其中还有一个constructorNewEntry方法,他和上面也差不多,只不过他没有调用移除方法,在下面就是public V get(Object key)方法了,这个方法和HashMap的get方法差不多,只不过他多了一个判断,因为LinkedHashMap多了一个链表的维护,所以他要判断是否是按照访问顺序来维护,

if (accessOrder)
    makeTail((LinkedEntry) e);

如果是按照访问顺序来维护的就会调用makeTail方法。

    private void makeTail(LinkedEntry e) {
        // Unlink e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail
        LinkedEntry header = this.header;
        LinkedEntry oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

上面代码很好理解,就是把元素e从双向链表中删除,然后添加在header的前一个,就相当于新添加的一个,因为他是双向链表,所以断开的时候要保证他的前一个和后一个连接,不能让他断了。其中还有几个preModify和postRemove方法,都比较简单就不在介绍,我们来看一下containsValue方法

    @Override public boolean containsValue(Object value) {
        if (value == null) {
            for (LinkedEntry header = this.header, e = header.nxt;
                    e != header; e = e.nxt) {
                if (e.value == null) {
                    return true;
                }
            }
            return false;
        }

        // value is non-null
        for (LinkedEntry header = this.header, e = header.nxt;
                e != header; e = e.nxt) {
            if (value.equals(e.value)) {
                return true;
            }
        }
        return false;
    }

我们上一篇讲到HashMap的时候也说到containsKey和containsValue方法,HashMap的containsValue方法是通过遍历数组,然后在根据数组的next一个一个查找的,而LinkedHashMap的containsValue方法是遍历双向链表,从链表的header开始查找,因为是环形的,如果查找一圈还没找到则返回false。还有一个clear方法,他是先调用HashMap的clear方法把所有数据全部清除了,然后在通过循环把链表清空。剩下的就是迭代了,其中LinkedHashIterator类也是从header开始的,这里就不在详述。由于LinkedHashMap的源码很少,今天就暂时先分析到这,下一篇在分析Android中比较常用的缓存类LruCache。





推荐阅读
  • JDK源码学习之HashTable(附带面试题)的学习笔记
    本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记,包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货,并附带了其他相关主题的学习笔记。 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • 本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计,并以数字赋能和创新驱动高质量发展的理念,建设了集成、智慧、高效的一体化城市综合管理平台,促进了城市的数字化转型。该中心被称为当代城市的智能心脏,为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • 预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]
  • Whatsthedifferencebetweento_aandto_ary?to_a和to_ary有什么区别? ... [详细]
  • Spring特性实现接口多类的动态调用详解
    本文详细介绍了如何使用Spring特性实现接口多类的动态调用。通过对Spring IoC容器的基础类BeanFactory和ApplicationContext的介绍,以及getBeansOfType方法的应用,解决了在实际工作中遇到的接口及多个实现类的问题。同时,文章还提到了SPI使用的不便之处,并介绍了借助ApplicationContext实现需求的方法。阅读本文,你将了解到Spring特性的实现原理和实际应用方式。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • 个人学习使用:谨慎参考1Client类importcom.thoughtworks.gauge.Step;importcom.thoughtworks.gauge.T ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 前景:当UI一个查询条件为多项选择,或录入多个条件的时候,比如查询所有名称里面包含以下动态条件,需要模糊查询里面每一项时比如是这样一个数组条件:newstring[]{兴业银行, ... [详细]
  • Java学习笔记之面向对象编程(OOP)
    本文介绍了Java学习笔记中的面向对象编程(OOP)内容,包括OOP的三大特性(封装、继承、多态)和五大原则(单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则)。通过学习OOP,可以提高代码复用性、拓展性和安全性。 ... [详细]
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
author-avatar
jiuye
这个家伙很懒,什么也没留下!
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有