LRU算法的简单实现范例

>> 欢迎您客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章

返回首页

>>分享数据结构和算法相关的知识和技术

书籍支持

卫琴直播

品书摘要

在线测试

资源下载

联系我们

Java技术网站 → 『 Java开发技术』 → 『数据结构和算法专题』 → LRU算法的简单实现范例

您是本文章第 19705 个阅读者

* 贴子主题: LRU算法的简单实现范例

点赞(0) 收藏

作者:javathinker 发表时间：2020-03-15 12:34:02

消息

查看

搜索

好友

复制

引用

package com.hanchao.test0809;

import java.util.Hashtable;

public class LRUCache {
    /**
     * 链表节点
     * @author Administrator
     *
     */
    class CacheNode {
        CacheNode prev;//前一节点
        CacheNode next;//后一节点
        Object value;//值
        Object key;//键
        CacheNode() {
        }
    }

    private int cacheSize;
    private Hashtable nodes;//缓存容器
    private int currentSize;
    private CacheNode first;//链表头
    private CacheNode last;//链表尾

    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//缓存容器
    }

    /**
     * 获取缓存中对象
     * @param key
     * @return
     */
    public Object get(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        } else {
            return null;
        }
    }

    /**
     * 添加缓存
     * @param key
     * @param value
     */
    public void put(Object key, Object value) {
        CacheNode node = (CacheNode) nodes.get(key);

        if (node == null) {
            //缓存容器是否已经超过大小.
            if (currentSize >= cacheSize) {
                if (last != null)//将最少使用的删除
                    nodes.remove(last.key);
                removeLast();
            } else {
                currentSize++;
            }

            node = new CacheNode();
        }
        node.value = value;
        node.key = key;
        //将最新使用的节点放到链表头，表示最新使用的.
        moveToHead(node);
        nodes.put(key, node);
    }

    /**
     * 将缓存删除
     * @param key
     * @return
     */
    public Object remove(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
            if (last == node)
                last = node.prev;
            if (first == node)
                first = node.next;
        }
        return node;
    }

    public void clear() {
        first = null;
        last = null;
    }

    /**
     * 删除链表尾部节点
     *  表示删除最少使用的缓存对象
     */
    private void removeLast() {
        //链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
        if (last != null) {
            if (last.prev != null)
                last.prev.next = null;
            else
                first = null;
            last = last.prev;
        }
    }

    /**
     * 移动到链表头，表示这个节点是最新使用过的
     * @param node
     */
    private void moveToHead(CacheNode node) {
        if (node == first)  {
         //如果当前节点就是链表的头，不做处理
         return;
        }
        if (node.prev != null)  {
         //如果当前节点的前一个元素不为null,把前一个元素的下一个指向当前元素的下一个元素
         node.prev.next = node.next;
        }
        if (node.next != null)  {
         //如果当前节点的后一个元素不为null,把后一个元素的前一个指向当前元素的前一个元素
         node.next.prev = node.prev;
        }
        if (last == node)  {
         //如果当前元素为最后一个元素，则最后一个元素变成当前元素的前一个元素
         last = node.prev;
        }
        if (first != null) {
         //如果第一个算不为null,则当前元素的下一个指向为原来的第一个元素
         //原来的第一个元素的前一个元素变成当前元素
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null)  {
         last = first;
        }
    }

}

参考：http://gogole.iteye.com/blog/692103

http://blog.chinaunix.net/uid-26147414-id-3435752.html

http://dennis-zane.iteye.com/blog/128278

----------------------------
原文链接:https://blog.51cto.com/hanchaohan/1538252

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-19 10:58:14 重新编辑]

Java精品书籍推荐