返回顶部

收藏

实现lru 缓存

更多

思路:用map+链表实现,map用来提高查询速度,链表用来存放元素。链表头放入最新的元素,表尾为最老元素。访问cache命中,或者cache满写入时都需要对链表内容和map进行调整。

JDK里面有一个LinkedHashMap就是基于这个思路实现的。

LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. ShowTags```java public class LRUCache {
static class Node {
int key;
int value;

        @Override  
        public String toString() {  
            return "Node{" +  
                    "key=" + key +  
                    ", value=" + value +  
                    '}';  
        }  
    }

    static private LinkedList<Node> cache;  
    static private int cap;  
    static private Node indexMap[];

    public LRUCache(int capacity) {  
        cache = new LinkedList<Node>();  
        indexMap = new Node[100000];  
        cap = capacity;  
    }

    static public boolean isFull() {  
        return cache.size() == cap;  
    }

    static public Node find(int key) {  
        if (cache.isEmpty())  
            return null;  
        Node tar = null;

        if ((tar = indexMap[key]) == null)  
            return null;

        cache.remove(tar);  
        cache.addFirst(tar);  
        return tar;

    }

     public int get(int key) {  
        Node node = find(key);  
        if (node == null) {  
            return -1;  
        }  
        return node.value;  
    }

     public void set(int key, int value) {  
        Node node = null;  
        if ((node = find(key)) != null) {  
            node.value = value;  
            return;  
        }

        //not find the element

        if (isFull()) {  
            indexMap[cache.getLast().key] = null;  
            cache.removeLast();  
        }

        Node newNode = new Node();  
        newNode.key = key;  
        newNode.value = value;  
        cache.addFirst(newNode);  
        indexMap[key] = newNode;

    }  
}

```

标签:java

收藏

0人收藏

支持

0

反对

0

发表评论