cuckoo

README

goCuckoo

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

一个 CuckooFilter 的 Go 库, BloomFilter 的替代物

Description

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

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

• 误报，它能判断元素一定不存在，但只能判断可能存在，因为存在其它元素被映射到部分相同位上，导致该位置1，那么一个不存在的元素可能会被误报成存在；
• 漏报，如果删除了某个元素，导致该映射位被置0，那么本来存在的元素会被漏报成不存在。

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

• 每个元素对应两个哈希算法，在哈希碰撞时会启用备用哈希算法。
• 每一个桶是有4路的槽，每个槽对应一个指纹。

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

import (
	"fmt"
	"github.com/zheng-ji/goCuckoo"
)

func main() {
    // speicify capacity 
	filter := cuckoo.NewFilter(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
• CMU PPT
• CoolShell Article

License

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

Documentation

Index

• Constants
• Variables
• type Bucket
• type Filter
  • func NewFilter(capacity uint) *Filter
  • func (filter *Filter) Del(data []byte) bool
  • func (filter *Filter) Find(data []byte) bool
  • func (filter *Filter) Insert(data []byte) bool
  • func (filter *Filter) Size() int
• type Signature

Constants

const (
	// NotFound const
	NotFound = -1

	// SlotSize const
	SlotSize = 4

	// SignatureSize const
	SignatureSize = 1

	// MaxCuckooCount max times to try when collision
	MaxCuckooCount = 800
)

Variables

var Empty = Signature{0}

Empty Signature

Types

type Bucket

type Bucket [SlotSize]Signature

Bucket Type, has slotsize signature

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

Filter struct

func NewFilter

func NewFilter(capacity uint) *Filter

NewFilter Init a Filter with capacity

func (*Filter) Del

func (filter *Filter) Del(data []byte) bool

Del Func:delete entry

func (*Filter) Find

func (filter *Filter) Find(data []byte) bool

Find Func，check an entry exist or not

func (*Filter) Insert

func (filter *Filter) Insert(data []byte) bool

Insert Func，Insert an entry

func (*Filter) Size

func (filter *Filter) Size() int

Size Fun: get size of Filter's element

type Signature

type Signature [SignatureSize]byte

Signature Type,mean FingerPrint