Q200510-03-02: LRU缓存机制

问题: LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

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

代码:

package test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class ChItem{
    public ChItem(int key,int value) {
        this.key=key;
        this.value=value;
    }
    
    int key;
    int value;
}
public class LruCache2 {
    private List<ChItem> dataList;
    private int size;
    
    public LruCache2(int capacity) {
        this.size=capacity;
        dataList = new ArrayList<ChItem>();
    }
    
    public int get(int key) {
        int retval=-1;
        
        Iterator<ChItem> iterator = dataList.iterator();
        while(iterator.hasNext()) {
            ChItem item=iterator.next();
            
            if(item.key==key) {
                retval=item.value;
                dataList.remove(item);
                break;
            }
        }
        
        if(retval!=-1) {
            dataList.add(0, new ChItem(key,retval));
        }
        
        return retval;
    }
    
    public void put(int key,int value) {
        if(dataList.size()>=this.size) {
            dataList.remove(dataList.size()-1);
        }
        
        dataList.add(0, new ChItem(key,value));
    }
    
    public void print() {
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        
        for(ChItem item:dataList) {
            sb.append("("+item.key+","+item.value+"),");
        }
        
        sb.append("]");
        System.out.print(sb.toString());
    }
    
    public static void main(String[] args) throws Exception{
        LruCache2 cache=new LruCache2(2);
        cache.put(1,1);
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        cache.put(2,2);
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        System.out.print(cache.get(1));
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        cache.put(3, 3);                
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        System.out.print(cache.get(2));
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        cache.put(4, 4);    
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        
        System.out.print(cache.get(1));
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        System.out.print(cache.get(3));
        System.out.print(".....");
        cache.print();
        System.out.println();
        
        
        System.out.print(cache.get(4));
        System.out.print(".....");
        cache.print();
        System.out.println();
    }
}

输出:

.....[(1,1),]
.....[(2,2),(1,1),]
1.....[(1,1),(2,2),]
.....[(3,3),(1,1),]
-1.....[(3,3),(1,1),]
.....[(4,4),(3,3),]
-1.....[(4,4),(3,3),]
3.....[(3,3),(4,4),]
4.....[(4,4),(3,3),]

--2020年5月10日 19点47分--