您现在的位置:首页 --> 查看专题: Cuckoo
对于海量数据处理业务,我们通常需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这种数据结构通常又叫过滤器(filter)。考虑这样一个场景,上网的时候需要在浏览器上输入URL,这时浏览器需要去判断这是否一个恶意的网站,它将对本地缓存的成千上万的URL索引进行过滤,如果不存在,就放行,如果(可能)存在,则向远程服务端发起验证请求,并回馈客户端给出警告。
索引的存储又分为有序和无序,前者使用关联式容器,比如B树,后者使用哈希算法。这两类算法各有优劣:比如,关联式容器时间复杂度稳定O(logN),且支持范围查询;又比如哈希算法的查询、增删都比较快O(1),但这是在理想状态下的情形,遇到碰撞严重的情况,哈希算法的时间复杂度会退化到O(n)。因此,选择一个好的哈希算法是很重要的。
[ 共1篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [70] Go Reflect 性能
- [12] 公钥私钥加密解密数字证书数字签名详解
- [12] 系统工程师的自我修养- sed篇
- [12] osx平台上lol英雄联盟launcher启
- [11] iTerm2 (Mac Terminal)
- [11] iOS可视化编程 Tips 之“无需代码设置
- [11] 浅谈Web安全验证码
- [11] 正态分布的前世今生(一)
- [11] 基于HTTP缓存轻松实现客户端应用的离线支持
- [10] iOS并发编程(Concurrency Pr
赞助商广告