您现在的位置:首页 --> 查看专题: Cuckoo
对于海量数据处理业务,我们通常需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这种数据结构通常又叫过滤器(filter)。考虑这样一个场景,上网的时候需要在浏览器上输入URL,这时浏览器需要去判断这是否一个恶意的网站,它将对本地缓存的成千上万的URL索引进行过滤,如果不存在,就放行,如果(可能)存在,则向远程服务端发起验证请求,并回馈客户端给出警告。
索引的存储又分为有序和无序,前者使用关联式容器,比如B树,后者使用哈希算法。这两类算法各有优劣:比如,关联式容器时间复杂度稳定O(logN),且支持范围查询;又比如哈希算法的查询、增删都比较快O(1),但这是在理想状态下的情形,遇到碰撞严重的情况,哈希算法的时间复杂度会退化到O(n)。因此,选择一个好的哈希算法是很重要的。
[ 共1篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [68] Go Reflect 性能
- [68] 如何拿下简短的域名
- [67] Oracle MTS模式下 进程地址与会话信
- [62] IOS安全–浅谈关于IOS加固的几种方法
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
赞助商广告