算法训练营 - 布隆过滤器、LRU Cache - 《算法》

布隆过滤器（Bloom Filter）
LRU Cache

布隆过滤器（Bloom Filter）

布隆过滤器 VS HashTable

布隆过滤器和哈希表类似。

哈希表：HashTable + 拉链存储重复元素。

对于哈希表，不仅存在哈希函数来得到 index 值，还要把整个元素全部放到哈希表中。哈希表是一种没有误差的数据结构，且有多少元素，每个元素有多大，所以的元素需要占用的内容空间，在哈希表中都要找相应的内存大小给存起来。

很多时候，在工业级应用中，我们并不需要存所有的元素本身，只需要存储这个元素在表中是否存在。这种情况下，如果只想查询有还是没有，这时我们需要一种更高效的数据结构。

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

布隆过滤器优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率、删除困难。

示意图

如果一个元素它所对应的二进制位只要一个为 0，就说明这个元素不在布隆过滤器的索引中。
但是当一个元素刚好分配的三个二进制都为 1 时，我们不能肯定说元素存在于布隆过滤器的索引中，只能说是可能存在。

在布隆过滤器中查询元素，如果查不到，说明肯定不在，如果元素在布隆过滤器中二进制位都是 1，只能说它可能存在。

布隆过滤器，只适合在外面当缓存使用，进行快速判断。当元素查到，就会继续在数据库中去查。布隆过滤器可以节省访问数据库时间。

案例

比特币网络
分布式系统（Map-Reduce）- Hadoop、search engine
Redis 缓存
垃圾邮件、评论过滤等

实现

LRU Cache

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

LRU: least recent use 最近最少使用

工作示例

替换策略

LFU - least frequently used
- 统计每个元素被使用的频次最少的，放到最下面，最先被淘汰掉
LRU - least recently used
- 最先淘汰不常使用的

替换算法总览：https://en.wikipedia.org/wiki/Cache_replacement_policies

相关题目

LRU 缓存

// LRU 缓存
// 双向链表 + HashTable
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity;
  this.hash = {};
  this.count = 0;
  this.dummyHead = new ListNode();
  this.dummyTail = new ListNode();
  this.dummyHead.next = this.dummyTail;
  this.dummyTail.prev = this.dummyHead;
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const node = this.hash[key];
  if (node == null) return -1;
  this.moveToHead(node);
  return node.value;
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  const node = this.hash[key];
  if (node == null) {
    if (this.count == this.capacity) {
      this.remove();
    }
    const newNode = new ListNode(key, value);
    this.hash[key] = newNode;
    this.unshift(newNode);
    this.count++;
  } else {
    node.value = value;
    this.moveToHead(node);
  }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
 function ListNode (key, value) {
  this.key = key;
  this.value = value;
  this.prev = null;
  this.next = null;
}
LRUCache.prototype.swap = function (node) {
  const temp1 = node.prev,
        temp2 = node.next;
  temp1.next = temp2;
  temp2.prev = temp1;
}
LRUCache.prototype.unshift = function (node) {
  node.prev = this.dummyHead;
  node.next = this.dummyHead.next;
  this.dummyHead.next.prev = node;
  this.dummyHead.next = node;
}
LRUCache.prototype.moveToHead = function (node) {
  this.swap(node);
  this.unshift(node);
}
LRUCache.prototype.remove = function () {
  const tail = this.pop();
  delete this.hash[tail.key];
  this.count--;
}
LRUCache.prototype.pop = function () {
  const tail = this.dummyTail.prev;
  this.swap(tail);
  return tail;
}