首页 > 代码库 > Java技术之LinkedHashMap
Java技术之LinkedHashMap
在Android开发过程中，遇到需要处理大量图片显示问题时，需要运用缓存机制。而Java中已经为我们提供了很好的工具LinkedHashMap,为我们实现LRU算法提供了很大的便利。下面结合LinkedHashMap源码来了解其原理。
1.LinkedHashMap结构
LinkedHashMap继承了HashMap底层是通过Hash表+单向链表实现Hash算法，内部自己维护了一套元素访问顺序的列表。
LinkedHashMap与HashMap的区别是在于LinkeedHashMap每个元素插入表中时，就会并入到双向链表中。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。当访问顺序时，每次调用get或者put，受到影响的条目将从当前的位置删除，并放到链表条目的尾部，在这里只是链表中位置变化受到影响，而散列表中的桶不会受影响。
2.LinkedHashMap实现
2.1记录顺序
Linked内部含有一个private transient Entry header;来记录元素插入的顺序或者是元素被访问的顺序。
决定记录顺序的是由初始化时private final boolean accessOrder;
AccessOrder。默认为false,即插入顺序，true为访问顺序。
2.2构造函数
1 public LinkedHashMap(int initialCapacity,2 float loadFactor,3 boolean accessOrder) {4 super(initialCapacity, loadFactor);5 this.accessOrder = accessOrder;6 }
initialCapacity是初始化表的大小，loadFactor是装载因子，默认0.75，accessOrder是指定记录的顺序，访问顺序还是插入顺序。后面的true表明LinkedHashMap按照访问的次序来排序。按照访问的次序来排序的含义:当调用LinkedHashMap的get(key)或者put(key, value)时，碰巧key在map中被包含，那么LinkedHashMap会将key对象的entry放在线性结构的最后。按照插入顺序来排序的含义:调用get(key), 或者put(key, value)并不会对线性结构产生任何的影响。
2.3获取记录
1 public V get(Object key) {2 Entry<K,V> e = (Entry<K,V>)getEntry(key);3 if (e == null)4 return null;5 e.recordAccess(this);6 return e.value;7 }
如果key存在，执行recordAccess(this);
1 void recordAccess(HashMap<K,V> m) {2 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;3 if (lm.accessOrder) {4 lm.modCount++;5 remove();6 addBefore(lm.header);7 }8 }
recordAccess方法会accessOrder为true会先调用remove清除当前首尾元素的指向关系，之后调用addBefore方法，将当前元素加入header之前。
1 /** 2 * Removes this entry from the linked list. 3 */ 4 private void remove() { 5 before.after = after; 6 after.before = before; 7 } 8 9 /**10 * Inserts this entry before the specified existing entry in the list.11 */12 private void addBefore(Entry<K,V> existingEntry) {13 after = existingEntry;14 before = existingEntry.before;15 before.after = this;16 after.before = this;17 }
2.4获取数据
LinkedHashMap put方法时继承HashMap的put方法，但是需要重写其中的方法
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); 4 int hash = hash(key.hashCode()); 5 int i = indexFor(hash, table.length); 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue =http://www.mamicode.com/ e.value;10 e.value =http://www.mamicode.com/ value;11 e.recordAccess(this);12 return oldValue;13 }14 }15 16 modCount++;17 addEntry(hash, key, value, i);18 return null;19 }
2.5删除最久未被访问数据
1 protected boolean removeEldestEntry(Map.Entry eldest) {2 return false;3 }
LinkedHashMap中一个方法，当调用put(key, value)的时候，HashMap判断是否要自动增加map的size的作法是判断是否超过threshold， LinkedHashMap则进行了扩展，如果removeEldestEntry方法return false；（默认的实现），那么LinkedHashMap跟HashMap处理扩容的方式一致；如果removeEldestEntry返回 true，那么LinkedHashMap会自动删掉最不常用的那个entry（也就是header线性表最前面的那个）。这一特点可以很好实现缓存机制。
3.缓存机制简单实现
1 import java.util.Iterator; 2 import java.util.LinkedHashMap; 3 4 public class LRULinkedHashMap<K,V> extends LinkedHashMap<K, V>{ 5 6 private static final int INIT_CAPACITY=10; 7 private static final int MAX_SIZE=6; 8 private static final float LOAD_FACTOR=0.75f; 9 10 public LRULinkedHashMap() {11 super(INIT_CAPACITY, LOAD_FACTOR, true);12 }13 14 @Override15 protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {16 return size()>MAX_SIZE;17 }18 19 public static void main(String[] args) {20 21 LRULinkedHashMap<String, String> lruLinkedHashMap=new LRULinkedHashMap<String,String>();22 lruLinkedHashMap.put("1", "A");23 lruLinkedHashMap.put("2", "B");24 lruLinkedHashMap.put("3", "C");25 lruLinkedHashMap.put("4", "D");26 lruLinkedHashMap.put("5", "E");27 lruLinkedHashMap.put("6", "F");28 lruLinkedHashMap.put("7", "G");29 lruLinkedHashMap.put("8", "H");30 lruLinkedHashMap.put("9", "I");31 lruLinkedHashMap.put("10", "J");32 lruLinkedHashMap.put("11", "K");33 Iterator<String> iterator=lruLinkedHashMap.keySet().iterator();34 while(iterator.hasNext()){35 System.out.print(iterator.next()+" ");36 }37 }38 39 }
结果显示：
6 7 8 9 10 11