LinkedHashMap接口.docVIP

LinkedHashMap接口 一、类继承关系 [java] view plain copy 在CODE上查看代码片派生到我的代码片 public class LinkedHashMapK,V extends HashMapK,V implements MapK,V 二、LinkedHashMap接口特点 与HashMap的异同：同样是基于散列表实现， 区别是LinkedHashMap内部多了一个双向循环链表的维护，该链表是有序，可以按元素插入顺序或元素最近访问顺序(LRU)排列 简单地说：LinkedHashMap=散列表+循环双向链表，能够保持遍历的顺序和插入的顺序一致。 总结： 1.LinkedHashMap继承自HashMap，具有HashMap的大部分特性， 比如支持null键和值，默认容量为16，装载因子为0.75， 非线程安全等等； 改为同步： * Map m = Collections.synchronizedMap(new LinkedHashMap()); 2.LinkedHashMap通过设置accessOrder控制遍历顺序是按照插入顺序还是按照访问顺序。 当accessOrder为true时，可以利用其完成LRU缓存的功能； 3.LinkedHashMap内部维护了一个双向循环链表，并且其迭代操作时通过链表完成的，而不是去遍历hash表。 4 增加了维护链接列表的开支，性能比HashMap稍逊； 三、内部结构 第一张图是LinkedHashMap的全部数据结构，包含散列表和循环双向链表； 左边的红色箭头引用为Entry节点对象的next引用(散列表中的单链表)， 绿色线条为Entry节点对象的before, after引用(循环双向链表的前后引用)； 由图可知：LinkedHashMa在遍历的时候直接遍历双向循环链； 第二张图专门把循环双向链表抽取出来，直观一点，注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口； 四、源码分析 1 与HashMap不同之处的两个重要属性。 LinkedHashMap比HashMap多了两个成员变量，其中header代表内部双向链表的头结点，后面我们就会发现，LinkedHashMap除了有个桶数组 容纳所有Entry之外，还有一个双向链表保存所有Entry引用。遍历的时候，并不是去遍历桶数组，而是直接遍历双向链表，所以LinkedHashMap的遍历 时间不受桶容量的限制，这是它和HashMap的重要区别之一。 而这个accessOrder代表的是是否按照访问顺序，true代表是，默认是插入顺序。所以我们可以将accessOrder置为true来实现LRU算法， 这可以用来做缓存。 [java] view plain copy 在CODE上查看代码片派生到我的代码片 //双向循环链表的头结点 private transient EntryK,V header; //accessOrder代表链表的排序方式；true为按照访问顺序，false为插入顺序。 private final boolean accessOrder; 2 构造器 [java] view plain copy 在CODE上查看代码片派生到我的代码片 //按指定的初始化容量和加载因子，生成一个空的LinkedHashMap， 默认将accessOrder设为false，按插入顺序排序. public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;//默认设为插入顺序 } //按指定初始化容量，生成一个LinkedHashMap构造器；默认加载因子为0.75 默认将accessOrder设为false，按插入顺序排序. public LinkedHashMap(int initialCapacity) { super(initialCapacity); acce