10.LRU缓存

面试题 16.25. LRU缓存

难度中等18

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4</pre>

import java.util.Iterator;
import java.util.LinkedList;

class LRUCache {
    int capacity;
    LinkedList<Integer> usedlist=new LinkedList();
    LinkedList[] bracket;

    //若链表包含key,则删除并在末尾追加，否则直接追加,若找到，则返回true,否则返回false
    public boolean updateList(LinkedList<Integer> list,int key){
        boolean found=false;
        Iterator<Integer> it=list.iterator();
        while(it.hasNext()){
            if(it.next()==key){
                found=true;
                it.remove();
                break;
            }
        }
        list.add(key);
        return found;
    }
    public LRUCache(int capacity) {
        this.capacity=capacity;
        bracket=new LinkedList[capacity];
        for(int i=0;i<capacity;i++){
            bracket[i]=new LinkedList<int[]>();
        }
    }
    
    public int get(int key) {
        boolean found=false;
        Iterator<Integer> it=usedlist.iterator();
        while(it.hasNext()){
            if(it.next()==key){
                found=true;
                it.remove();
                break;
            }
        }

        int result=-1;
        if(found){
            usedlist.add(key);
            int hashKey=key%capacity;
            LinkedList<int[]> list=bracket[hashKey];
            for(int[] entry : list){
                if(entry[0]==key){
                    result=entry[1];
                    break;
                }
            }
        }
        
        return result;
    }
    
    public void put(int key, int value) {
        //判断是否是更新
        boolean isUpdate=false;
        Iterator<Integer> it=usedlist.iterator();
        while(it.hasNext()){
            if(it.next()==key){
                isUpdate=true;
                break;
            }
        }

        int hashKey=key%capacity;
        if(isUpdate){//若是更新，则不需要判断空间是否溢出
            LinkedList<int[]> list=bracket[hashKey];
            for(int[] entry : list){
                if(entry[0]==key){
                    entry[1]=value;
                    break;
                }
            }
        }else{//先判断是否是溢出，做出相应处理之后然后再插入
            if(usedlist.size()==capacity){
                int removeKey=usedlist.removeFirst();
                Iterator<int[]> it2=bracket[removeKey%capacity].iterator();
                while(it2.hasNext()){
                    if(it2.next()[0]==removeKey){
                        it2.remove();
                        break;
                    }
                }
            }
            //直接在对应位置插入
            bracket[key%capacity].add(new int[]{key,value});
            
        }
        
        updateList(usedlist, key); //更新使用链
    }

    public static void main(String[] args) {
        LRUCache cache=new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}