feling.net/_posts/2015-07-23-scr-java-LinkedHashMap.md

layout	title	categories
pages	读 LinkedHashMap	Java

别人那边听到的 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 的大小。

• 文章目录 {:toc}