• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LRU 缓存机制

开发技术 开发技术 4小时前 1次浏览

链接

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

import java.util.HashMap;
import java.util.Map;

class LRUCache {

    private int capacity;

    private Map<Integer, Node> indexMap;

    private DoubleList doubleList;

    static class Node {
        private int key;
        private int value;
        private Node pre;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class DoubleList {
        private Node head;
        private Node tail;

        private void add(Node node) {
            if (this.head == null) {
                this.head = node;
                this.tail = this.head;
            } else {
                this.tail.next = node;
                node.pre = this.tail;
                this.tail = node;
            }
        }

        private Node removeOldest() {
            if (this.head == null) {
                throw new NullPointerException();
            }
            Node removed = this.head;
            if (this.head == this.tail) {
                this.head = null;
                this.tail = null;
            } else {
                this.head.next.pre = null;
                this.head = this.head.next;
            }
            return removed;
        }

        private void moveToTail(Node node) {
            if (node == null) {
                return;
            }
            if (this.tail == node) {
                return;
            }
            if (this.head == node) {
                removeOldest();
                add(node);
                return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            add(node);
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.indexMap = new HashMap<>();
        this.doubleList = new DoubleList();
    }

    public int get(int key) {
        Node node = this.indexMap.get(key);
        if (node == null) {
            return -1;
        }
        doubleList.moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = this.indexMap.get(key);
        if (node != null) {
            node.value = value;
            this.doubleList.moveToTail(node);
        } else {
            if (this.indexMap.size() == this.capacity) {
                Node removeOldest = doubleList.removeOldest();
                this.indexMap.remove(removeOldest.key);
            }
            node = new Node(key, value);
            this.doubleList.add(node);
            this.indexMap.put(key, node);
        }
    }
}

程序员灯塔
转载请注明原文链接:LRU 缓存机制
喜欢 (0)