LRU算法java实现

LRU原理

LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

实现代码为

package com.cw.demo.algorithm;

import java.util.concurrent.ConcurrentHashMap;

/**
 * LRU算法demo
 *
 * @author chenwei
 * @create 2017-11-13 16:18
 **/

public class LRU
{

    public static void main(String[] args) {

        LruList list = new LruList();
        list.put("key1","value1");
        list.put("key2","value2");
        list.put("key3","value3");
        list.put("key4","value4");
        list.put("key5","value5");
        list.put("key6","value6");
        list.put("key7","value7");
        System.out.println(list);
        list.get("key5");
        list.get("key1");
        list.put("key8","value8");
        list.put("key9","value9");
        list.put("key10","value10");
        list.put("key11","value11");
        list.put("key12","value12");
        list.get("key1");
        list.get("key3");
        System.out.println(list);
        list.put("key3","value3");
        System.out.println(list);
    }


    /**
     * lru数据结构
     */
    static class LruList<V> {

        private Node<V> first;

        private Node<V> last;

        private int capacity = 10;

        private ConcurrentHashMap<String, Node> data = new ConcurrentHashMap<>();

        LruList() {
            first = new Node<>();
            last = new Node<>();
            first.next = last;
            last.prev = first;
        }

        LruList(int capacity) {
            this.capacity = capacity;
        }

        public Node get(String key) {
            if (key == null) {
               return null;
            }
            Node node = data.get(key);
            if (node != null) {
                //node的相邻节点双向指针指向对方
                node.prev.next=node.next;
                node.next.prev=node.prev;

                //将node插入到first后
                node.next=first.next;
                node.prev=first;
                first.next.prev=node;
                first.next=node;
                return node;
            }
            return null;
        }


        public void put(String key,V value) {
            if (key == null) {
               throw new  IllegalArgumentException("param is null");
            }
            Node node = data.get(key);
            if (node == null) {
                if (data.size() >= capacity) {
                    Node nodeRemoved=last.prev;
                    data.remove(nodeRemoved.key);
                    nodeRemoved.prev.next=last;
                    last.prev=nodeRemoved.prev;
                }
                node = new Node<>(key, value);
                data.put(key, node);
            }else {
                node.prev.next=node.next;
                node.next.prev=node.prev;
            }
            //将node插入到first后面
            node.next=first.next;
            node.prev=first;
            first.next.prev=node;
            first.next=node;
        }


        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node node= first.next;
            while (node != last) {
                sb.append("{").append(node.key).append(":").append(node.value).append("}");
                if (node.next != last) {
                    sb.append(",");
                }
                node= node.next;
            }
            sb.append("]");
            return sb.toString();
        }

        /**
         * 节点类
         */
        static class Node<V> {
            private String key;

            private V value;

            private Node prev;

            private Node next;
            Node (){
            }

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

        }
    }


}