LRU算法 O(1)时间复杂度

作者: NetCedar | 来源:发表于2018-10-29 22:26 被阅读0次

实现LRU算法,查找删除时间复杂度都为O(1)
LRU Cache是一个Cache置换算法,含义是“最近最少使用”,当Cache满(没有空闲的cache块)时,把满足“最近最少使用”的数据从Cache中置换出去,并且保证Cache中第一个数据是最近刚刚访问的

实现思路
利用hashmap加链表来实现这个原理
链表元素node由两个元素构成(key-value),在hashmap中存入node的key值,以及node;hashmap的构成为<Integer,Node>

为保证每次查找为O(1)并要判断双向链表里面是否含有元素,所以要将node设为两个值,key和value,其中node的key与map的值相同,当hashmap中存在key的时候,则双向链表中也存在key。利用这个特质,能完成查找删除都为O(1)

将最小使用的元素删除,核心就是每次插入的时候,都插入到链表的头结点;每次get一个元素时候,将get的那个元素删除,然后将元素插入到头结点


import java.util.HashMap;

public class LRU {


    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head = null;
    Node end = null;

    public LRU(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 每次使用的时候,就将用的元素删除,然后放到链表头部
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            remove(n);
            setHead(n);
            printNodes("get");
            return n.value;
        }
        printNodes("get");
        return -1;
    }


    public void remove(Node n) {
        if (n.pre != null) { //如果n不是头结点,将元素删除
            n.pre.next = n.next;
        } else {
            head = n.next;  //将n方法到头结点位置
        }

        if (n.next != null) {   //操作另外一个指针
            n.next.pre = n.pre;
        } else {
            end = n.pre;
        }

    }

    /**
     * 将元素设置成头结点
     * @param n
     */
    public void setHead(Node n) {
        //将n插入到头结点位置
        n.next = head;
        n.pre = null;

        if (head != null)
            head.pre = n;

        //将头结点设为n
        head = n;

        if (end == null)
            end = head;
    }

    /**
     * 对map插入操作
     * @param key
     * @param value
     */
    public void set(int key, int value) {
        //如果存在key,将元素放到头位置
        if (map.containsKey(key)) {
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        } else {
            //如果不存在 就插入头位置
            Node created = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(end.key);
                remove(end);
                setHead(created);

            } else {
                setHead(created);
            }

            map.put(key, created);
        }
        printNodes("set");
    }

    public void printNodes(String explain) {

        System.out.print(explain + ":" + head.toString());
        Node node = head.next;
        while (node != null) {
            System.out.print(node.toString());
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRU lruCacheTest = new LRU(5);
        lruCacheTest.set(1, 1);
        lruCacheTest.set(2, 2);
        lruCacheTest.set(3, 3);
        lruCacheTest.set(4, 4);
        lruCacheTest.set(5, 5);
        System.out.println("lruCacheTest.get(1):" + lruCacheTest.get(1));
        lruCacheTest.set(6, 6);
        System.out.println("lruCacheTest.get(2):" + lruCacheTest.get(2));
    }

}

/**
 * 双向链表
 */

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

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

    @Override
    public String toString() {
        return this.key + "-" + this.value + " ";
    }


}

相关文章

  • LRU算法 O(1)时间复杂度

    实现LRU算法,查找删除时间复杂度都为O(1)LRU Cache是一个Cache置换算法,含义是“最近最少使用”,...

  • LRU-Swift实现

    双向链表+Map实现,get、put、时间复杂度为O(1).LRU数据结构如下图: LRU LRU(least r...

  • 每日一题20201106(169. 多数元素)

    hash表 时间复杂度: O(N)空间复杂度: O(N) 投票算法 时间复杂度: O(N)空间复杂度: O(1)

  • 最大子序列和问题的几种实现

    算法一,暴力法,时间复杂度O(n^3): 算法二,时间复杂度O(n^2): 算法三,在线处理,时间复杂度O(n):...

  • o(1), o(n), o(logn), o(nlogn)算法的

    在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度,...

  • O(1), O(n), O(logn), O(nlogn)

    在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度,...

  • 复杂度分析

    1. 大 O 复杂度表示法 时间复杂度就是算法的执行效率,也就是算法代码执行的时间; 大 O 时间复杂度实际上并不...

  • TwoSum

    暴力暴力算法时间复杂度O(n²),空间复杂度O(1) 两次遍历 HashMap时间复杂度:O(n),我们把包含有 ...

  • 6. 归并排序

    归并排序:算法时间复杂度O(nlogn) 空间复杂度O(n) 算法实现

  • 插入排序 insert sort

    插入排序 时间复杂度(平均、最坏)O(n^2), 最好时间复杂度O(n) 空间复杂度为O(1) 稳定性:稳定 算法...

网友评论

    本文标题:LRU算法 O(1)时间复杂度

    本文链接:https://www.haomeiwen.com/subject/qcnitqtx.html