# 哈希+海量数据处理
常见哈希函数:
直接定值法
除留余数法:%len(表的长度)
哈希冲突:不同的值映射到相同的位置
闭散列的开放定址法:数组方法
开散列—拉链法—-哈希桶
负载因子:表中已有的数据个数/表的长度
位图的应用:
40亿个无符号整型,给一个无符号整型,如何判断一个数是否在这个集合中
位图只能处理整型
布隆过滤器:位图的衍生
针对字符串设计一个和位图差不多的数据结构
布隆解决方式:这个问题不可以解决,降低误判概率
每个值映射一个位置容易冲突,每个值可以映射多个位置,映射多各位,还时存在误判,但是误判的概率降低了,因为要映射多个位都被占用冲突,才会误判
布隆过滤器,出发点是节省空间,效率高,
布隆过�