算法训练营-布隆过滤器、LRUCache的实现和应用

布隆过滤器-Bloom filter

Bloom filter vs Hash Table

一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点：空间效率和查询时间都远远超过一般的算法。

缺点：有一定的误识别率和删除困难。

结论：如果这个元素在布隆过滤器查不到，那肯定不存在；如果查得到，那可能存在。

案例

1，比特币网络
2，分布式系统（Map-Reduce）——Hadoop、Search Engine
3，Redis缓存
4，垃圾邮件、评论等的过滤

实现

LRUCache

Cache缓存

1，记忆
2，钱包-储物柜
3，代码模块

• 两个要素：大小、替换策略
• Hash Table + Double LinkedList
• O(1)查询，修改、更新

代码示例：

# Python 
class LRUCache(object): 	
    def __init__(self, capacity): 		
        self.dic = collections.OrderedDict() 		
        self.remain = capacity	def get(self, key): 		
        if key not in self.dic: 			
            return -1 		
            v = self.dic.pop(key) 		
            self.dic[key] = v   # key as the newest one 		
            return v 	
        def put(self, key, value): 		
            if key in self.dic: 			
                self.dic.pop(key) 		
            else: 			
                if self.remain > 0: 				
                    self.remain -= 1 			
                else:   # self.dic is full				
                    self.dic.popitem(last=False) 		
            self.dic[key] = value

/** * 使用 哈希表 + 双端链表 实现 */
class LinkedNode {  constructor(key = 0, val = 0) {    
    this.key = key    
    this.val = val    
    this.prev = null    
    this.next = null  }
}

class LinkedList {  
    constructor() {    this.head = new LinkedNode()    this.tail = new LinkedNode()    this.head.next = this.tail    this.tail.prev = this.head  }  insertFirst(node) {    node.next = this.head.next    node.prev = this.head    this.head.next.prev = node    this.head.next = node  }  remove(node) {    node.prev.next = node.next    node.next.prev = node.prev  }  removeLast() {    if (this.tail.prev === this.head) return null    let last = this.tail.prev    this.remove(last)    return last  }}/** * @param {number} capacity */var LRUCache = function(capacity) {  this.capacity = capacity  this.keyNodeMap = new Map()  this.cacheLink = new LinkedList()};/**  * @param {number} key * @return {number} */LRUCache.prototype.get = function(key) {  if (!this.keyNodeMap.has(key)) return -1  let val = this.keyNodeMap.get(key).val  this.put(key, val)  return val};/**  * @param {number} key  * @param {number} value * @return {void} */LRUCache.prototype.put = function(key, value) {  let size = this.keyNodeMap.size  if (this.keyNodeMap.has(key)) {    this.cacheLink.remove(this.keyNodeMap.get(key));     --size   }  if (size >= this.capacity) {    this.keyNodeMap.delete(this.cacheLink.removeLast().key)  }  let node = new LinkedNode(key, value)  this.keyNodeMap.set(key, node)  this.cacheLink.insertFirst(node)};

参考链接

布隆过滤器(Bloom Filter)的原理和实现
使用BloomFilter布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
Bloom Filters – Introduction and Implementation
Github-Pybloof
布隆过滤器Java实现示例1
布隆过滤器Java实现示例2
Understanding the Meltdown exploit – in my own simple words
Cache replacement policies
LRU Cache Python代码