Documentation
¶
Index ¶
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 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
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) GetBucket ¶
GetBucket returns the index in a given bucket which represents the value in the list of identifiers to which it points.
func (*Cuckoo) GetItemWithHash ¶
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 ¶
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) LoadFactor ¶
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.