cuckoo

README

Cuckoo hash tables

Description

Cuckoo hash tables [1] is an optimized hash table data structure with O(1) look up times in worst case scenario, and O(1) insertion time with amortized costs. We implement a variant of cuckoo hash tables that uses 3 hash functions to limit the probability of hashing faillure to 2^σ, where σ is a security parameter that is set to 40.

Benchmark

go test -bench=. -benchmem ./internal/cuckoo/...                                
goos: darwin
goarch: amd64
pkg: github.com/optable/match/internal/cuckoo
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkCuckooInsert-12         2627492               498.0 ns/op             0 B/op          0 allocs/op
BenchmarkCuckooExists-12         7582648               203.0 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/optable/match/internal/cuckoo        7.896s

References

[1] Pagh, R., and Rodler, F. F. Cuckoo hashing. J. Algorithms 51, 2 (2004), 122–144.

Documentation

Index

• Constants
• type Cuckoo
  • func NewCuckoo(size uint64, seeds [Nhash][]byte) *Cuckoo
  • func (c *Cuckoo) Exists(item []byte) (bool, byte)
  • func (c *Cuckoo) GetBucket(bIdx uint64) uint64
  • func (c *Cuckoo) GetItemWithHash(idx uint64) (item []byte, hIdx uint8)
  • func (c *Cuckoo) Insert(item []byte) error
  • func (c *Cuckoo) Len() uint64
  • func (c *Cuckoo) LoadFactor() (factor float64)
• type CuckooHasher
  • func NewCuckooHasher(size uint64, seeds [Nhash][]byte) *CuckooHasher
  • func (h *CuckooHasher) BucketIndices(item []byte) (idxs [Nhash]uint64)
  • func (h *CuckooHasher) GetHasher() hash.Hasher

Constants

const (
	// Nhash is the number of hash function used for cuckoo hash
	Nhash = 3
	// ReInsertLimit is the maximum number of reinsertions.
	// Each reinsertion kicks off 1 egg (item) and replace it
	// with the item being reinserted, and then reinserts the
	// kicked off egg
	ReInsertLimit = 200
	// Factor is the multiplicative factor of items to be
	// inserted which represents the capacity overhead of
	// the hash table to reduce risk of failure on insertion.
	Factor = 1.4
)

Types

type Cuckoo

type Cuckoo struct {
	*CuckooHasher
	// contains filtered or unexported fields
}

Cuckoo represents a 3-way Cuckoo hash table data structure that contains the items, bucket indices of each item and the 3 hash functions. The bucket lookup is a lookup table on items which tells us which item should be in the bucket at that index. Upon construction the items slice has an additional nil value prepended so the index of the Cuckoo.items slice is +1 compared to the index of the input slice you use. The number of inserted items is also tracked.

func NewCuckoo

func NewCuckoo(size uint64, seeds [Nhash][]byte) *Cuckoo

NewCuckoo instantiates a Cuckoo struct with a bucket of size Factor * size, seeds math/rand with a random seed, returns a CuckooHasher for the 3-way cuckoo hashing.

func (*Cuckoo) Exists

func (c *Cuckoo) Exists(item []byte) (bool, byte)

Exists returns true if an item is inserted in cuckoo, false otherwise

func (*Cuckoo) GetBucket

func (c *Cuckoo) GetBucket(bIdx uint64) uint64

GetBucket returns the index in a given bucket which represents the value in the list of identifiers to which it points.

func (*Cuckoo) GetItemWithHash

func (c *Cuckoo) GetItemWithHash(idx uint64) (item []byte, hIdx uint8)

GetItemWithHash returns the item at a given index along with its hash index. Panic if the index is greater than the number of items.

func (*Cuckoo) Insert

func (c *Cuckoo) Insert(item []byte) error

Insert tries to insert a given item at the next index to the bucket in available slots, otherwise, it evicts a random occupied slot, and reinserts evicted item. Returns an error msg if all failed.

func (*Cuckoo) Len

func (c *Cuckoo) Len() uint64

Len returns the total size of the cuckoo struct which is equal to bucketSize

func (*Cuckoo) LoadFactor

func (c *Cuckoo) LoadFactor() (factor float64)

LoadFactor returns the ratio of occupied buckets with the overall bucketSize

type CuckooHasher

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

CuckooHasher is the building block of a Cuckoo hash table. It only holds the bucket size and the hashers.

func NewCuckooHasher

func NewCuckooHasher(size uint64, seeds [Nhash][]byte) *CuckooHasher

NewCuckooHasher instantiates a CuckooHasher struct.

func (*CuckooHasher) BucketIndices

func (h *CuckooHasher) BucketIndices(item []byte) (idxs [Nhash]uint64)

BucketIndices returns the 3 possible bucket indices of an item

func (*CuckooHasher) GetHasher

func (h *CuckooHasher) GetHasher() hash.Hasher

GetHasher returns the first seeded hash function from a CuckooHasher struct.