LRU算法的实现

作者:神秘网友 发布时间:2020-11-20 12:23:03

LRU算法的实现

缘由:看到redis的缓存淘汰机制,便自己实现了一下

代码实现(双向链表+HashMap)

package com.jarjune.jdalao.framework.algorithm;

import java.util.*;

/**
 * LRU
 * @author jarjune
 * @version 1.0.1
 * @date 2020/11/19
 */
public class LRUCache<K, V> {

    // 缓存Node
    private Map<K, Node<K, V>> cache;

    // 双向链表首结点
    private Node<K, V> first;

    // 双向链表尾结点
    private Node<K, V> last;

    // 最大缓存容量
    private int capacity;

    public LRUCache(int capacity) throws Exception {
        if(capacity < 2) {
            throw new Exception("capacity小于2就没啥意义了...");
        }
        this.cache = new HashMap<>((int) (capacity / 0.75f + 1));
        this.capacity = capacity;
    }

    private class Node<K, V> {
        K k;
        V v;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K k, V v) {
            this.k = k;
            this.v = v;
        }

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

    public int size() {
        return cache.size();
    }

    public void put(K k, V v) {

        Node<K, V> node = cache.get(k);
        if(null == node) {
            node = new Node<>(k, v);

            // 大于等于capacity容量最大值时
            if(cache.size() >= capacity) {

                if(null != last) {
                    // 移除最后一个元素的缓存
                    cache.remove(last.k);

                    last = last.prev;
                    if(null == last) {
                        first = null;
                    } else {
                        last.next = null;
                    }
                }
            }
            cache.put(k, node);
        } else {
            node.v = v;
        }

        moveToFirst(node);
    }

    /**
     *  1(first)
     * ↑  ↓
     *  2(node)
     * ↑  ↓
     *  3
     * ↑  ↓
     *  4(last)
     */
    private void moveToFirst(Node<K, V> node) {

        if(first == null || last == null) {
            first = last = node;
            return;
        }

        // 如果是头结点就结束
        if(node == first) {
            return;
        }

        // 如果是尾结点,尾结点就等于当前结点的上一个结点
        if(node == last) {
            last = node.prev;
        }

        if(null != node.next) {
            node.next.prev = node.prev;
        }

        if(null != node.prev) {
            node.prev.next = node.next;
        }

        node.next = first;
        first.prev = node;
        node.prev = null;
        first = node;
    }

    class LRUIterable implements Iterable<Node<K, V>> {

        @Override
        public Iterator<Node<K, V>> iterator() {
            return new Iterator<Node<K, V>>() {

                private Node<K, V> node = first;

                @Override
                public boolean hasNext() {
                    return node != null;
                }

                @Override
                public Node<K, V> next() {
                    Node<K, V> tmp = node;
                    node = node.next;
                    return tmp;
                }
            };
        }
    }

    public Iterator<Node<K, V>> iterator() {
        return new LRUIterable().iterator();
    }

    public Set<K> keySet() {
        Iterator<Node<K, V>> iterator = iterator();
        Set<K> keys = new LinkedHashSet<>();
        while(iterator.hasNext()) {
            keys.add(iterator.next().k);
        }
        return keys;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node<K, V> node: new LRUIterable()) {
            sb.append(node);
        }
        return sb.toString();
    }
}

搞定

LRU算法的实现相关教程

  1. Laravel 如何优雅地实现输出结构统一的功能?

    背景 一般的项目需求都会要求统一的输出结构,特别是对于api应用而言。因此,如果有beforeResponse的功能,则可以在数据输出之前对response进行统一格式化处理。 假设这么一种场景,应用做api开发,使用抛异常的方式(自定义异常类ApiException)返回无效非法

  2. 拉斯维加斯算法之n后问题

    1、拉斯维加斯(Las Vegas)算法 舍伍德算法优点在于计算时间复杂度对所有实例相对均匀,但与其相应的确定性算法相比,其平均时间复杂度没有改进。拉斯维加斯算法则不然,它能显著改进算法的有效性,甚至对某些迄今为止找不到有效算法的问题,也能得到满意的算

  3. 拉斯维加斯随机化算法求解整数因子分解

    问题描述 设n1是一个整数。关于整数n的因子分解问题是找出n的如下形式的 唯一分解式 :。其中,p1p2…pk是k个素数,m1,m2,…,mk是k个正整数。如果n是一个合数,则n必有一个非平凡因子x,1xn,使得x可以整除n。 给定一个合数n, 求n的一个非平凡因子的问题称

  4. css 背景不滚动的实现方法

    css背景不滚动的实现方法:首先新建一个html代码页面;然后在title标签后面创建一个style标签;接着在这个标签里设置body标签的背景图片;最后设置“background-repeat:no-repeat;”属性即可。 推荐:《css视频教程》 打开html开发软件,新建一个html代码页

  5. css实现文字不换行溢出显示省略号

    css文字不换行溢出显示省略号的实现方法:首先打开css样式表;然后通过属性“white-space: nowrap;”实现文本强制不换行;接着通过“text-overflow:ellipsis;”实现文本溢出显示省略号即可。 推荐:《css视频教程》 1. 强制不换行 white-space: nowrap; 文本

  6. css怎么实现首字母下沉效果

    css实现首字母下沉效果的方法:可以通过使用first-letter伪类选择器来实现,如【.contain p:first-letter{}】。first-letter伪类选择器用来指定元素第一个字母的样式。 可以通过使用css的first-letter伪类选择器来实现首字母下沉效果。 (学习视频分享:css

  7. thinkphp5.1和php、vue.js实现前后端分离和交互

    下面由 thinkphp 框架教程栏目给大家介绍thinkphp5.1和php、vue.js实现前后端分离和交互,希望对需要的朋友有所帮助! 主要目标是使用vue.js把前端获取的账号和密码传到后台,然后使用tp5.1框架获取前端的值,并返回token等一些值。然后使用localStorage.set

  8. java面试之归并排序的应用

    文章背景: 在复习算法及数据结构时,找到了面试笔试题目,下面我们来看看题目: (学习视频分享:java教学视频) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1