要實(shí)現(xiàn)LRU緩存，Java中最常見(jiàn)的方法是使用LinkedHashMap或手動(dòng)結(jié)合哈希表與雙向鍊錶。 1. 使用LinkedHashMap時(shí)，通過(guò)構(gòu)造函數(shù)傳入true啟用訪問(wèn)順序，並重寫removeEldestEntry方法控制容量；2. 手動(dòng)實(shí)現(xiàn)則需定義雙向鍊錶節(jié)點(diǎn)類，維護(hù)訪問(wèn)順序，操作包括添加、刪除和移動(dòng)節(jié)點(diǎn)；3. 若需線程安全，可使用同步塊或併發(fā)集合，但要注意性能影響。這些方法可根據(jù)需求選擇，兼顧效率與控制。

To implement an LRU (Least Recently Used) Cache in Java, you'll typically use a combination of data structures to efficiently track and remove the least recently used items when the cache reaches capacity. The most common approach is to use a doubly linked list along with a hash map .

Java actually provides a built-in class that makes this easier: LinkedHashMap . It maintains insertion or access order, which allows us to easily evict the least recently used entry.

Here's how to do it step by step:

Using LinkedHashMap for LRU Cache

Java's LinkedHashMap can be extended and customized to behave like an LRU cache by overriding the removeEldestEntry() method. This method controls whether the eldest entry should be removed when a new entry is added.

 import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        // Load factor 0.75f is standard; accessOrder true means we want access-order instead of insertion-order
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

This is a simple and effective way to build an LRU Cache if thread safety isn't required. Just make sure the constructor passes true as the third argument to enable access order.

Implementing from Scratch with HashMap Doubly Linked List

If you're implementing it without relying on LinkedHashMap , you'll need:

• A doubly linked list to keep track of the access order.
• A hash map to store key-node mappings for O(1) access.

Here's a high-level breakdown:

• Each node holds a key-value pair and references to previous and next nodes.
• When a key is accessed (get or put), move its node to the front (most recently used).
• When the cache is full, remove the last node (least recently used).

You'd define a Node class and manage operations like:

• Adding a node to the front.
• Removing a specific node.
• Moving a node to the front.

This version gives more control but requires careful handling of pointers and edge cases like removing the head or tail.

Handling Thread Safety

The above implementations are not thread-safe. If your application uses multiple threads, you have two options:

• Wrap access to the cache with synchronized blocks.
• Use a concurrent data structure or decorate the map with Collections.synchronizedMap() .

For example:

 Map<Integer, Integer> synchronizedMap = Collections.synchronizedMap(yourLRUMap);

However, this might affect performance under heavy concurrency. For production systems, consider using libraries or writing fine-grained locking mechanisms.

Implementing an LRU Cache in Java doesn't have to be hard — especially if you take advantage of built-in classes like LinkedHashMap . But understanding the internal mechanics (like doubly linked lists and hash maps) helps you debug and optimize better when things get more complex.

基本上就這些。

以上是如何在Java中實(shí)現(xiàn)LRU緩存？的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！