一个比 BloomFilter 更优的过滤器, CuckooFilter

2016-07-29 22:43:52 +08:00
 zhengji

阅读 CMU 的论文PPT,以及Coolshell 的相关文章,用 Go 语言实现了论文提到的算法,做成一个库, goCuckoo GitHub

A Cuckoo hashing, substituting for bloom filter. written by Go

一个 Cuckoo Filter 的 Go 库

Description

面对海量数据,我们需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这类数据结构叫过滤器,常用的选择是 Bloom Filter. 而 Cuckoo Filter 是它的优化变种。

Bloom Filter 的位图模式有两个问题:

Cuckoo Filter,可以确保该元素存在的必然性,又可以在不违背此前提下删除任意元素,仅仅比 Bloom Filter 牺牲了微量空间效率。 它的的数据模型:

Feature

Installation

go get github.com/zheng-ji/goCuckoo

Example

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

License

Copyright (c) 2016 by zheng-ji released under MIT License.

3743 次点击
所在节点    程序员
4 条回复
3dwelcome
2016-07-29 23:10:27 +08:00
牛逼
mscorp
2016-07-29 23:41:23 +08:00
效率怎么样?误差率呢
KyleMeow
2016-07-29 23:49:33 +08:00
酷壳上也有个文章是介绍这个的,详细一些
knightdf
2016-07-30 00:08:42 +08:00
Bloom Filter 本来就不应该做删除,我用 bloom 不就是为了节省内存而浪费一点精度?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/295902

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX