首页 > algorithm > Bloom Filter

Bloom Filter

记得几年前跟未曾谋面的网友 黄晓强@Blizzard 在讨论Hash map hash函数值的唯一性(隐含分布均匀性)以及hash函数本身性能的时候,问及他是怎么做的,结论跟Bloom Filter的原理是一样的。

比如:从分布和唯一性来看,crc32比不上md5,更比不上sha1,但是性能是反过来的。而用于hashmap的hash函数对性能会产生直接影响,合理的hash函数能尽可能保持hash值的唯一性(不至于最后还要进行多次比较),还能保证足够的性能。

这里介绍 Bloom Filter 跟 黄晓强 他们的做法是一样的,就是利用多个简单高效的hash函数计算key的hash值,存入一个大的向量,如果测试一个key的hash值不匹配,那么这个key一定不存在,如果匹配,说明这个key是存在的(这里只是可能,所有通过hash值去判断唯一性都是不对的,只是概率问题)

JS实现: https://github.com/jasondavies/bloomfilter.js

Related posts:

  1. gitlab安装中遇到的问题及解决办法
  2. 由CSDN泄密想到的:MySQL数据库验证过程的改进、密码存储及验证方法的总结
分类: algorithm 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.