实现lru哈希淘汰思路-DPDK中文网

LRU（Least Recently Used，最近最少使用）缓存淘汰算法是一种常用的缓存管理策略，用于确定在缓存空间满时，应该淘汰哪个数据。以下是实现LRU缓存淘汰的思路：

数据结构选择

哈希表：用于快速查找缓存中的数据，键为数据的唯一标识（如ID），值为对应的数据和其位置。
双向链表：用于维护数据的使用顺序。头部表示最近使用的数据，尾部表示最久未使用的数据。当访问或插入新数据时，需要调整链表的顺序。

主要操作

获取数据：
- 查找哈希表，如果存在：
  - 将该节点移到双向链表的头部（表示最近使用）。
  - 返回该节点的数据。
- 如果不存在，返回-1或者其他指示未找到的数据。
插入/更新数据：
- 如果哈希表中已存在该数据：
  - 更新其值，并将对应节点移到链表的头部。
- 如果哈希表中不存在且缓存未满：
  - 将新数据添加到双向链表的头部，同时在哈希表中记录其位置。
- 如果缓存已满：
  - 淘汰双向链表尾部的数据（即最久未使用的数据），并从哈希表中删除对应项。
  - 将新数据添加到双向链表头部，并在哈希表中记录其位置。

示例代码

以下是一个简单的Python实现示例：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表
        self.head = Node(0, 0)  # 哨兵头结点
        self.tail = Node(0, 0)  # 哨兵尾结点
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        """移除节点"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
        
    def _add_to_head(self, node: Node):
        """添加节点到头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 移动到头部并返回值
            self._remove(node)
            self._add_to_head(node)
            return node.value
        
        return -1

    def put(self, key: int, value: int) -> None:
        
         if key in self.cache:
             # 更新现有节点并移动到头部 
             existing_node= self.cache[key] 
             existing_node.value=value 
             # Move the updated node to head of the list 
             this._remove(existing_node) 
             this._add_to_head(existing_node)
         else:
              newNode=Node(key,value)
              if len(this.cache)==this.capacity:
                   tail=this.tail.prev 
                   this._remove(tail) 
                   del this.cache[tail.key]
               
               this._add_to_head(newNode)
               this.cache[key]=newNode