package main

import (
	"math/rand"
	"time"
)

const (
	TSize = 1024 // 假设表的大小为 1024
)

var (
	T1 = make(map[int]any, TSize) // 哈希表 1
	T2 = make(map[int]any, TSize) // 哈希表 2
)

// 哈希函数 1
// 返回随机数作为哈希值
func H1(x any) int {
	rand.Seed(time.Now().UnixNano())
	return rand.Intn(TSize)
}

// 哈希函数 2
// 返回随机数作为哈希值
func H2(x any) int {
	rand.Seed(time.Now().UnixNano())
	return rand.Intn(TSize)
}

// 扩容操作，这里省略具体实现
func ReHash() {
	// do something
}

// 随机踢出一个元素
// 返回踢出的哈希桶编号以及元素索引
func KicksOut(x any) any {
	// 哈希桶已满
	if len(T1) == TSize && len(T2) == TSize {
		return nil
	}

	rand.Seed(time.Now().UnixNano())
	n := rand.Intn(2)

	var y any // 被踢出的元素 y

	// 直接利用 Go map 的无序遍历特性
	// 遍历时将 [第一个元素] 作为随机元素踢出
	if n == 0 {
		// 从 T1 桶随机选择一个元素踢出
		for k, v := range T1 {
			// 将 x 插入到 y 的桶 (覆盖式)
			T1[k] = x
			y = v
			break
		}
	} else {
		// 从 T2 桶随机选择一个元素踢出
		for k, v := range T2 {
			// 将 x 插入到 y 的桶 (覆盖式)
			T2[k] = x
			y = v
			break
		}
	}

	return y
}

// 插入元素
func Insert(x any) bool {
	idx1, idx2 := H1(x), H2(x)

	// 如果 T1 桶对应桶为空，则插入 T1
	if _, ok := T1[idx1]; !ok {
		T1[idx1] = x
		return true
	}
	// 如果 T2 桶对应桶为空，则插入 T2
	if _, ok := T2[idx2]; !ok {
		T2[idx2] = x
		return true
	}

	y := KicksOut(x)
	// 哈希桶已满，进行扩容
	if y == nil {
		ReHash()
	}

	// 插入元素 y
	return Insert(y)
}

package main

func main() {
	println(1 ^ 2) // 3
	println(3 ^ 1) // 2
	println(3 ^ 2) // 1
}

package main

import "fmt"

// 计算重复组合数量
func multiCombination(n, r int) int {
	if n == 0 || r == 0 {
		return 0
	}
	numerator := 1
	denominator := 1
	for i := 1; i <= r; i++ {
		numerator *= n + i - 1
		denominator *= i
	}
	return numerator / denominator
}

func main() {
	fmt.Printf("n = %d, r = %d, combinations = %d\n", 16, 4, multiCombination(16, 4))
}

$ go run main.go

# 输出如下
n = 16, r = 4, combinations = 3876

package main

import (
	"fmt"
	"github.com/linvon/cuckoo-filter"
)

func main() {
	// 初始化一个布谷鸟过滤器
	// 使用半排序桶
	// 	  每个桶包含 4 个指纹, 每个指纹 4 bits
	// 最大存放元素数量 4096
	cf := cuckoo.NewFilter(4, 4, 1<<12, cuckoo.TableTypePacked)

	// 添加一些元素
	cf.Add([]byte(`Hello World`))
	cf.Add([]byte(`Hello Golang`))

	// 检测元素是否存在
	fmt.Printf("%v\n", cf.Contain([]byte(`Hello World`)))
	fmt.Printf("%v\n", cf.Contain([]byte(`Hello Golang`)))
	fmt.Printf("%v\n", cf.Contain([]byte(`Hello Rust`)))

	// 输出元素数量
	fmt.Printf("filter size = %d\n", cf.Size())

	// 删除元素
	cf.Delete([]byte(`Hello World`))

	// 输出过滤器信息
	fmt.Println("\n", cf.Info())
}

$ go run main.go

# 输出如下

true
true
false
filter size = 2

CuckooFilter Status:
              PackedHashtable with tag size: 4 bits
              4 packed bits(3 bits after compression) and 0 direct bits
              Associativity: 4
              Total # of rows: 2048
              Total # slots: 8192

              Keys stored: 1
              Load factor: 0.0001220703125
              Hashtable size: 3 KB
              bit/key:   24632

const (
	// 普通表
	TableTypeSingle = 0
	
	// 压缩表
	TableTypePacked = 1
)
  
type table interface {
  ...
}
  
func getTable(tableType uint) interface{} {
	switch tableType {
	case TableTypePacked:
		return NewPackedTable()
	default:
		return NewSingleTable()
	}
} 

type victimCache struct {
	index uint
	tag   uint32
	used  bool
}

type Filter struct {
	victim   victimCache
	numItems uint
	table    table
}

func NewFilter(tagsPerBucket, bitsPerItem, maxNumKeys, tableType uint) *Filter {
	// 根据表内存放元素和每个桶的元素指纹数量，计算需要的桶的数量
	numBuckets := getNextPow2(uint64(maxNumKeys / tagsPerBucket))
	
	// 如果表的负载因子过高，就将桶的数量扩容 (翻 1 倍)
	// 负载因子如何计算出来的呢？
	//    框架这里进行了 3 个硬编码的值:
	//        默认:      0.99
	//        桶大小为 2: 0.85
	//        桶大小为 4: 0.96
	if float64(maxNumKeys)/float64(numBuckets*tagsPerBucket) > maxLoadFactor(tagsPerBucket) {
		numBuckets <<= 1
	}
	
	// 桶最少得有 1 个
	if numBuckets == 0 {
		numBuckets = 1
	}
	
	// 工厂方法根据参数类型生成过滤器
	table := getTable(tableType).(table)
	
	// 表初始化
	_ = table.Init(tagsPerBucket, bitsPerItem, numBuckets, nil)
	return &Filter{
		table: table,
	}
}

func (f *Filter) Add(item []byte) bool {
	// 如果被踢出的元素没有找到可用的桶
	// 那么继续添加元素只会进入恶行循环，降低性能
	// 此时直接返回即可
	if f.victim.used {
		return false
	}
	
	// 计算哈希值和桶索引，然后将元素添加到表中对应的桶
	i, tag := f.generateIndexTagHash(item)
	return f.addImpl(i, tag)
}

func (f *Filter) Contain(key []byte) bool {
	// 计算元素的哈希值和桶索引
	i1, tag := f.generateIndexTagHash(key)
	// 计算候选桶索引
	i2 := f.altIndex(i1, tag)
	
	hit := f.victim.used && tag == f.victim.tag && (i1 == f.victim.index || i2 == f.victim.index)

	// 满足以下两个条件之一，说明参数元素存在于表中:
	//    1. 参数元素和表内被踢出元素的哈希值以及桶位置相同
	//    2. 在表的某个桶内找到了相同的参数元素哈希
	if hit || f.table.FindTagInBuckets(i1, i2, tag) {
		return true
	}
	return false
}

func (f *Filter) Size() uint {
	var c uint
	if f.victim.used {
		c = 1
	}
	return f.numItems + c
}

func (f *Filter) LoadFactor() float64 {
	return 1.0 * float64(f.Size()) / float64(f.table.SizeInTags())
}

func (f *Filter) Reset() {
    // 底层表内元素初始化为 0
    f.table.Reset()
    
    // 元素计数归 0  
    f.numItems = 0
	
	// 重置被踢出元素
    f.victim.index = 0
    f.victim.tag = 0
    f.victim.used = false
}

func (f *Filter) FalsePositiveRate() float64 {
	n1 := make([]byte, 4)
	
	f.Reset() // 重置过滤器
	
	// 获取底层表可存储元素数量
	n := f.table.SizeInTags()
	// 循环向表内添加元素，元素为 [0 ... n]
	for i := uint32(0); i < uint32(n); i++ {
		binary.BigEndian.PutUint32(n1, i)
		f.Add(n1)
	}
	
	// 计算误判率采用的检测次数 (这里硬编码为 10 W)
	var rounds uint32 = 100000
	// 误判计数
	fp := 0
	for i := uint32(0); i < rounds; i++ {
		// 给定一个不可能存在表中的元素
		binary.BigEndian.PutUint32(n1, i+uint32(n)+1)
        // 正常情况下，Contain 方法返回的都是 false
		if f.Contain(n1) {
			// 如果 Contain 方法返回 true, 则属于误判
			// 误判计数 + 1 
			fp++
		}
	}
	f.Reset()  // 重置过滤器
	
	// 误判计数 / 检测次数 = 误判率
	return float64(fp) / float64(rounds)
}

module github.com/linvon/cuckoo-filter

go 1.14

require github.com/dgryski/go-metro v0.0.0-20200812162917-85c65e2d0165

func (f *Filter) altIndex(index uint, tag uint32) uint {
	// 0x5bd1e995 是 MurmurHash2 算法的哈希常量
	return f.indexHash(uint32(index) ^ (tag * 0x5bd1e995))
}