深圳那个网站建设/新产品宣传推广策划方案

一、Bloom Filter

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

from bitarray import bitarray
import mmh3
class BloomFilter:def __init__(self, size, hash_num):self.size = sizeself.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.sizeself.bit_array[res] = 1def 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 -1v = self.dic.pop(key)self.dic[key] = vreturn vdef 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 += 1self.remain -= 1self.dic[key] = value

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

class Node: # 定义双向链表的节点def __init__(self, key = -1, val = -1):self.key = key # 由于后面需要删除哈希表中的key，因此需要存下self.val = valself.next = Noneself.prev = Noneclass LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.dic = dict()# 定义一个伪头和伪尾，便于找头、找尾、头删、尾插# 注意伪头这边才是最近最久未使用元素所在self.head = Node()self.tail = Node()self.head.next = self.tailself.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.valreturn -1# 插入元素，原来有就删除了，然后尾插，更新dic# 如果超出容量，就删头，且在dic中删除对应的keydef put(self, key: int, value: int) -> None:if key in self.dic:self.__remove(self.dic[key])tmp = Node(key, value)self.dic[key] = tmpself.__add(tmp)if len(self.dic) > self.capacity:tmp = self.tail.prevself.__remove(tmp)del self.dic[tmp.key]def __remove(self, node):p = node.prevn = node.nextp.next = nn.prev = pdef __add(self, node): # 添加肯定是在头部添加tmp = self.head.nextself.head.next = nodenode.next = tmptmp.prev = nodenode.prev = self.head