LRU Cache & Bloom Filter

Cache 缓存

1. 记忆

2. 空间有限

3. 钱包 - 储物柜

4. 类似背代码模板，O(n) 变 O(1)

LRU Cache

缓存替换算法

1. Least Recently Used（最近最少使⽤的淘汰掉）

2. Hash Table + Double LinkedList（哈希表 + 双向链表）

3. O(1) 查询（cache只要查询第一个）

4. O(1) 修改、更新（同3；要是处理最中间的话就是O(n)了）

双向链表实现：

LFU Cache

也记录元素出现的频次，即使最近刚出现的，也未必就会挪到最前面。

缓存内始终按频次排序，如果超了缓存空间限制，还是新进的元素把原先频次最低的顶走。

1. LFU - least frequently used（最近最不常用⻚⾯置换算法，频次越高的放越前面)

2. LRU - least recently usd（最近最少使⽤页⾯置换算法)

Leetcode 146. LRU缓存机制 https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

解：

考虑用 ordered dict 实现

 1 import collections
 2 class LRUCache:
 3     def __init__(self, capacity: int):
 4         self.dic = collections.OrderedDict()
 5         self.remain = capacity
 6 
 7     def get(self, key: int) -> int:
 8         if key not in self.dic:
 9             return -1
10         v = self.dic.pop(key)
11         self.dic[key] = v  # 如果在key在dict中，就pop出来后再set成最新的key
12         return v
13 
14     def put(self, key: int, value: int) -> None:
15         if key in self.dic:
16             self.dic.pop(key)
17         else:
18             if self.remain > 0:
19                 self.remain -= 1
20             else:  # 如果已经满了，就删除第一个key-value对（即最早put的键值对。令last=False即可）
21                 self.dic.popitem(last=False)
22                 
23         self.dic[key] = value   # put进去作为最新的键值对
24 
25 
26 # Your LRUCache object will be instantiated and called as such:
27 # obj = LRUCache(capacity)
28 # param_1 = obj.get(key)
29 # obj.put(key,value)

View Code

布隆过滤器 Bloom Filter

过滤器的作用：判断元素在还是不在。（如图查询 w 在不在集合中）

布隆过滤器：⼀个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在⼀个集合中（如果检测出元素不在集合中，那一定不在；如果检测出元素在集合中，有一定可能判断错误）。

它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。布隆过滤器后面一定要跟一个完备的搜索系统。

判断 C 不存在，一定正确；判断 B 存在，判断错了

案例

1. ⽐特币网络

2. 分布式系统(Map-Reduce)