• 目录:

    读 LinkedHashMap


    别人那边听到的 Map

    最开始,在网上的安卓教学视频里看到了别人用 Map,这是第一次见到这东西。当时只知道跟着敲代码。
    后来,在马士兵的java视频里第一次算是系统的学到了 Map。
    再后来,自己写的代码里 Map成为了最常用也是最好用的一种数据结构。
    最常用的,是第一次跟着视频敲的 HashMap。然后,因为程序需要,用过 ConcurrentMap, 还有一个弱引用的 Map。。但都只是看别人用自己也用。。

    现在,毕业了,入职了。。。再也不是自己一个人玩编程了。有人带了。相对系统地知道了几个 Map。

    • HashMap 把元素放到对应hash值的桶里。桶里的放的不是单个元素,而是一个列表,以此应付 hash 重复的情况。
    • LinkedMap 最开始他们简介的时候,只提到了它会保留元素put 的先后顺序。详细的介绍以及它的另一种顺序。是这篇文章的主要内容。
    • TreeMap 传说是用红黑树实现的,(红黑树是什么。。。)是按键排序的。

    亲眼看见的Map

    今天看了LinkedHashMap的源代码。五百行左右,不算很长。主要看到了这么个东西:它有两种排序模式。第一种按插入的顺序排,第二种按使用的时间排(传说这个叫 LRU,不太懂。。)。

    按插入顺序排序

    为了实现顺序,在正常的HashMap的基础上,它多了一个双向链表。这个链表是环状的。有一个初始节点head,它的初始前后节点都指向它自己。
    每次插入新的数据,都插在head节点的前一个位置。这样就留住了插入的先后顺序。

    按使用时间排序

    有一个构造方法,可以设置 accessOrder 的值。如果这个值为 True,在每次get操作的时候会多执行一个步骤:把 get 的这个节点移到 head 节点的前一个位置。
    这样就做到了最近使用的和新插入的都集中在 head 节点前面,从 head 节点往后数就是最不常用的节点。

    控制 Map 的大小

    重写 removeEldestEntry 方法,让它返回 Ture,能让Map在每次添加节点的时候,删除 head 后面的那个节点。按源码注释里说到的,自己规定个大小,如果 Map 的 size()大于这个值,就让 removeEldestEntry 返回 True。就能限制 Map 的大小。