LRU(Least Recently Used)アルゴリズムの簡単な紹介

文書ディレクトリ

LRUアルゴリズム概要

使用シーン

単純実現

簡単な紹介

LRUアルゴリズムの概要
LRU英文翻訳はleast recently usedで、字面の意味は最近最も少なく使用して、はっきり言って1種の淘汰アルゴリズムで、新しい要素が挿入される時、私達の使用空間はまた有限な時、古い要素を淘汰する必要があって、この時最も少なく使用する要素を淘汰することを選択します.
シーンの操作
私达は1つの机能を実现してログインする时すべてのuserのipを保存して、まずこのipはデータベースの中に挿入して、システムがスタートする时キャッシュの中に更新して、もしだから毎回ユーザーがログインする时私达は先にキャッシュの中にこのuserがあるかどうかを検索して、もし更にデータベースを検索していないならば、データベースがない場合はapiにこのuserのipをクエリーしてキャッシュとデータベースに更新するように要求し、userの増加に伴ってキャッシュの数も増加するので、メモリが非常に消費されるので、一定数のメモリを制定して一定数のuserにアクセスしますが、後で淘汰のメカニズムに直面し、この時LRUアルゴリズムは役に立ちます.
単純な実装

/**
 * Created by dc on 2019/6/29.
 * lru   least recently userd          
 */
public class LruMap {

    /**
     *     ，        
     */
    private Node head;
    /**
     *     ，          
     */
    private Node tail;
    /**
     *     
     */
    private int limit;

    private Map data;

    public LruMap(int limit) {
        this.data = new HashMap<>();
        this.limit = limit;
    }

    /**
     *     
     * @param key
     * @param value
     */
    public void put(String key, String value) {
        Node node = data.get(key);
        if(node == null) {
            if(data.size() >= limit) {
                String oldKey = removeNode(tail);
                data.remove(oldKey);
            }
            Node node1 = new Node(key,value);
            addNode(node1);
            data.put(key, node1);
        }else {
            node.value = value;
            refresh(node);
        }
    }

    /**
     *     
     * @param key
     * @return
     */
    public String get(String key) {
        Node node = data.get(key);
        if(node == null ){
            return null;
        }else {
            refresh(node);
            return node.value;
        }
    }

    /**
     *     
     * @param node
     */
    private void refresh(Node node) {
        if(node == head) {
            return;
        }
        removeNode(node);
        addNode(node);
    }

    /**
     *     
     * @param node
     */
    private void addNode(Node node) {
        if (head != null) {
            node.next = head;
            head.pre = node;
        }
        head = node;
        if(tail == null) {
            tail = node;
        }
    }

    /**
     *     
     * @param node
     * @return
     */
    private String removeNode(Node node) {
        if(node == tail){
            tail = tail.pre;
        }else if(node == head) {
            head = head.next;
        }else{
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
      return node.key;
    }

    class Node{

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

        private Node pre;
        private Node next;
        private String key;
        private String value;


    }

    public static void main(String[] args) {

        LruMap lruMap = new LruMap(5);
        lruMap.put("001","  001   ");
        lruMap.put("002","  002   ");
        lruMap.put("003","  003   ");
        lruMap.put("004","  004   ");
        lruMap.put("005","  005   ");

        lruMap.get("001");
        lruMap.put("006","  006   ");
        System.out.println(lruMap.get("002"));



    }

簡単な紹介
主にhashmap+双方向チェーンテーブルに基づいて、linkedhashmapで、私はただ手書きで簡単なものを書いただけで、原理は1つのスタックに相当して、先進的な後出の原理で、最後に挿入した要素あるいは最近アクセスした要素はすべて最も上にあって、記憶が足りない時最も下の要素を淘汰します.