LinkedHashMap

randian666 · randian666 · commit e7618708a5d8 · 2019-02-13T11:10:43.000+08:00
diff --git a/src/main/java/com/algorithm/study/demo/LRUCache/LRUCache.java b/src/main/java/com/algorithm/study/demo/LRUCache/LRUCache.java
@@ -0,0 +1,48 @@
+package com.algorithm.study.demo.LRUCache;
+
+import java.util.*;
+
+/**
+ * LinkedHashMap实现LRU缓存
+ * @Author: liuxun
+ * @CreateDate: 2019/2/13 上午10:24
+ * @Version: 1.0
+ */
+public class LRUCache {
+    MapCache cache;
+    public LRUCache(int capacity) {
+        this.cache = new MapCache(capacity);
+    }
+
+    public int get(int key) {
+        return cache.getOrDefault(key, -1);
+    }
+
+    public void put(int key, int value) {
+        cache.put(key, value);
+    }
+    public Collection<Map.Entry<Integer, Integer>> getAll() {
+        return new ArrayList<Map.Entry<Integer, Integer>>(cache.entrySet());
+    }
+    class MapCache extends LinkedHashMap<Integer, Integer> {
+        public int max;
+        public MapCache(int max) {
+            super(max, 0.75f, true);
+            this.max = max;
+        }
+        protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
+            return size() > max;
+        }
+
+    }
+    public static void main(String[] args) {
+        LRUCache map = new LRUCache(2) ;
+        map.put(1,1);
+        System.out.println(map.get(4));
+        for (Map.Entry<Integer, Integer> e : map.getAll()){
+            System.out.print(e.getKey() + " : " + e.getValue() + "\t");
+        }
+    }
+}
+
+
diff --git a/src/main/java/com/algorithm/study/demo/LRUCache/LRULinked.java b/src/main/java/com/algorithm/study/demo/LRUCache/LRULinked.java
@@ -9,11 +9,11 @@
  * @CreateDate: 2019/1/23 下午4:03
  * @Version: 1.0
  */
-public class LRULinked<K,V>{
+public class LRULinked{
     //缓存
-    private final Map<K, V> cacheMap = new HashMap<>();
+    private final Map<Integer, Integer> cacheMap = new HashMap<>();
     //根节点
-    private Node<K, V> root;
+    private Node root;
     private int cacheSize;
     private int size;
     public LRULinked(int cacheSize){
@@ -24,14 +24,15 @@ public LRULinked(int cacheSize){
      * 插入头结点
      * @param value
      */
-    public void put(K key,V value){
-        Node<K, V> node=new Node<K, V>(key,value);
+    public void put(int key,int value){
+        cacheMap.put(key,value);
+        Node node=new Node(key,value);
         if (size==cacheSize){//容量满了删除尾节点
-            Node<K, V> temp=root.next;
+            Node temp=root.next;
             if (temp==null){
                 root=null;
             }else{
-                Node<K, V> current=root;
+                Node current=root;
                 while (temp.next!=null){
                     current=temp;
                     temp=temp.next;
@@ -44,10 +45,13 @@ public void put(K key,V value){
         root=node;
         size++;
     }
-    public V get(K key){
-        for (Node<K,V> node = root; node!=null&&!root.key.equals(key); node=node.next){
+    public int get(int key){
+        if (!cacheMap.containsKey(key)){
+            return -1;
+        }
+        for (Node node = root; node!=null&&!root.key.equals(key); node=node.next){
             if (node.next.key.equals(key)){
-                Node<K, V> nodeNew=new Node<K, V>(node.next.key,node.next.value);
+                Node nodeNew=new Node(node.next.key,node.next.value);
                 node.next=node.next.next;
                 size--;
                 this.put(nodeNew.key,nodeNew.value);//查找的节点放到头结点
@@ -60,7 +64,7 @@ public V get(K key){
     public String toString(){
         StringBuilder sb=new StringBuilder();
         int j=0;
-        Node<K, V> temp=root;
+        Node temp=root;
         while (j<size){
             sb.append(temp.value);
             temp= temp.next;//找到最后一个结点
@@ -69,26 +73,24 @@ public String toString(){
         return sb.toString();
     }
 
-    public static class Node<K, V>{
-        private K key;
-        private V value;
-        private Node<K, V> next;
-        public Node(K key, V value){
+    public static class Node{
+        private Integer key;
+        private Integer value;
+        private Node next;
+        public Node(Integer key, Integer value){
             this.key=key;
             this.value=value;
         }
     }
 
     public static void main(String[] args) {
-        LRULinked<String,String> linked=new LRULinked<>(3);
-        linked.put("a","a");
-        linked.put("b","b");
-        linked.put("c","c");
-        linked.get("b");
-        linked.put("d","d");
+        LRULinked linked=new LRULinked(3);
+        linked.put(1,2);
+        linked.put(2,2);
+        linked.put(3,3);
+        System.out.println(linked.get(1));
+        linked.put(4,4);
         System.out.println(linked.size);
         System.out.println(linked.toString());
-        System.out.println(linked.toString());
-        System.out.println(linked.size);
     }
 }
