Tôi đang cố gắng triển khai bộ nhớ cache LRU của riêng mình. Có, tôi biết rằng Java cung cấp một LinkedHashMap cho mục đích này, nhưng tôi đang cố gắng thực hiện nó bằng cách sử dụng các cấu trúc dữ liệu cơ bản.ConcurrentModificationException khi cập nhật Iterator được lưu trữ (để thực hiện bộ nhớ cache LRU)
Từ đọc về chủ đề này, tôi hiểu rằng tôi cần một HashMap cho O (1) tra cứu khóa và danh sách được liên kết để quản lý chính sách trục xuất "ít được sử dụng gần đây nhất". Tôi tìm thấy những tài liệu tham khảo mà tất cả sử dụng một hashmap thư viện chuẩn nhưng thực hiện danh sách liên kết riêng của họ:
- "What data structures are commonly used for LRU caches and quickly locating objects?" (stackoverflow.com)
- "What is the best way to Implement a LRU Cache?" (quora.com)
- "Implement a LRU Cache in C++" (uml.edu)
- "LRU Cache (Java)" (programcreek.com)
bảng băm là nghĩa vụ phải lưu trữ trực tiếp một danh sách liên kết Node như tôi hiển thị bên dưới. Bộ nhớ cache của tôi sẽ lưu trữ các khóa Integer và các giá trị String.
Tuy nhiên, trong bộ sưu tập Java LinkedList không tiếp xúc với các nút nội bộ của mình, vì vậy tôi không thể lưu trữ chúng bên trong HashMap. Thay vào đó, tôi có thể có các chỉ mục cửa hàng HashMap vào LinkedList, nhưng sau đó nhận được một mục sẽ yêu cầu thời gian O (N). Vì vậy, tôi đã cố gắng để lưu trữ một ListIterator thay thế.
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;
public class LRUCache {
private static final int DEFAULT_MAX_CAPACITY = 10;
protected Map<Integer, ListIterator> _map = new HashMap<Integer, ListIterator>();
protected LinkedList<String> _list = new LinkedList<String>();
protected int _size = 0;
protected int _maxCapacity = 0;
public LRUCache(int maxCapacity) {
_maxCapacity = maxCapacity;
}
// Put the key, value pair into the LRU cache.
// The value is placed at the head of the linked list.
public void put(int key, String value) {
// Check to see if the key is already in the cache.
ListIterator iter = _map.get(key);
if (iter != null) {
// Key already exists, so remove it from the list.
iter.remove(); // Problem 1: ConcurrentModificationException!
}
// Add the new value to the front of the list.
_list.addFirst(value);
_map.put(key, _list.listIterator(0));
_size++;
// Check if we have exceeded the capacity.
if (_size > _maxCapacity) {
// Remove the least recently used item from the tail of the list.
_list.removeLast();
}
}
// Get the value associated with the key.
// Move value to the head of the linked list.
public String get(int key) {
String result = null;
ListIterator iter = _map.get(key);
if (iter != null) {
//result = iter
// Problem 2: HOW DO I GET THE STRING FROM THE ITERATOR?
}
return result;
}
public static void main(String argv[]) throws Exception {
LRUCache lruCache = new LRUCache(10);
lruCache.put(10, "This");
lruCache.put(20, "is");
lruCache.put(30, "a");
lruCache.put(40, "test");
lruCache.put(30, "some"); // Causes ConcurrentModificationException
}
}
Vì vậy, điều này dẫn đến ba vấn đề:
Vấn đề 1: Tôi nhận được một ConcurrentModificationException khi tôi cập nhật LinkedList sử dụng iterator mà tôi lưu trữ trong HashMap.
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:953)
at java.util.LinkedList$ListItr.remove(LinkedList.java:919)
at LRUCache.put(LRUCache.java:31)
at LRUCache.main(LRUCache.java:71)
Bài toán 2. Làm thế nào để lấy giá trị được chỉ bởi ListIterator? Có vẻ như tôi chỉ có thể lấy giá trị tiếp theo().
Sự cố 3. Có cách nào để thực hiện bộ nhớ cache LRU này bằng cách sử dụng các bộ sưu tập Java LinkedList, hay tôi thực sự phải thực hiện danh sách liên kết của riêng mình?
Vâng, không có cách nào bạn sẽ thực hiện công việc đó. Bạn sẽ phải tự thực hiện lại ít nhất một trong các cấu trúc dữ liệu này nếu bạn muốn phát minh lại bánh xe này. –