Tôi đang tìm cấu trúc dữ liệu hoạt động tương tự như bảng băm, nhưng vị trí bảng có giới hạn kích thước. Khi số lượng các mục trong băm đạt đến giới hạn kích thước, hàm culling nên được gọi để loại bỏ các cặp khóa/giá trị được lấy ít nhất trong bảng.Loại cấu trúc dữ liệu giống như bảng băm, nhưng các phím thường dùng được xóa là gì?
Dưới đây là một số giả về những gì tôi đang làm việc trên:
class MyClass {
private Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public int myFunc(int n) {
if(cache.containsKey(n))
return cache.get(n);
int next = . . . ; //some complicated math. guaranteed next != n.
int ret = 1 + myFunc(next);
cache.put(n, ret);
return ret;
}
}
gì xảy ra là có một số giá trị của n mà myFunc() sẽ được gọi rất nhiều lần, nhưng nhiều giá trị khác của n mà sẽ chỉ được tính một lần. Vì vậy, bộ nhớ cache có thể lấp đầy với hàng triệu giá trị không bao giờ cần thiết nữa. Tôi muốn có một cách để bộ nhớ cache tự động xóa các phần tử không thường xuyên được truy xuất.
Điều này giống như một vấn đề phải được giải quyết, nhưng tôi không chắc cấu trúc dữ liệu mà tôi sẽ sử dụng để làm điều đó một cách hiệu quả. ai đó có thể chỉ cho tôi phương hướng đúng không?
Cập nhật Tôi biết điều này đã trở thành một vấn đề đã-được giải quyết. Nó được gọi là Cache LRU và dễ thực hiện bằng cách mở rộng lớp LinkedHashMap. Dưới đây là đoạn code mà kết hợp các giải pháp:
class MyClass {
private final static int SIZE_LIMIT = 1000;
private Map<Integer, Integer> cache =
new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest)
{
return size() > SIZE_LIMIT;
}
};
public int myFunc(int n) {
if(cache.containsKey(n))
return cache.get(n);
int next = . . . ; //some complicated math. guaranteed next != n.
int ret = 1 + myFunc(next);
cache.put(n, ret);
return ret;
}
}
Xem thêm http://stackoverflow.com/questions/224868/easy-simple-to-use-lru-cache-in-java. –