양 방향 링크 와 HashMap 을 기반 으로 한 LRU 알고리즘 구현

LRU 알고리즘
메모리 관 리 를 할 때 우 리 는 LRU 알고리즘 을 비교적 많이 사용한다.즉,Last Recently Used최근 에 최소 사용 원칙 은 리 눅 스 운영 체제 에 최초 로 등장 했다.구체 적 인 실현 방향 은 해시 링크 를 사용 하여 키 값 을 저장 하 는 것 입 니 다.우 리 는 양 방향 링크 와 HashMap 을 바탕 으로 스스로 LRU 캐 시 알고리즘 을 실현 할 수 있 습 니 다.구체 적 인 코드 는 다음 과 같다.

package com.natsuki;

import java.util.HashMap;

/**
 * @Author: xuzhiwei
 * @Date: 2019-05-12
 * @Description:       HashMap LRU    
 */
public class LRUCache {
    private Node head;
    private Node end;
    private int limit;

    private HashMap<String, Node> hashMap;

    public LRUCache(int limit) {
        if (limit <= 0) {
            throw new IllegalArgumentException("limit must > 0");
        }
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            if (hashMap.size() >= limit) {
                //        
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            Node newNode = new Node(key, value);
            addNode(newNode);
            hashMap.put(key, newNode);
        } else {
            node.value = value;
            //    ，           
            refreshNode(node);
        }
    }

    private void refreshNode(Node node) {
        if (node == end) {
            return;
        }
        removeNode(node);
        addNode(node);
    }

    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.prev = end;
        }
        end = node;
        if (head == null) {
            head = node;
        }
        node.next = null;
    }

    private String removeNode(Node node) {
        if (node == end) {
            end = end.prev;
        } else if (node == head) {
            head = head.next;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        return node.key;
    }

    private class Node {
        Node prev;
        Node next;
        String key;
        String value;

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

    @Override
    public String toString() {
        StringBuilder ret = new StringBuilder();
        Node p = head;
        while (p!=null){
            ret.append("key:").append(p.key).append(",value:").append(p.value).append(";");
            p = p.next;
        }
        return ret.toString();
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001","  1  ");
        lruCache.put("002","  2  ");
        lruCache.put("003","  3  ");
        lruCache.put("002","  2   ");
        String s = lruCache.get("002");
        //   2   
        System.out.println(s);

        // key:001,value:  1  ;key:003,value:  3  ;key:002,value:  2   ;
        System.out.println(lruCache);

    }
}

여기 서 가장 오른쪽 끝 은 최근 이나 가장 많이 사용 되 는 데이터 이 고,가장 왼쪽 끝 은 가장 적 게 사용 되 는 데이터 로 매우 교묘 하 다.