【算法】FIFO先来先淘汰算法分析和编码实战

• 背景

  • 在设计一个系统的时候，由于数据库的读取速度远小于内存的读取速度

  • 为加快读取速度，将一部分数据放到内存中称为缓存，但内存容量是有限的，当要缓存的数据超出容量，就需要删除部分数据

  • 这时候需要设计一种淘汰机制，看哪些数据删除，哪些数据保留

  • 常见的有FIFO、LRU、LFU等淘汰算法

• 什么是FIFO淘汰算法

  • First In First Out，先进先出，淘汰最早被缓存的对象
  • 是一种常用的缓存淘汰算法，它的原理是按照先进先出的原则
  • 当缓存满了之后，先将最早进入缓存的数据淘汰掉，以腾出空间给新的数据
  • 优点
    • 在于实现简单，不需要记录或统计数据的使用次数，只需要记录每个数据进入缓存的时间和每个数据在缓存中的位置即可
  • 缺点
    • 在于它不能有效地淘汰最近最少使用的数据
    • 最近最少使用的数据可能会被淘汰掉，而最近最多使用的数据也可能被淘汰掉，这样就会导致缓存的效率不够高。
      

• 编码实现

public class FIFOCache <K,V>{//定义缓存最大容量private int maxSize;//定义当前缓存容量private int curSize;//定义用鱼存放缓存的keyprivate LinkedList<K> cacheKey;//用于存放缓存的valueprivate HashMap<K,V> cacheValue;//读写锁，保证线程安全性private Lock lock = new ReentrantLock();//构造函数public FIFOCache(int maxSize) {this.maxSize = maxSize;this.curSize = 0;this.cacheKey = new LinkedList<K>();this.cacheValue = new HashMap<K, V>();}//向缓存中插入key-valuepublic void put(K key,V value){//加锁lock.lock();try {//如果缓存已满，则删除最老的keyif (maxSize == curSize) {K oldKey = cacheKey.removeFirst();cacheValue.remove(oldKey);curSize--;}//插入新的key-valuecacheKey.add(key);cacheValue.put(key,value);curSize++;}finally {//解锁lock.unlock();}}// 查询指定key的valuepublic V get(K key) {return cacheValue.get(key);}public void printKeys() {System.out.println(this.cacheKey.toString());}public static void main(String[] args) {FIFOCache<String,String> cache = new FIFOCache<>(5);cache.put("A", "任务A");cache.put("B", "任务B");cache.put("C", "任务C");cache.put("D", "任务D");cache.put("E", "任务E");cache.printKeys();cache.put("F", "任务F");cache.printKeys();System.out.println("G=" + cache.get("G"));System.out.println("C=" + cache.get("C"));}}