详解Java中LinkedHashMap

初识linkedhashmap

大多数情况下，只要不涉及线程安全问题，map基本都可以使用hashmap，不过hashmap有一个问题，就是迭代hashmap的顺序并不是hashmap放置的顺序，也就是无序。hashmap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的map。

这个时候，linkedhashmap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，linkedhashmap保证了元素迭代的顺序。

四个关注点在linkedhashmap上的答案

关  注  点	结      论
linkedhashmap是否允许空	key和value都允许空
linkedhashmap是否允许重复数据	key重复会覆盖、value允许重复
linkedhashmap是否有序	有序
linkedhashmap是否线程安全	非线程安全

linkedhashmap基本结构

关于linkedhashmap，先提两点：

1、linkedhashmap可以认为是hashmap+linkedlist，即它既使用hashmap操作数据结构，又使用linkedlist维护插入元素的先后顺序

2、linkedhashmap的基本实现思想就是----多态。可以说，理解多态，再去理解linkedhashmap原理会事半功倍；反之也是，对于linkedhashmap原理的学习，也可以促进和加深对于多态的理解。

为什么可以这么说，首先看一下，linkedhashmap的定义：

public class linkedhashmap<k,v>
 extends hashmap<k,v>
 implements map<k,v>
{
 ...
}

看到，linkedhashmap是hashmap的子类，自然linkedhashmap也就继承了hashmap中所有非private的方法。再看一下linkedhashmap中本身的方法：

看到linkedhashmap中并没有什么操作数据结构的方法，也就是说linkedhashmap操作数据结构（比如put一个数据），和hashmap操作数据的方法完全一样，无非就是细节上有一些的不同罢了。

linkedhashmap和hashmap的区别在于它们的基本数据结构上，看一下linkedhashmap的基本数据结构，也就是entry：

private static class entry<k,v> extends hashmap.entry<k,v> {
 // these fields comprise the doubly linked list used for iteration.
 entry<k,v> before, after;
entry(int hash, k key, v value, hashmap.entry<k,v> next) {
  super(hash, key, value, next);
 }
 ...
}

列一下entry里面有的一些属性吧：

• k key
• v value
• entry<k, v> next
• int hash
• entry<k, v> before
• entry<k, v> after

其中前面四个，也就是红色部分是从hashmap.entry中继承过来的；后面两个，也就是蓝色部分是linkedhashmap独有的。不要搞错了next和before、after，next是用于维护hashmap指定table位置上连接的entry的顺序的，before、after是用于维护entry插入的先后顺序的。

还是用图表示一下，列一下属性而已：

初始化linkedhashmap

假如有这么一段代码：

public static void main(string[] args)
{
 linkedhashmap<string, string> linkedhashmap =
   new linkedhashmap<string, string>();
 linkedhashmap.put("111", "111");
 linkedhashmap.put("222", "222");
}

首先是第3行~第4行，new一个linkedhashmap出来，看一下做了什么：

public linkedhashmap() {
 super();
  accessorder = false;
 }

 public hashmap() {
 this.loadfactor = default_load_factor;
  threshold = (int)(default_initial_capacity * default_load_factor);
  table = new entry[default_initial_capacity];
  init();
 }

void init() {
 header = new entry<k,v>(-1, null, null, null);
 header.before = header.after = header;
}

/**
 * the head of the doubly linked list.
 */
private transient entry<k,v> header;

这里出现了第一个多态：init()方法。尽管init()方法定义在hashmap中，但是由于：

1、linkedhashmap重写了init方法

2、实例化出来的是linkedhashmap

因此实际调用的init方法是linkedhashmap重写的init方法。假设header的地址是0x00000000，那么初始化完毕，实际上是这样的：

 

linkedhashmap添加元素

继续看linkedhashmap添加元素，也就是put("111","111")做了什么，首先当然是调用hashmap的put方法：

public v put(k key, v value) {
 if (key == null)
  return putfornullkey(value);
 int hash = hash(key.hashcode());
 int i = indexfor(hash, table.length);
 for (entry<k,v> e = table[i]; e != null; e = e.next) {
  object k;
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
   v oldvalue = e.value;
   e.value = value;
   e.recordaccess(this);
   return oldvalue;
  }
 }
 modcount++;
 addentry(hash, key, value, i);
 return null;
}

第17行又是一个多态，因为linkedhashmap重写了addentry方法，因此addentry调用的是linkedhashmap重写了的方法：

void addentry(int hash, k key, v value, int bucketindex) {
 createentry(hash, key, value, bucketindex);

 // remove eldest entry if instructed, else grow capacity if appropriate
 entry<k,v> eldest = header.after;
 if (removeeldestentry(eldest)) {
  removeentryforkey(eldest.key);
 } else {
  if (size >= threshold)
   resize(2 * table.length);
 }
}

因为linkedhashmap由于其本身维护了插入的先后顺序，因此linkedhashmap可以用来做缓存，第5行~第7行是用来支持fifo算法的，这里暂时不用去关心它。看一下createentry方法：

void createentry(int hash, k key, v value, int bucketindex) {
 hashmap.entry<k,v> old = table[bucketindex];
 entry<k,v> e = new entry<k,v>(hash, key, value, old);
 table[bucketindex] = e;
 e.addbefore(header);
 size++;
}

private void addbefore(entry<k,v> existingentry) {
 after = existingentry;
 before = existingentry.before;
 before.after = this;
 after.before = this;
}

第2行~第4行的代码和hashmap没有什么不同，新添加的元素放在table[i]上，差别在于linkedhashmap还做了addbefore操作，这四行代码的意思就是让新的entry和原链表生成一个双向链表。假设字符串111放在位置table[1]上，生成的entry地址为0x00000001，那么用图表示是这样的：

如果熟悉linkedlist的源码应该不难理解，还是解释一下，注意下existingentry表示的是header：

1、after=existingentry，即新增的entry的after=header地址，即after=0x00000000

2、before=existingentry.before，即新增的entry的before是header的before的地址，header的before此时是0x00000000，因此新增的entry的before=0x00000000

3、before.after=this，新增的entry的before此时为0x00000000即header，header的after=this，即header的after=0x00000001

4、after.before=this，新增的entry的after此时为0x00000000即header，header的before=this，即header的before=0x00000001

这样，header与新增的entry的一个双向链表就形成了。再看，新增了字符串222之后是什么样的，假设新增的entry的地址为0x00000002，生成到table[2]上，用图表示是这样的：

就不细解释了，只要before、after清除地知道代表的是哪个entry的就不会有什么问题。

总得来看，再说明一遍，linkedhashmap的实现就是hashmap+linkedlist的实现方式，以hashmap维护数据结构，以linklist的方式维护数据插入顺序。

利用linkedhashmap实现lru算法缓存

前面讲了linkedhashmap添加元素，删除、修改元素就不说了，比较简单，和hashmap+linkedlist的删除、修改元素大同小异，下面讲一个新的内容。

linkedhashmap可以用来作缓存，比方说lrucache，看一下这个类的代码，很简单，就十几行而已：

public class lrucache extends linkedhashmap
{
 public lrucache(int maxsize)
 {
  super(maxsize, 0.75f, true);
  maxelements = maxsize;
 }

 protected boolean removeeldestentry(java.util.map.entry eldest)
 {
  return size() > maxelements;
 }
 private static final long serialversionuid = 1l;
 protected int maxelements;
}

顾名思义，lrucache就是基于lru算法的cache（缓存），这个类继承自linkedhashmap，而类中看到没有什么特别的方法，这说明lrucache实现缓存lru功能都是源自linkedhashmap的。linkedhashmap可以实现lru算法的缓存基于两点：

1、linkedlist首先它是一个map，map是基于k-v的，和缓存一致

2、linkedlist提供了一个boolean值可以让用户指定是否实现lru

那么，首先我们了解一下什么是lru：lru即least recently used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比方说数据a，1天前访问了；数据b，2天前访问了，缓存满了，优先会淘汰数据b。

我们看一下linkedlist带boolean型参数的构造方法：

public linkedhashmap(int initialcapacity,
   float loadfactor,
      boolean accessorder) {
 super(initialcapacity, loadfactor);
 this.accessorder = accessorder;
}

就是这个accessorder，它表示：

（1）false，所有的entry按照插入的顺序排列

（2）true，所有的entry按照访问的顺序排列

第二点的意思就是，如果有1 2 3这3个entry，那么访问了1，就把1移到尾部去，即2 3 1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最头的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最头的那个数据就是要淘汰的数据。

"访问"，这个词有两层意思：

1、根据key拿到value，也就是get方法

2、修改key对应的value，也就是put方法

首先看一下get方法，它在linkedhashmap中被重写：

public v get(object key) {
 entry<k,v> e = (entry<k,v>)getentry(key);
 if (e == null)
  return null;
 e.recordaccess(this);
 return e.value;
}

然后是put方法，沿用父类hashmap的：

public v put(k key, v value) {
 if (key == null)
  return putfornullkey(value);
 int hash = hash(key.hashcode());
 int i = indexfor(hash, table.length);
 for (entry<k,v> e = table[i]; e != null; e = e.next) {
  object k;
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
   v oldvalue = e.value;
   e.value = value;
   e.recordaccess(this);
   return oldvalue;
  }
 }
 modcount++;
 addentry(hash, key, value, i);
 return null;
}

修改数据也就是第6行~第14行的代码。看到两端代码都有一个共同点：都调用了recordaccess方法，且这个方法是entry中的方法，也就是说每次的recordaccess操作的都是某一个固定的entry。

recordaccess，顾名思义，记录访问，也就是说你这次访问了双向链表，我就把你记录下来，怎么记录？把你访问的entry移到尾部去。这个方法在hashmap中是一个空方法，就是用来给子类记录访问用的，看一下linkedhashmap中的实现：

void recordaccess(hashmap<k,v> m) {
 linkedhashmap<k,v> lm = (linkedhashmap<k,v>)m;
 if (lm.accessorder) {
  lm.modcount++;
  remove();
  addbefore(lm.header);
 }
}

private void remove() {
 before.after = after;
 after.before = before;
}

private void addbefore(entry<k,v> existingentry) {
 after = existingentry;
 before = existingentry.before;
 before.after = this;
 after.before = this;
}

看到每次recordaccess的时候做了两件事情：

1、把待移动的entry的前后entry相连

2、把待移动的entry移动到尾部

当然，这一切都是基于accessorder=true的情况下。最后用一张图表示一下整个recordaccess的过程吧：

代码演示linkedhashmap按照访问顺序排序的效果

最后代码演示一下linkedlist按照访问顺序排序的效果，验证一下上一部分linkedhashmap的lru功能：

public static void main(string[] args)
{
 linkedhashmap<string, string> linkedhashmap =
   new linkedhashmap<string, string>(16, 0.75f, true);
 linkedhashmap.put("111", "111");
 linkedhashmap.put("222", "222");
 linkedhashmap.put("333", "333");
 linkedhashmap.put("444", "444");
 looplinkedhashmap(linkedhashmap);
 linkedhashmap.get("111");
 looplinkedhashmap(linkedhashmap);
 linkedhashmap.put("222", "2222");
 looplinkedhashmap(linkedhashmap);
}
 
public static void looplinkedhashmap(linkedhashmap<string, string> linkedhashmap)
{
 set<map.entry<string, string>> set = inkedhashmap.entryset();
 iterator<map.entry<string, string>> iterator = set.iterator();
 
 while (iterator.hasnext())
 {
  system.out.print(iterator.next() + "\t");
 }
 system.out.println();
}

注意这里的构造方法要用三个参数那个且最后的要传入true，这样才表示按照访问顺序排序。看一下代码运行结果：

111=111 222=222 333=333 444=444 
222=222 333=333 444=444 111=111 
333=333 444=444 111=111 222=2222 

代码运行结果证明了两点：

1、linkedlist是有序的

2、每次访问一个元素（get或put），被访问的元素都被提到最后面去了

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持!