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分--

巴特西

Q200510-03-02: LRU缓存机制

最新文章

热门文章