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

LinkedHashMap已经为我们自己实现LRU算法提供了便利。
LinkedHashMap继承了HashMap底层是通过Hash表+单向链表实现Hash算法,内部自己维护了一套元素访问顺序的列表。

  1. /**
  2.   * The head of the doubly linked list.
  3.   */
  4.  private transient Entry<K,V> header;
  5.  …..
  6. /**
  7.   * LinkedHashMap entry.
  8.   */
  9.  private static class Entry<K,V> extends HashMap.Entry<K,V> {
  10.      // These fields comprise the doubly linked list used for iteration.
  11.      Entry<K,V> before, after;

HashMap构造函数中回调了子类的init方法实现对元素初始化

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

LinkedHashMap中有一个属性可以执行列表元素的排序算法

  1. /**
  2.   * The iteration ordering method for this linked hash map: <tt>true</tt>
  3.   * for access-order, <tt>false</tt> for insertion-order.
  4.   *
  5.   * @serial
  6.   */
  7.  private final boolean accessOrder;

注释已经写的很明白,accessOrder为true使用访问顺序排序,false使用插入顺序排序那么在哪里可以设置这个值。

  1. /**
  2.   * Constructs an empty <tt>LinkedHashMap</tt> instance with the
  3.   * specified initial capacity, load factor and ordering mode.
  4.   *
  5.   * @param  initialCapacity the initial capacity.
  6.   * @param  loadFactor      the load factor.
  7.   * @param  accessOrder     the ordering mode – <tt>true</tt> for
  8.   *         access-order, <tt>false</tt> for insertion-order.
  9.   * @throws IllegalArgumentException if the initial capacity is negative
  10.   *         or the load factor is nonpositive.
  11.   */
  12.  public LinkedHashMap(int initialCapacity,
  13.  float loadFactor,
  14.                       boolean accessOrder) {
  15.      super(initialCapacity, loadFactor);
  16.      this.accessOrder = accessOrder;
  17.  }

那么我们就行有访问顺序排序方式实现LRU,那么哪里LinkedHashMap是如何实现LRU的呢?

  1.    //LinkedHashMap方法
  2.    public V get(Object key) {
  3.        Entry<K,V> e = (Entry<K,V>)getEntry(key);
  4.        if (e == null)
  5.            return null;
  6.        e.recordAccess(this);
  7.        return e.value;
  8.    }
  9.    //HashMap方法
  10.    public V put(K key, V value) {
  11. if (key == null)
  12.     return putForNullKey(value);
  13.        int hash = hash(key.hashCode());
  14.        int i = indexFor(hash, table.length);
  15.        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  16.            Object k;
  17.            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  18.                V oldValue = e.value;
  19.                e.value = value;
  20.                e.recordAccess(this);
  21.                return oldValue;
  22.            }
  23.        }
  24.        modCount++;
  25.        addEntry(hash, key, value, i);
  26.        return null;
  27.    }

当调用get或者put方法的时候,如果K-V已经存在,会回调Entry.recordAccess()方法
我们再看一下LinkedHashMap的Entry实现

  1. /**
  2.   * This method is invoked by the superclass whenever the value
  3.   * of a pre-existing entry is read by Map.get or modified by Map.set.
  4.   * If the enclosing Map is access-ordered, it moves the entry
  5.   * to the end of the list; otherwise, it does nothing. 
  6.   */
  7.  void recordAccess(HashMap<K,V> m) {
  8.      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  9.      if (lm.accessOrder) {
  10.          lm.modCount++;
  11.          remove();
  12.          addBefore(lm.header);
  13.      }
  14.  }
  15.  /**
  16.   * Remove this entry from the linked list.
  17.   */
  18.  private void remove() {
  19.      before.after = after;
  20.      after.before = before;
  21.  }
  22.  /**                                             
  23.   * Insert this entry before the specified existing entry in the list.
  24.   */
  25.  private void addBefore(Entry<K,V> existingEntry) {
  26.      after  = existingEntry;
  27.      before = existingEntry.before;
  28.      before.after = this;
  29.      after.before = this;
  30.  }

recordAccess方法会accessOrder为true会先调用remove清楚的当前首尾元素的指向关系,之后调用addBefore方法,将当前元素加入header之前。

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

  1.   /**
  2.     * This override alters behavior of superclass put method. It causes newly
  3.     * allocated entry to get inserted at the end of the linked list and
  4.     * removes the eldest entry if appropriate.
  5.     */
  6.    void addEntry(int hash, K key, V value, int bucketIndex) {
  7.        createEntry(hash, key, value, bucketIndex);
  8.        // Remove eldest entry if instructed, else grow capacity if appropriate
  9.        Entry<K,V> eldest = header.after;
  10.        if (removeEldestEntry(eldest)) {
  11.            removeEntryForKey(eldest.key);
  12.        } else {
  13.            if (size >= threshold)
  14.                resize(2 * table.length);
  15.        }
  16.    }
  17.    /**
  18.     * This override differs from addEntry in that it doesn’t resize the
  19.     * table or remove the eldest entry.
  20.     */
  21.    void createEntry(int hash, K key, V value, int bucketIndex) {
  22.        HashMap.Entry<K,V> old = table[bucketIndex];
  23. Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
  24.        table[bucketIndex] = e;
  25.        e.addBefore(header);
  26.        size++;
  27.    }
  28.    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  29.        return false;
  30.    }

基本的原理已经介绍完了,那基于LinkedHashMap我们看一下是该如何实现呢?

  1. public static class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
  2.         /** serialVersionUID */
  3.         private static final long serialVersionUID = -5933045562735378538L;
  4.         /** 最大数据存储容量 */
  5.         private static final int  LRU_MAX_CAPACITY     = 1024;
  6.         /** 存储数据容量  */
  7.         private int               capacity;
  8.         /**
  9.          * 默认构造方法
  10.          */
  11.         public LRULinkedHashMap() {
  12.             super();
  13.         }
  14.         /**
  15.          * 带参数构造方法
  16.          * @param initialCapacity   容量
  17.          * @param loadFactor        装载因子
  18.          * @param isLRU             是否使用lru算法,true:使用(按方案顺序排序);false:不使用(按存储顺序排序)
  19.          */
  20.         public LRULinkedHashMap(int initialCapacity, float loadFactor, boolean isLRU) {
  21.             super(initialCapacity, loadFactor, true);
  22.             capacity = LRU_MAX_CAPACITY;
  23.         }
  24.         /**
  25.          * 带参数构造方法
  26.          * @param initialCapacity   容量
  27.          * @param loadFactor        装载因子
  28.          * @param isLRU             是否使用lru算法,true:使用(按方案顺序排序);false:不使用(按存储顺序排序)
  29.          * @param lruCapacity       lru存储数据容量       
  30.          */
  31.         public LRULinkedHashMap(int initialCapacity, float loadFactor, boolean isLRU, int lruCapacity) {
  32.             super(initialCapacity, loadFactor, true);
  33.             this.capacity = lruCapacity;
  34.         }
  35.         /** 
  36.          * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
  37.          */
  38.         @Override
  39.         protected boolean removeEldestEntry(Entry<K, V> eldest) {
  40.             System.out.println(eldest.getKey() + “=” + eldest.getValue());
  41.             if(size() > capacity) {
  42.                 return true;
  43.             }
  44.             return false;
  45.         }
  46.     }

测试代码:

  1. public static void main(String[] args) {
  2.     LinkedHashMap<String, String> map = new LRULinkedHashMap<String, String>(160.75f, true);
  3.     map.put(“a”“a”); //a  a
  4.     map.put(“b”“b”); //a  a b
  5.     map.put(“c”“c”); //a  a b c
  6.     map.put(“a”“a”); //   b c a     
  7.     map.put(“d”“d”); //b  b c a d
  8.     map.put(“a”“a”); //   b c d a
  9.     map.put(“b”“b”); //   c d a b     
  10.     map.put(“f”“f”); //c  c d a b f
  11.     map.put(“g”“g”); //c  c d a b f g
  12.     map.get(“d”); //c a b f g d
  13.     for (Entry<String, String> entry : map.entrySet()) {
  14.         System.out.print(entry.getValue() + “, “);
  15.     }
  16.     System.out.println();
  17.     map.get(“a”); //c b f g d a
  18.     for (Entry<String, String> entry : map.entrySet()) {
  19.         System.out.print(entry.getValue() + “, “);
  20.     }
  21.     System.out.println();
  22.     map.get(“c”); //b f g d a c
  23.     for (Entry<String, String> entry : map.entrySet()) {
  24.         System.out.print(entry.getValue() + “, “);
  25.     }
  26.     System.out.println();
  27.     map.get(“b”); //f g d a c b
  28.     for (Entry<String, String> entry : map.entrySet()) {
  29.         System.out.print(entry.getValue() + “, “);
  30.     }
  31.     System.out.println();
  32.     map.put(“h”“h”); //f  f g d a c b h
  33.     for (Entry<String, String> entry : map.entrySet()) {
  34.         System.out.print(entry.getValue() + “, “);
  35.     }
  36.     System.out.println();
  37. }

运行结果:
a=a
a=a
a=a
b=b
c=c
c=c
c, a, b, f, g, d,
c, b, f, g, d, a,
b, f, g, d, a, c,
f, g, d, a, c, b,
f=f
f, g, d, a, c, b, h,

插入时entry变化如下图:

2ac8ad47ececb43627b1ea852b8aefad

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s