算法学习之路：LRU和LFU的简单实现 V1

public class LRUcache {
    HashMap table;
    Node first,tail;
    static int defaultSize = 5;
    class Node{
        Node pre;
        Node next;
        K key;
        V val;
        Node(K key,V val){
            this.key = key;
            this.val = val;
        }
    }
    public void put(K key,V val){
        if (key == null){
            return;
        }
        if (table == null || table.size() == 0){
            table = new HashMap<>();
        }
        Node node = new Node(key,val);
        if (table.get(key) == null){
            if (table.size() == defaultSize){
                remove(first.key);
            }
            addToTail(key,node);
        }else {
            remove(key);
            addToTail(key,node);
        }
    }
    public V get(K key){
        if (table.get(key) == null){
            return null;
        }else {
            Node node = table.get(key);
            remove(key);
            addToTail(key,node);
            return (V) node.val;
        }
    }
    private void remove(K key){
        Node oldNode = table.get(key);
        if (first.equals(oldNode)){
            first = first.next;
            oldNode.next = null;
        }else if (tail.equals(oldNode)){
            return;
        }else {
            oldNode.pre.next = oldNode.next;
            oldNode.next.pre = oldNode.pre;
            oldNode.pre = null;
            oldNode.next = null;
        }
        table.remove(key);
    }
    private void addToTail(K key,Node node){
        if (first == null && tail == null){
            first = node;
            tail = node;
        }else {
            tail.next = node;
            node.pre = tail;
            node.next = null;
            tail = node;
        }
        table.put(key,node);
    }
    public List getAll(){
        if (first == null){
            return null;
        }
        Node node = first;
        List list = new ArrayList<>();
        do {
            list.add((V) node.val);
            node = node.next;
        }while (node != null);
        return list;
    }
}

public class LFUcache {
    HashMap table;
    static int defaultSize = 5;
    class Node{
        K key;
        V val;
        int count;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
            this.count = 1;
        }
    }
    public V get(K key){
        if (key == null || table.get(key) == null){
            return null;
        }
        Node node = table.get(key);
        node.count++;
        table.put(key,node);
        return node.val;
    }
    public void put(K key,V val){
        if (key == null){
            return;
        }
        if (table == null || table.size() == 0){
            table = new HashMap<>();
        }
        if (table.get(key) == null){
            if (table.size() == defaultSize){
                removeLeastUsed();
            }
            Node node = new Node(key,val);
            table.put(key,node);
        }
    }
    private void removeLeastUsed(){
        Set> entries = table.entrySet();
        K lkey = null;
        int lcount = Integer.MAX_VALUE;
        for (Map.Entry map : entries){
            if (map.getValue().count < lcount){
                lcount = map.getValue().count;
                lkey = map.getValue().key;
            }
        }
        table.remove(lkey);
    }
}

该算法后续还将继续优化