《leetcode》哈希表

目录

146. LRU 缓存

146. LRU 缓存

题目描述：请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路：LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

• 对于 get 操作，首先判断 key 是否存在：
• 如果 key 不存在，则返回 -1−1；
• 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
• 对于 put 操作，首先判断 key 是否存在：
• 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
• 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

LRU缓存机制，即采用最近最少使用的缓存策略。它的原则是，如果一个数据最近没有被访问到，那么它将来被访问的几率也很小，也就是说当限定的内存空间已没有其他空间可用时，应该把最久没有访问到的数据去除掉。

1.  
   class LRUCache {
2.  
   // 定义双链表
3.  
   class DLinkNode{
4.  
   int key;
5.  
   int value;
6.  
   DLinkNode pre;
7.  
   DLinkNode next;
8.  
   public DLinkNode(){}
9.  
   public DLinkNode(int _key,int _value){
10.  
    key=_key;
11.  
    value=_value;
12.  
    }
13.  
    }
14.  
    //定义哈希表、头指针、尾指针等全局变量
15.  
    private Map<Integer,DLinkNode>cache=new HashMap<Integer,DLinkNode>();
16.  
    int size;
17.  
    int capacity;
18.  
    private DLinkNode head,tail;
19.  
    //定义LRUCache函数体
20.  
    public LRUCache(int capacity) {
21.  
    this.size=0;
22.  
    this.capacity=capacity;
23.  
    head=new DLinkNode();
24.  
    tail=new DLinkNode();
25.  
    head.next=tail;
26.  
    tail.pre=head;
27.  
    }
28.  
     
29.  
    public int get(int key) {
30.  
    DLinkNode node=cache.get(key);
31.  
    if(node==null)
32.  
    return -1;
33.  
    //把查到的结点移到头结点上
34.  
    moveToHead(node);
35.  
    return node.value;
36.  
    }
37.  
     
38.  
    public void put(int key, int value) {
39.  
    //1、先查有没有这个结点
40.  
    DLinkNode node=cache.get(key);
41.  
    if(node==null){
42.  
    DLinkNode temp=new DLinkNode(key,value);
43.  
    cache.put(key,temp);
44.  
    addToHead(temp);
45.  
    size;
46.  
    if(size>capacity){
47.  
    DLinkNode tailnode=deleteTail();
48.  
    cache.remove(tailnode.key);
49.  
    --size;
50.  
    }
51.  
    }
52.  
    else{
53.  
    node.value=value;
54.  
    moveToHead(node);
55.  
    }
56.  
    }
57.  
    //将结点插入至头结点后
58.  
    public void addToHead(DLinkNode node){
59.  
    node.next=head.next;
60.  
    head.next.pre=node;
61.  
    node.pre=head;
62.  
    head.next=node;
63.  
    }
64.  
    //把查到的结点移到头结点上
65.  
    public void moveToHead(DLinkNode node){
66.  
    deleteNode(node);
67.  
    addToHead(node);
68.  
    }
69.  
    void deleteNode(DLinkNode node){
70.  
    node.pre.next=node.next;
71.  
    node.next.pre=node.pre;
72.  
    }
73.  
    //删除尾结点
74.  
    public DLinkNode deleteTail(){
75.  
    DLinkNode deleteres=tail.pre;
76.  
    deleteNode(deleteres);
77.  
    return deleteres;
78.  
    }
79.  
    }
80.  
     
81.  
    /**
82.  
    * Your LRUCache object will be instantiated and called as such:
83.  
    * LRUCache obj = new LRUCache(capacity);
84.  
    * int param_1 = obj.get(key);
85.  
    * obj.put(key,value);
86.  
    */

这篇好文章是转载于：学新通技术网