Sử dụng LinkedHashMap để triển khai bộ nhớ cache LRU

Question

Tôi đã cố gắng triển khai bộ nhớ cache LRU bằng LinkedHashMap. Trong tài liệu của LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html), nó nói:

Lưu ý rằng thứ tự chèn không bị ảnh hưởng nếu khóa được chèn lại vào bản đồ.

Nhưng khi tôi làm puts sau

public class LRUCache<K, V> extends LinkedHashMap<K, V> { 
    private int size; 

    public static void main(String[] args) { 
     LRUCache<Integer, Integer> cache = LRUCache.newInstance(2); 
     cache.put(1, 1); 
     cache.put(2, 2); 
     cache.put(1, 1); 
     cache.put(3, 3); 

     System.out.println(cache); 
    } 

    private LRUCache(int size) { 
     super(size, 0.75f, true); 
     this.size = size; 
    } 

    @Override 
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 
     return size() > size; 
    } 

    public static <K, V> LRUCache<K, V> newInstance(int size) { 
     return new LRUCache<K, V>(size); 
    } 

} 

Đầu ra là

{1=1, 3=3} 

nào chỉ ra rằng việc tái chèn đã ảnh hưởng đến trật tự. Có ai biết giải thích nào không?

Answer 1

Như được chỉ ra bởi @Jeffrey, bạn đang sử dụng accessOrder. Khi bạn tạo LinkedHashMap, tham số thứ ba chỉ định cách thứ tự được thay đổi.

"true for access-order, false for insertion-order" 

Đối với thực hiện chi tiết hơn về LRU, bạn có thể xem xét điều này http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Answer 2

Nhưng bạn không sử dụng thứ tự chèn, bạn đang sử dụng access order.

thứ tự lặp là thứ tự mà mục của nó là cuối cùng truy cập, từ gần đây ít được tiếp cận với nhiều nhất thời gian gần đây (truy cập theo đơn đặt hàng)

...

Gọi phương thức đặt hoặc nhận được truy cập vào mục nhập tương ứng

Vì vậy, đây là trạng thái bộ nhớ cache của bạn khi bạn sửa đổi bộ nhớ cache:

LRUCache<Integer, Integer> cache = LRUCache.newInstance(2); 
    cache.put(1, 1); // { 1=1 } 
    cache.put(2, 2); // { 1=1, 2=2 } 
    cache.put(1, 1); // { 2=2, 1=1 } 
    cache.put(3, 3); // { 1=1, 3=3 } 

Answer 3

Đây là thực hiện của tôi bằng cách sử dụng LinkedHashMap trong AccessOrder. Nó sẽ di chuyển phần tử truy cập mới nhất lên mặt trước, nó chỉ chịu phí O (1) vì các phần tử bên dưới được tổ chức trong danh sách được liên kết kép trong khi cũng được lập chỉ mục bởi hàm băm. Vì vậy, các hoạt động get/put/top_newest_one đều có giá O (1).

class LRUCache extends LinkedHashMap<Integer, Integer>{ 
    private int maxSize; 
    public LRUCache(int capacity) { 
     super(capacity, 0.75f, true); 
     this.maxSize = capacity; 
    } 

    //return -1 if miss 
    public int get(int key) { 
     Integer v = super.get(key); 
     return v == null ? -1 : v; 
    } 

    public void put(int key, int value) { 
     super.put(key, value); 
    } 

    @Override 
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 
     return this.size() > maxSize; //must override it if used in a fixed cache 
    } 
}