布隆过滤器及LRU Cache的实现

一、Bloom Filter

它是什么？：一个很长的二进制向量和一系列随机映射函数。
用途：布隆过滤器可以用于检索、一个元素是否在一个集合中。
优点：空间效率和查询时间都远远超过一般的算法，
缺点：有一定的误识别率和删除困难。

from bitarray import bitarray
import mmh3
class BloomFilter:
    def __init__(self, size, hash_num):
        self.size = size
        self.hash_num = hash_num # 将一个数hash成几个二进制位？
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, s):
        for seed in range(self.hash_num):
            res = mmh3.hash(s, seed) % self.size
            self.bit_array[res] = 1

    def look_up(self, s):
        for seed in range(self.hash_num): # 得到三个二进制位
            res = mmh3.hash(s, seed) % self.size # seed就是加的盐
            if not self.bit_array[res]: # 有一位是0, 就是肯定不存在的
                return "Nope"
        return "Probably" # 所有位都存在, 也只是可能存在而已

二、LRU Cache

凰凰科普

1. Cache缓存，LRU Cache就是采用LRU算法实现的缓存。
2. LRU算法，学过操作系统的同学相信应该对其不陌生，这是一种内存淘汰策略，当发生缺页中断时, 需要从硬盘请求调页到内存，如果内存满了，就需要淘汰一些内存页，淘汰那些页？LRU规定淘汰最近最久未使用的页！

两个要素：大小 、替换策略
实现：Hash Table + Double LinkedList

特点:
	O(1) 查询
	O(1) 修改、更新

1、OrderedDict实现

class LRUCache:
    def __init__(self, capacity: int):
        self.dic = collections.OrderedDict()
        self.remain = capacity # size和cap是有区别的哈

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        v = self.dic.pop(key)
        self.dic[key] = v
        return v

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self.dic.pop(key)
        else:
            if not self.remain: # 维护cache的大小
                self.dic.popitem(last = False)
                self.remain += 1
            self.remain -= 1
        self.dic[key] = value

2、哈希 + 双向链表（面试建议）

class Node: # 定义双向链表的节点
    def __init__(self, key = -1, val = -1):
        self.key = key # 由于后面需要删除哈希表中的key，因此需要存下
        self.val = val
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = dict()
        # 定义一个伪头和伪尾，便于找头、找尾、头删、尾插
        # 注意伪头这边才是最近最久未使用元素所在
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # 查询元素，在哈希表中查，然后找到结点更新双向链表的尾元素
    def get(self, key: int) -> int:
        if key in self.dic:
            v = self.dic[key]
            self.__remove(v)
            self.__add(v)
            return v.val
        return -1

    # 插入元素，原来有就删除了，然后尾插，更新dic
    # 如果超出容量，就删头，且在dic中删除对应的key
    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self.__remove(self.dic[key])
        tmp = Node(key, value)
        self.dic[key] = tmp
        self.__add(tmp)
        if len(self.dic) > self.capacity:
            tmp = self.tail.prev
            self.__remove(tmp)
            del self.dic[tmp.key]
    
    def __remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
    
    def __add(self, node): # 添加肯定是在头部添加
        tmp = self.head.next
        self.head.next = node
        node.next = tmp
        tmp.prev = node
        node.prev = self.head