LRU与LRU-K算法实现

2019/05/01 算法

LRU与LRU-K算法实现

LRU

LRU是Least Recently Used的缩写,即最近最少使用,常用于页面置换算法,是为虚拟页式存储管理服务的。

一种简单的实现方法:

利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

LinkedHashMap底层就是用的HashMap加双链表实现的,而且本身已经实现了按照访问顺序的存储。此外,LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数,方法默认是直接返回false,不会移除元素,所以需要重写该方法。即当缓存满后就移除最不常用的数。

public class LRU<K,V> {
 
  private static final float hashLoadFactory = 0.75f;
  private LinkedHashMap<K,V> map;
  private int cacheSize;
 
  public LRU(int cacheSize) {
    this.cacheSize = cacheSize;
    int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1;
    map = new LinkedHashMap<K,V>(capacity, hashLoadFactory, true){
      private static final long serialVersionUID = 1;
 
      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > LRU.this.cacheSize;
      }
    };
  }
 
  public synchronized V get(K key) {
    return map.get(key);
  }
 
  public synchronized void put(K key, V value) {
    map.put(key, value);
  }
 
  public synchronized void clear() {
    map.clear();
  }
 
  public synchronized int usedSize() {
    return map.size();
  }
 
  public void print() {
    for (Map.Entry<K, V> entry : map.entrySet()) {
      System.out.print(entry.getValue() + "--");
    }
    System.out.println();
  }
}
  • 上述实现存在的问题:缓存污染(会将不常用的数据移到缓存,降低缓存效率)
  • 解决办法LRU-K

LRU-K

LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。

public class LRUK<K, V> {

    private static final float hashLoadFactory = 0.75f;
    private ArrayList<History> histories;
    private LinkedHashMap<K, V> map;
    private int cacheSize, historyLength;
    private final int K_COUNT = 2; //进入缓存的计数要求

    public LRUK(int historyLength, int cacheSize) {
        this.historyLength = historyLength;
        this.cacheSize = cacheSize;
        histories = new ArrayList<>(historyLength);
        int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
        map = new LinkedHashMap(capacity, hashLoadFactory, true) {
            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > LRUK.this.cacheSize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized boolean moveToCache(K key) {
        int hashCode = key.hashCode();
        if (inHistory(hashCode)) {
            return modifyHistory(hashCode);
        } else {
            History history = new History();
            history.setHash(hashCode);
            history.setTimes(1);

            histories.add(history);
            return false;
        }
    }

    private boolean modifyHistory(int objectHash) {
        for (History item : histories) {
            if (item.getHash() != objectHash) {
                continue;
            }

            if (item.getTimes() + 1 < K_COUNT) {
                item.setTimes(item.getTimes() + 1);
                histories.remove(item);
                histories.add(item);
                return false;
            }
            histories.remove(item);
            return true;
        }
        return false;
    }

    private boolean inHistory(int objectHash) {
        for (History item : histories) {
            if (item.getHash() == objectHash) {
                return true;
            }
        }
        return false;
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    private void sortOutHistory() {
        histories.remove(0);
    }

    public synchronized void clear() {
        map.clear();
    }

    public synchronized int usedSize() {
        return map.size();
    }

    public void print() {
        for (Map.Entry<K, V> entry : map.entrySet()) {
            System.out.print(entry.getValue() + "--");
        }
        System.out.println();
    }

    class History {
        private int hash; // 资源Hash值

        private int times; // 使用次数

        public int getHash() {
            return hash;
        }

        public void setHash(int hash) {
            this.hash = hash;
        }

        public int getTimes() {
            return times;
        }

        public void setTimes(int times) {
            this.times = times;
        }

    }

}

Search

    Table of Contents