1. 基于LinkedHashMap

2. 基于HashMap 和 雙向鏈表

import java.util.LinkedHashMap;/*** Created by itworker365 on 5/11/2017.* 基于LinkedHashMap特性，用繼承或代理方式，選擇基于訪問順序并在繼承后重寫removeEldestEntry當超過容量時返回true。
* 基本測試看代碼知道這個結構的實現就很清楚了，不用寫了。*/ public class LRUCacheUseLinkedHashmap {public static void main(String[] args) {/*** LinkedHashMap 參數說明* initialCapacity the initial capacity* loadFactor the load factor* accessOrder the ordering mode - <tt>true</tt> for access-order, <tt>false</tt> for insertion-order*/LinkedHashMap<Integer, Integer> linkedHashMapInsertionOrder = new LinkedHashMap<>(5, 10, false);linkedHashMapInsertionOrder.put(1, 111);linkedHashMapInsertionOrder.put(3, 333);linkedHashMapInsertionOrder.put(2, 222);System.out.println("linkedHashMapInsertionOrder before get: " + linkedHashMapInsertionOrder.toString());linkedHashMapInsertionOrder.get(3);System.out.println("linkedHashMapInsertionOrder after get: " + linkedHashMapInsertionOrder.toString());LinkedHashMap<Integer, Integer> linkedHashMapAccessOrder = new LinkedHashMap<>(5, 10, true);linkedHashMapAccessOrder.put(1, 111);linkedHashMapAccessOrder.put(3, 333);linkedHashMapAccessOrder.put(2, 222);System.out.println("linkedHashMapAccessOrder before get: " + linkedHashMapAccessOrder.toString());linkedHashMapAccessOrder.get(1);System.out.println("linkedHashMapAccessOrder after get: " + linkedHashMapAccessOrder.toString());linkedHashMapAccessOrder.put(4, 444);System.out.println("linkedHashMapAccessOrder put: " + linkedHashMapAccessOrder.toString());} } import java.util.HashMap;/*** Created by itworker365 on 5/11/2017.*/ public class LRUCache {int capacity;HashMap<Integer, Entry> table = new HashMap<Integer, Entry>();Entry head = null;Entry tail = null;public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if (table.containsKey(key)) {Entry entry = table.get(key);//調整節點位置 NodeChangeAfterAccess(entry);return entry.value;} else {return -1;}}public void set(int key, int value) {if(table.containsKey(key)){//已經存在節點，則取出更新其valueEntry old = table.get(key);old.value = value;//調整節點位置 NodeChangeAfterAccess(old);}else{Entry created = new Entry(key, value, null, null);//LRU刪除隊尾元素if(table.size() >= capacity){table.remove(tail.key);removeNodeFromList(tail);MoveNodeToHead(created);}else{MoveNodeToHead(created);}table.put(key, created);}}private void NodeChangeAfterAccess(Entry old) {removeNodeFromList(old);MoveNodeToHead(old);}private void MoveNodeToHead(Entry entry) {//移動節點到頭節點entry.next = head;entry.pre = null;if(head!=null) {head.pre = entry;}head = entry;if(tail ==null) {tail = head;}}private void removeNodeFromList(Entry entry) {//獲取后需要調整鏈表關系除當前位置if (entry.pre != null) {entry.pre.next = entry.next;} else {head = entry.next;}if (entry.next != null) {entry.next.pre = entry.pre;} else {tail = entry.pre;}} } class Entry {int key;int value;Entry pre;Entry next;public Entry(int key, int value, Entry pre, Entry next) {this.key = key;this.value = value;this.pre = pre;this.next = next;} }

?

轉載于:https://www.cnblogs.com/it-worker365/p/6839611.html

總結

以上是生活随笔為你收集整理的LRU Cache的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。