手寫一個LRU工具類
LRU概述
LRU演算法，即最近最少使用演算法。其使用場景非常廣泛，像我們日常用的手機的後台應用展示，軟體的複製粘貼板等。
本文將基於演算法思想手寫一個具有LRU演算法功能的Java工具類。
結構設計
在插入數據時，需要能快速判斷是否已有相同數據。為實現該目的，可以使用hash表結構。
同時根據LRU的規則，在對已有元素進行查找和修改操作後，該元素應該被置於首位；在增加元素時，如果超過了最大容量，則會淘汰末尾元素。為減少元素移動的時間複雜度，這裡採用雙端鏈表結構，使得移動元素到首位和刪除末尾元素的時間複雜度都為O(1)。
根據上述數據結構，可以定義元素節點內容，包含hash值，鍵K，值value，先繼節點和後繼節點。如下所示：
1 static class Entry<K,V> { 2 final int hash; // 哈希值 3 final K key; // 鍵 4 V value; // 值 5 Entry<K,V> before; // 先繼節點 6 Entry<K,V> after; // 後繼節點 7 Entry(int hash, K key, V value, Entry before, Entry after) { 8 this.hash = hash; 9 this.key = key; 10 this.value = value; 11 this.before = before; 12 this.after = after; 13 } 14 }
雙端鏈表則需要存儲頭節點和尾節點。
其它成員變數如下：
1 int maxSize; // 最大容量 2 Entry<K,V> head; // 頭節點 3 Entry<K,V> tail; // 尾節點 4 HashMap<K,V> hashMap; // 哈希表
在實現容器的增刪改查方法前，我們先把一些對鏈表的共用操作抽象出來，包括查找鏈表節點、將鏈表節點移動到隊首、刪除鏈表中節點。對應方法實現如下：
1 // 根據key從鏈表中找對應節點 2 Entry<K, V> find(Object key) { 3 // 遍歷鏈表找到該元素 4 Entry<K,V> entry = head; 5 while (entry != null) { 6 if (entry.key.equals(key)) 7 break; 8 entry = entry.after; 9 } 10 return entry; 11 } 12 // 將key對應的元素移至隊首 13 Entry<K,V> moveToFront(Object key) { 14 // 遍歷鏈表找到該元素 15 Entry<K,V> entry = find(key); 16 // 如果找到了並且不是隊首,則將該節點移動到隊列的首部 17 if (entry != null && entry != head) { 18 // 如果該節點是隊尾 19 if (entry == tail) 20 tail = entry.before; 21 // 先將該節點從鏈表中移出 22 Entry<K,V> p = entry.before; 23 Entry<K,V> q = entry.after; 24 p.after = q; 25 if (q != null) 26 q.before = p; 27 // 然後將該節點作為新的head 28 entry.before = null; 29 entry.after = head; 30 head = entry; 31 } 32 return entry; 33 } 34 // 將key對應的元素從雙端鏈表中刪除 35 void removeFromLinkedList(Object key) { 36 // 遍歷鏈表找到該元素 37 Entry<K,V> entry = find(key); 38 // 如果沒找到則直接返回 39 if (entry == null) return; 40 // 如果是隊首元素 41 if (entry == head) { 42 // 只有一個節點 43 if (tail == head) 44 tail = entry.after; 45 head = entry.after; 46 head.before = null; 47 } else if (entry == tail) { 48 // 如果是隊尾元素 49 tail = tail.before; 50 tail.after = null; 51 } 52 }
put()方法
put元素時需要判斷元素是否已經在容器中存在，如果存在，則修改對應節點的值，並將該節點移動到鏈表的頭部。
如果不存在，則將元素插入到鏈表的頭部。如果此時容量超過預設最大容量，需要將隊列尾部元素移除。
注意：上述操作需要判斷是否更新頭尾節點。
程式碼如下：
1 // 存入元素/修改元素 2 public void put(K key, V value) { 3 V res = hashMap.put(key,value); 4 // 如果res為null，表示沒找到，則存入並放置到隊首 5 if (res == null) { 6 Entry<K,V> entry = new Entry<>(key.hashCode(), key, value, null, head); 7 // 如果之前沒有頭節點 8 if (head == null) { 9 head = entry; 10 tail = entry; 11 } else { 12 // 如果之前有頭節點，將頭節點before指向entry 13 entry.after = head; 14 head.before = entry; 15 head = entry; 16 } 17 // 判斷此時節點數量是否超過最大容量,如果超過，則將隊尾元素刪除 18 if (hashMap.size() > maxSize) { 19 tail = tail.before; 20 tail.after = null; 21 } 22 } else { 23 // 如果res不為null,表示包含該元素，則將節點放置到隊首 24 Entry<K,V> entry = moveToFront(key); 25 // 同時修改節點的V值 26 entry.value = value; 27 } 28 }
remove()方法
從容器中刪除元素，需要判斷是否在容器中存在。同時也要注意更新頭尾節點。
1 // 刪除元素 2 public void remove(Object key) { 3 V res = hashMap.remove(key); 4 // 如果刪除成功，則將鏈表中節點一併刪除 5 if (res != null) 6 removeFromLinkedList(key); 7 }
get()方法
查找元素如果找到的話需要將對應節點移動到隊列頭部。
1 // 查詢元素 2 public V get(Object key) { 3 V res = hashMap.get(key); 4 // 如果在已有數據中找到，則將該元素放置到隊首 5 if (res != null) 6 moveToFront(key); 7 return res; 8 }
完整程式碼
完整程式碼以及測試如下：
1 package com.simple.test; 2 3 import java.util.ArrayList; 4 import java.util.HashMap; 5 import java.util.List; 6 7 public class SimpleLRUCache <K,V>{ 8 int maxSize; // 最大容量 9 Entry<K,V> head; // 頭節點 10 Entry<K,V> tail; // 尾節點 11 HashMap<K,V> hashMap; // 哈希表 12 // 構造函數 13 public SimpleLRUCache(int size) { 14 if (size <= 0) 15 throw new RuntimeException("容器大小不能<=0"); 16 this.maxSize = size; 17 this.hashMap = new HashMap<>(); 18 } 19 static class Entry<K,V> { 20 final int hash; // 哈希值 21 final K key; // 鍵 22 V value; // 值 23 Entry<K,V> before; // 先繼節點 24 Entry<K,V> after; // 後繼節點 25 Entry(int hash, K key, V value, Entry before, Entry after) { 26 this.hash = hash; 27 this.key = key; 28 this.value = value; 29 this.before = before; 30 this.after = after; 31 } 32 } 33 // 查詢元素 34 public V get(Object key) { 35 V res = hashMap.get(key); 36 // 如果在已有數據中找到，則將該元素放置到隊首 37 if (res != null) 38 moveToFront(key); 39 return res; 40 } 41 // 存入元素/修改元素 42 public void put(K key, V value) { 43 V res = hashMap.put(key,value); 44 // 如果res為null，表示沒找到，則存入並放置到隊首 45 if (res == null) { 46 Entry<K,V> entry = new Entry<>(key.hashCode(), key, value, null, head); 47 // 如果之前沒有頭節點 48 if (head == null) { 49 head = entry; 50 tail = entry; 51 } else { 52 // 如果之前有頭節點，將頭節點before指向entry 53 entry.after = head; 54 head.before = entry; 55 head = entry; 56 } 57 // 判斷此時節點數量是否超過最大容量,如果超過，則將隊尾元素刪除 58 if (hashMap.size() > maxSize) { 59 tail = tail.before; 60 tail.after = null; 61 } 62 } else { 63 // 如果res不為null,表示包含該元素，則將節點放置到隊首 64 Entry<K,V> entry = moveToFront(key); 65 // 同時修改節點的V值 66 entry.value = value; 67 } 68 } 69 // 刪除元素 70 public void remove(Object key) { 71 V res = hashMap.remove(key); 72 // 如果刪除成功，則將鏈表中節點一併刪除 73 if (res != null) 74 removeFromLinkedList(key); 75 } 76 // 將key對應的元素移至隊首 77 Entry<K,V> moveToFront(Object key) { 78 // 遍歷鏈表找到該元素 79 Entry<K,V> entry = find(key); 80 // 如果找到了並且不是隊首,則將該節點移動到隊列的首部 81 if (entry != null && entry != head) { 82 // 如果該節點是隊尾 83 if (entry == tail) 84 tail = entry.before; 85 // 先將該節點從鏈表中移出 86 Entry<K,V> p = entry.before; 87 Entry<K,V> q = entry.after; 88 p.after = q; 89 if (q != null) 90 q.before = p; 91 // 然後將該節點作為新的head 92 entry.before = null; 93 entry.after = head; 94 head = entry; 95 } 96 return entry; 97 } 98 // 將key對應的元素從雙端鏈表中刪除 99 void removeFromLinkedList(Object key) { 100 // 遍歷鏈表找到該元素 101 Entry<K,V> entry = find(key); 102 // 如果沒找到則直接返回 103 if (entry == null) return; 104 // 如果是隊首元素 105 if (entry == head) { 106 // 只有一個節點 107 if (tail == head) 108 tail = entry.after; 109 head = entry.after; 110 head.before = null; 111 } else if (entry == tail) { 112 // 如果是隊尾元素 113 tail = tail.before; 114 tail.after = null; 115 } 116 } 117 // 根據key從鏈表中找對應節點 118 Entry<K, V> find(Object key) { 119 // 遍歷鏈表找到該元素 120 Entry<K,V> entry = head; 121 while (entry != null) { 122 if (entry.key.equals(key)) 123 break; 124 entry = entry.after; 125 } 126 return entry; 127 } 128 // 順序返回元素 129 public List<Entry<K,V>> getList() { 130 List<Entry<K,V>> list = new ArrayList<>(); 131 Entry<K,V> p = head; 132 while (p != null) { 133 list.add(p); 134 p = p.after; 135 } 136 return list; 137 } 138 // 順序輸出元素 139 public void print() { 140 Entry<K,V> p = head; 141 while (p != null) { 142 System.out.print(p.key.toString()+":"+p.value.toString()+"\t"); 143 p = p.after; 144 } 145 System.out.println(); 146 } 147 public static void main(String[] args) { 148 SimpleLRUCache<String, String> test = new SimpleLRUCache(4); 149 test.put("a","1"); 150 test.put("b","2"); 151 test.put("c","3"); 152 test.put("d","4"); 153 // 此時順序為d c b a 154 test.print(); 155 // 獲取a,此時順序為 a d c b 156 test.get("a"); 157 test.print(); 158 // 修改c，此時順序為 c a d b 159 test.put("c","31"); 160 test.print(); 161 // 增加e,淘汰末尾元素b,此時順序為e c a d 162 test.put("e","5"); 163 test.print(); 164 } 165 }
