一个 Cuckoo Filter 的 Go 库,根据CMU论文实现的BloomFilter的替代物

Go4Fun · · 3580 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

## [goCuckoo](https://github.com/zheng-ji/goCuckoo) [![Build Status](https://travis-ci.org/zheng-ji/goCuckoo.svg)](https://travis-ci.org/zheng-ji/goCuckoo) [![GoDoc](https://godoc.org/github.com/zheng-ji/goCuckoo?status.svg)](https://godoc.org/github.com/zheng-ji/goCuckoo) A Cuckoo hashing, substituting for bloom filter. written by Go 一个 Cuckoo Filter 的 Go 库,根据CMU论文实现的BloomFilter的替代物 ![goCuckoo](https://cloud.githubusercontent.com/assets/1414745/17084380/8c3a4896-51ee-11e6-869e-b087226cc5ce.jpg) Description ----------- 面对海量数据,我们需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这类数据结构叫过滤器,常用的选择是 `Bloom Filter`. 而 `Cuckoo Filter` 是它的优化变种。 `Bloom Filter` 的位图模式有两个问题: * 误报,它能判断元素一定不存在,但只能判断可能存在,因为存在其它元素被映射到部分相同位上,导致该位置1,那么一个不存在的元素可能会被误报成存在; * 漏报,如果删除了某个元素,导致该映射位被置0,那么本来存在的元素会被漏报成不存在。 `Cuckoo Filter`,可以确保该元素存在的必然性,又可以在不违背此前提下删除任意元素,仅仅比 `Bloom Filter` 牺牲了微量空间效率。 它的的数据模型: * 每个元素对应两个哈希算法,在哈希碰撞时会启用备用哈希算法。 * 每一个桶是有4路的,每个槽对应一个指纹。 ![model](https://cloud.githubusercontent.com/assets/1414745/17103421/c97635e0-52b0-11e6-83ac-1b1fdbb5d31c.png) Feature -------- * Deletion Support * FastLoopUp O(1) * High Space Utilization,4-way set-associative table: > 95% entries occupied * Subsituting for Bloom Filters Installation ------------- ``` go get github.com/zheng-ji/goCuckoo ``` Example ------- ```go import ( "fmt" "github.com/zheng-ji/goCuckoo" ) func main() { // speicify capacity filter := cuckoo.NewCuckooFilter(10000) filter.Insert([]byte("zheng-ji")) filter.Insert([]byte("stupid")) filter.Insert([]byte("coder")) if filter.Find([]byte("stupid")) { fmt.Println("exist") } else { fmt.Println("Not exist") } filter.Del([]byte("stupid")) filter.Println(filter.Size()) } ``` Documentation ------------- - [CMU Paper](http://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf) - [CMU PPT](http://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pptx) - [CoolShell Article](http://coolshell.cn/articles/17225.html) License ------- Copyright (c) 2016 by [zheng-ji](http://zheng-ji.info) released under MIT License.

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3580 次点击  ∙  4 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传