Java面试题：实现一个基于链表的LRU缓存 |21xrx.com

Java面试题：实现一个基于链表的LRU缓存

2023-06-14 20:51:49 深夜i -- --

Java LRU缓存链表

在处理大量数据时，缓存对于提高性能至关重要。LRU（最近最少使用）缓存是其中一种常见的缓存实现方式。下面我们来实现一个基于链表的LRU缓存。

实现过程

我们可以通过Java的LinkedList类实现链表。对于LRU缓存，我们需要维护两个数据结构：

1. LinkedList：维护缓存元素的顺序，越靠前的元素是最近访问的元素

2. HashMap：快速查询元素是否在缓存中，并能快速获取缓存元素。

在实现缓存过程中，我们需要创建一个类LRUCache来维护缓存的相关信息，并实现以下功能：

1. 添加元素

若元素已存在，则将元素移动至链表最前端；若不存在，则进行以下操作：

- 若缓存未满，则将元素添加至链表最前端和HashMap中。

- 若缓存已满，则移除链表最后一个元素，并将新元素添加至链表最前端和HashMap中。

2. 获取元素

若元素存在于缓存中，则将其移动至链表最前端并返回元素值；若不存在，则返回-1。

代码实现


import java.util.*;
class LRUCache {
  private int capacity;
  private Map
  map;
 
  private LinkedList
  list;
 
  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();
    this.list = new LinkedList<>();
  }
  public int get(int key) {
    if (map.containsKey(key)) {
      list.remove(new Integer(key)); // 从List中删除key
      list.addFirst(key); // 将key添加到List头部
      return map.get(key); // 返回缓存值
    } else
      return -1;
    
  }
  public void put(int key, int value) {
    if (map.containsKey(key)) {
      list.remove(new Integer(key)); // 从List中删除key
    } else if (map.size() == capacity) {
      int last = list.removeLast(); // 从List中删除最后一个元素
      map.remove(last); // 从Map中删除最后一个元素
    }
    list.addFirst(key); // 将key添加到List头部
    map.put(key, value); // 将值添加到Map中
  }
}

上一篇: idea打包java可执行jar包

下一篇: Java中如何将字符串转换为整型（int）

评论区

()

相似文章