读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 的大小。