布隆过滤器、LRU Cache

布隆过滤器（Bloom Filter）

布隆过滤器 VS HashTable

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

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

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

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

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

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

示意图

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

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

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

案例

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

实现

• Python
  • https://www.geeksforgeeks.org/bloom-filters-introduction-and-python-implementation/
  • https://github.com/jhgg/pybloof
• Java
  • https://github.com/lovasoa/bloomfilter/blob/master/src/main/java/BloomFilter.java
  • https://github.com/Baqend/Orestes-Bloomfilter

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;
}