LinkedHashMap和HashMap

先看一段代码：

代码1：

public class TestLinkedHashMap {
    public static void main(String args[])
      {
       System.out.println("*************************LinkedHashMap*************");
       Map<Integer,String> map = new LinkedHashMap<Integer,String>();
       map.put(6, "apple");
       map.put(3, "banana");
       map.put(2,"pear");
       
       for (Iterator it =  map.keySet().iterator();it.hasNext();)
       {
        Object key = it.next();
        System.out.println( key+"="+ map.get(key));
       }
       
       System.out.println("*************************HashMap*************");
       Map<Integer,String> map1 = new  HashMap<Integer,String>();
       map1.put(6, "apple");
       map1.put(3, "banana");
       map1.put(2,"pear");
       
       for (Iterator it =  map1.keySet().iterator();it.hasNext();)
       {
        Object key = it.next();
        System.out.println( key+"="+ map1.get(key));
       }
      }
}

运行结果

*************************LinkedHashMap*************
6=apple
3=banana
2=pear
*************************HashMap*************
2=pear
3=banana
6=apple

分析:LinkedHashmap 的特点是put进去的对象位置未发生变化,而HashMap会发生变化.

代码2：

public class TestLinkedHashMap {
    
    public static void main(String args[])
    {
     System.out.println("*************************LinkedHashMap*************+accessOrder="+false);
     Map<Integer,String> map = new LinkedHashMap<Integer,String>(32,0.75f,false);
     map.put(6, "apple");
     map.put(3, "banana");
     map.put(2,"pear");
     map.get(6);
     map.get(3);
     
      System.out.println( map);
     
     System.out.println("*************************LinkedHashMap*************accessOrder=="+true);
     Map<Integer,String> map1 = new  LinkedHashMap<Integer,String>(32,0.75f,true);
     map1.put(6, "apple");
     map1.put(3, "banana");
     map1.put(2,"pear");
     map1.get(6);
     map1.get(3);
     
     System.out.println( map1);
    }
    
}

结果

*************************LinkedHashMap*************+accessOrder=false
{6=apple, 3=banana, 2=pear}
*************************LinkedHashMap*************accessOrder==true
{2=pear, 6=apple, 3=banana}

分析

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；
initialCapacity   初始容量
loadFactor    加载因子，一般是 0.75f
accessOrder   false 基于插入顺序 true 基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最近最少被使用的调度算法）

1.关于Hash
一般翻译做“散列”，也有译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出。简单的说，就是hashcode = hash(key),这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，在查找的时候也能提高效率。
Hashtables（哈希表）在计算机领域中已不是一个新概念了。它们是用来加快计算机的处理速度的，用当今的标准方法来处理，速度非常慢，而它们可以让你在查询许多数据条目时，很快地找到一个特殊的条目。尽管现代的机器速度已快了几千倍，但是为了得到应用程序的最佳性能，hashtables仍然是个很有用的方法。
设想一下，你有一个包含约一千条记录的数据文件。比如一个小企业的客户记录还有一个程序，它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的，所以，如果程序要将客户号作为“key” 来查找一个特殊的客户记录，唯一的查找方法就是连续地搜索每个记录。有时侯，它会很快找到你需要的记录；但有时侯，在程序找到你需要的记录前，它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索，那么查找任何一条记录都需要程序平均查核500.5 ((1000 + 1 )/2)条记录。如果你常需要查找数据，你应该需要一个更快的方法来找到一条记录。
一种加快搜索的方法就是把记录分成几段，这样，你就不用搜索一个很大的列表了，而是搜索几个短的列表。对于我们数字式的客户ID号，你可以建10个列表。以0开头的ID号组成一个列表，以1开头的ID号组成一个列表，依此类推。那么要查找客户ID号38016，你只需要搜索以3开头的列表就行了。如果有1,000条记录，每个列表的平均长度为100（1,000条记录被分成10个列表），那么搜索一条记录的平均比较次数就降到了约50（见图1）。
当然，如果约十分之一的客户号是以0开头的，另外十分之一是以1开头的，等等，那么这种方法会很适合。如果90%的客户号以0开头，那么那个列表就会有900条记录，每次查找平均需要进行450次比较。另外，程序需要执行的搜索有90%都是针对以0开头的号码的。因此，平均比较数就大大超过简单数学运算的范围了。
如果我们可以按这样一种方式在我们的列表中分配记录，情况就会好一些，即每个列表约有相同条目的记录，而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如，我们可以取号码中的每位数，乘以某个大的数（随着数字位置的不同而不同），然后将结果相加产生一个总数，把这个数除以10，并将余数作为列表索引值（index）。当读入记录时，程序在客户号码上运行这个哈希（hash) 函数来确定记录属于哪个列表。当用户需要查询时，将同一个哈希函数作为一个“key”用于客户号码，这样就可以搜索正确的列表了。像这样的一个数据结构就称为一个哈希表（hashtable)。

2.Hashmap的原理
要知道hashmap是什么，首先要搞清楚它的数据结构，在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。java的Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“）。
java的hashmap是用一个key和value的模式来存取数据，但是本质上，它还是存储在一个数组里面，过程是这样的：首先得到key的hashcode，然后通过index=hashcode%size，得到数组的索引，然后把相应的entry放进数组中。请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）。

从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组。
让我们来看看java代码：

1 /** * The table, resized as necessary. Length MUST Always be a power of two. * 这里需要注意这句话，至于原因后面会讲到 */

 transient Entry[] table;
2 static class Entry<K,V> implements Map.Entry<K,V> { 
   final K key; 
   V value;
   Entry<K,V> next;
   final int hash; 
   ……
 }

上面的Entry就是数组中的元素，它持有一个指向下一个元素的引用，这就构成了链表。
当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。只要满足这两个基本的要求，key和value可以是任何对象。注意，因为key和value必须是对象，所以原始类型（primitive types）必须通过运用诸如Integer(int)的方法转换成对象。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的，但是理想总是美好的，现实总是有困难需要我们去克服，哈哈~

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中时这样做的:

/** * Returns index for hash code h. */ 

static int indexFor(int h, int length) 
{
 return h & (length-1);
 }

首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和24-1做“与”运算。很多人都有这个疑问，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！

所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：


 1 public HashMap(int initialCapacity, float loadFactor) {
 2     if (initialCapacity < 0)
 3        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); 
 4    if (initialCapacity > MAXIMUM_CAPACITY)
 5       initialCapacity = MAXIMUM_CAPACITY; 
 6   if (loadFactor <= 0 || Float.isNaN(loadFactor))
 7     throw new IllegalArgumentException("Illegal load factor: " + loadFactor); 
 8 // Find a power of 2 >= initialCapacity
 9  // 重点代码 int capacity = 1; 
10 while (capacity < initialCapacity) 
11 capacity <<= 1; 
12 this.loadFactor = loadFactor; 
13 threshold = (int)(capacity * loadFactor);
14  table = new Entry[capacity]; init(); 
}

另外为了将一个特定类的对象用做一个key，这个类必须提供两个方法，equals() 和 hashCode()。这两个方法在java.lang.Object中，所以所有的类都可以继承这两个方法；但是，这两个方法在Object类中的实现一般没什么用，所以你通常需要自己重载这两个方法:


1 public native int hashCode();
 public boolean equals(Object obj) {
  return (this == obj); 
}

hashCode方法的定义用到了native关键字，表示它是由C或C++采用较为底层的方式来实现的，你可以认为它返回了该对象的内存地址；equals()方法把它的对象同另一个对象进行比较，如果这两个对象代表相同的信息，则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象，则Object.equals()返回true，这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下，你需要一个方法来一个字段一个字段地进行比较，因为我们认为代表相同数据的不同对象是相等的。
例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等,还可以根据名称、年龄和性别来判定两个user是否相等。
在改写equals方法的时候，需要满足以下三点:
自反性：就是说a.equals(a)必须为true。
对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。
通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
作为例子，我们可以查看一下String 类，因为它有自己的方法来实现这两个方法。String.equals()对两个String对象一个字符一个字符地进行比较，如果字符串是相同的，则返回true：
Equals代码:


1 public boolean equals(Object anObject) { 
if (this == anObject) { return true; } 
if (anObject instanceof String) { 
String anotherString = (String)anObject; 
int n = count; 
if (n == anotherString.count) { 
    char v1[] = value; char v2[] = anotherString.value;
     int i = offset; int j = anotherString.offset;
     while (n-- != 0) { 
     if (v1[i++] != v2[j++]) return false;
      } return true;
 }
 } 
return false;
 }

hashCode代码:

1 public int hashCode() { 
int h = hash; 
if (h == 0) {
     int off = offset; 
     char val[] = value;
     int len = count; 
     for (int i = 0; i < len; i++){ 
         h = 31*h + val[off++];
       } 
     hash = h;
 } 
return h;
}

String.hashCode()在一个字符串上运行哈希函数。字符串中每个字符的数字代码都乘以31，结果取决于字符串中字符的位置。然后将这些计算的结果相加，得到一个总数。这个过程似乎很复杂，但是它确保能够更好地分布值。它也证明了你在开发你自己的hashCode()方法时，能够走多远，确信结果是唯一的。
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容

以下转自

http://uule.iteye.com/blog/1522291

LinkedHashMap

1. LinkedHashMap概述：

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。

   LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
   LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
   注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。

默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。

2. LinkedHashMap的实现：

对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：

类结构：

Java代码

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>

1) 成员变量：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：

Java代码

//true表示按照访问顺序迭代，false时表示按照插入顺序
private final boolean accessOrder;

/**
* 双向链表的表头元素。
*/
private transient Entry<K,V> header;
/**
* LinkedHashMap的Entry元素。
* 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
}

HashMap.Entry:

Java代码

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}

2) 初始化：

通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：

Java代码

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

HashMap中的相关构造方法：

Java代码

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}

我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。
LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。

Java代码

void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}

3) 存储：

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

HashMap.put:

Java代码

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;
}

重写方法：

Java代码

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

void addEntry(int hash, K key, V value, int bucketIndex) {
// 调用create方法，将新元素以双向链表的的形式加入到映射中。
createEntry(hash, key, value, bucketIndex);
// 删除最近最少使用元素的策略定义
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}

Java代码

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;
// 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。
e.addBefore(header);
size++;
}

Java代码

private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

4) 读取：

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

HashMap.containsValue:

Java代码

public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}

Java代码

/*查找Map中是否包含给定的value，还是考虑到，LinkedHashMap拥有的双链表，在这里Override是为了提高迭代的效率。
*/
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}

Java代码

/*该transfer()是HashMap中的实现：遍历整个表的各个桶位，然后对桶进行遍历得到每一个Entry，重新hash到newTable中，
//放在这里是为了和下面LinkedHashMap重写该法的比较，
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
*/
/**
*transfer()方法是其父类HashMap调用resize()的时候调用的方法，它的作用是表扩容后，把旧表中的key重新hash到新的表中。
*这里从写了父类HashMap中的该方法，是因为考虑到，LinkedHashMap拥有的双链表，在这里Override是为了提高迭代的效率。
*/
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K, V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}

Java代码

public V get(Object key) {
// 调用父类HashMap的getEntry()方法，取得要查找的元素。
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 记录访问顺序。
e.recordAccess(this);
return e.value;
}

Java代码

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果定义了LinkedHashMap的迭代顺序为访问顺序，
// 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

Java代码

/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}

Java代码

/**clear链表，设置header为初始状态*/
public void clear() {
super.clear();
header.before = header.after = header;
}

5) 排序模式：

LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。

Java代码

private final boolean accessOrder;

一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：

Java代码

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：

Java代码

public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

当有新元素加入Map的时候会调用Entry的addEntry方法，会调用removeEldestEntry方法，这里就是实现LRU元素过期机制的地方，默认的情况下removeEldestEntry方法只返回false表示元素永远不过期。

Java代码

/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
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);
}
}
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
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++;
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}

此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。

例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。

Java代码

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}

来源：http://zhangshixi.iteye.com/blog/673789

参考：http://hi.baidu.com/yao1111yao/blog/item/3043e2f5657191f07709d7bb.html

部分修改。

使用LinkedHashMap构建LRU的Cache

http://tomyz0223.iteye.com/blog/1035686

基于LinkedHashMap实现LRU缓存调度算法原理及应用

http://woming66.iteye.com/blog/1284326

其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry<K,V> header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry<K,V>,并添加两个属性Entry<K,V> before,after,和header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。