栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

基于Java的LRU算法的实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

基于Java的LRU算法的实现

1.思想:基于HashMap和双向循环链表实现

 2.代码实现
package alian;

import java.util.HashMap;
import java.util.Set;

class Main {
    public static void main(String[] args) {
        LRU lru = new LRU(3);
//        lru.add(3);
//        lru.add(2);
//        lru.add(1);
//        lru.add(0);
        // 0 1 2

//        lru.add(3);
//        lru.add(2);
//        lru.add(1);
//        lru.get(3);
//        lru.add(0);
//        0 1 3
        Set keys = lru.map.keySet();
        for (Object key : keys) {
            System.out.print(key + " ");
        }
    }
}

// 循环双向链表
class Node {
    Object key;

    public Node(Object key) {
        this.key = key;
        pre = null;
        next = null;
    }

    Node pre;
    Node next;
}

class LRU {
    HashMap map;
    Node head;
    int size;
    int cval;

    public LRU(int size) {
        map = new HashMap<>();
        head = null;
        this.size = size;
        cval = 0;
    }

    // 新插入的对象放在循环双向链表的首部
    public void add(Object obj) {
        Node node = new Node(obj);
        map.put(obj, node);
        if (head == null) {
            head = node;
            node.next = node;
            node.pre = node;
            cval++;
        } else {
            Node tail = head.pre;
            node.next = head;
            head.pre = node;
            node.pre = tail;
            tail.next = node;
            head = node;
            cval++;
            delete();
        }
    }

    public void delete() {
        if (cval > size) {
            Node tep = head.pre.pre;
            //删除最后的一个节点
            map.remove(head.pre.key);
            head.pre = tep;
            tep.next = head;
            cval--;
        }
    }

    public Object get(Object obj) {
        if (!map.containsKey(obj)) {
            return null;
        }
        //更新双向链表的顺序
        Node node = (Node) map.get(obj);
        Node pre1 = node.pre;
        Node pre2 = node.next;
        pre1.next = pre2;
        pre2.pre = pre1;
        //将访问值放在双向队列的首尾
        Node tail = head.pre;
        node.next = head;
        head.pre = node;
        node.pre = tail;
        tail.next = node;
        head = node;
        cval++;
        return obj;
    }
} 

转载请注明:文章转载自 www.mshxw.com
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号