• 展开微博窗口
  • QQ:52619941
  • 微信:cnmemory
  • 展开分类目录
  • 还没有账号?

Memory

对布隆过滤器(Bloom Filter)一点总结

布隆过滤器是一种空间利用率高,可以用来对数据进行排重过滤处理的数据结构,具有以下两点特征:

  • 判定为不存在的数据一定不存在
  • 判定为存在的数据可能存在也可能不存在

存在的数据如果实际上并不存在,称为false positive,那么为什么会有这种现象呢?

布隆过滤器是通过khash函数将某个key映射到m个的比特位上。那么某个key的比特位有可能会被其他的一个或多个key占用,即会产生误判为存在的情况,所以这个误判率取决于…

笔记

磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO

星期三