cuckoo

README

cuckoo

Cuckoo hash in go.

This is an implementation of a generic cuckoo hash table in pure Go. It uses dohash for hashing any type with the underlying hash being hash/maphash. It supports several tables and multiple buckets per position in each table. There is no support for concurrency. If more than one goroutine wants to access the table to modify while another is accessing it, they will have to synchronize using external mechanisms. Read only access is safe.

A local copy of the godoc is here.

Documentation

Overview

Implementation of a cuckoo hash table using gitlab.eif.urjc.es/paurea/dohash, with the hasher wired to hash/maphash. There is no support for concurrency. Read only access is safe.

Index

• Constants
• type Cuckoo
  • func NewCuckoo[K comparable, V any]() (cuckoo *Cuckoo[K, V])
  • func NewCuckooWithLoad[K comparable, V any](maxpercload int) (cuckoo *Cuckoo[K, V])
  • func (cuckoo *Cuckoo[K, V]) Delete(key K) (waspresent bool)
  • func (cuckoo *Cuckoo[K, V]) Iter() iter.Seq2[K, V]
  • func (cuckoo *Cuckoo[K, V]) IterCopy() iter.Seq2[K, V]
  • func (cuckoo *Cuckoo[K, V]) Len() int
  • func (cuckoo *Cuckoo[K, V]) Lookup(key K) (val V, isok bool)
  • func (cuckoo *Cuckoo[K, V]) PercFull() int
  • func (cuckoo *Cuckoo[K, V]) Set(key K, val V) (waspresent bool, err error)

Constants

const (
	DefaultSz       = 1 << 5   // of each tab, has to be 2's exponent
	DefaultNTabs    = 2        // see percLoadResize, can be 2 or 3
	DefaultNBuckets = (1 << 1) // has to be 2's exponent see percLoadResize

)

const (
	TotMinPercLoad = 50 // Theoretical limit of a cuckoo without buckets is 50.
	TotMaxPercLoad = 97 // Theoretical max is around 97.
)

Types

type Cuckoo

type Cuckoo[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewCuckoo

func NewCuckoo[K comparable, V any]() (cuckoo *Cuckoo[K, V])

Creates a cuckoo hash.

func NewCuckooWithLoad

func NewCuckooWithLoad[K comparable, V any](maxpercload int) (cuckoo *Cuckoo[K, V])

Creates a cuckoo hash which will have as maximum load (as a percentage) maxpercload. Bigger maximum load means slower operations but less memory usage and a smaller maximum capacity.

func (*Cuckoo[K, V]) Delete

func (cuckoo *Cuckoo[K, V]) Delete(key K) (waspresent bool)

Deletes the element associated to a key. Returns if the key was present.

func (*Cuckoo[K, V]) Iter

func (cuckoo *Cuckoo[K, V]) Iter() iter.Seq2[K, V]

Iterator for the cuckoo hash. Not safe to use the closure while operating on the table, will panic. Creating the iterator is not dangerous: iterating is. See Cuckoo.IterCopy for a safe version.

func (*Cuckoo[K, V]) IterCopy

func (cuckoo *Cuckoo[K, V]) IterCopy() iter.Seq2[K, V]

Iterator for the cuckoo hash. Safe to use while operating on the table, makes a copy and iterates on that. A copy of the table backend storage will exist while the closure returned exists.

func (*Cuckoo[K, V]) Len

func (cuckoo *Cuckoo[K, V]) Len() int

func (*Cuckoo[K, V]) Lookup

func (cuckoo *Cuckoo[K, V]) Lookup(key K) (val V, isok bool)

Lookups the value associated to a key. It has O(1) guaranteed worst case.

func (*Cuckoo[K, V]) PercFull

func (cuckoo *Cuckoo[K, V]) PercFull() int

Percentage of the hash full (load).

func (*Cuckoo[K, V]) Set

func (cuckoo *Cuckoo[K, V]) Set(key K, val V) (waspresent bool, err error)

Sets the value associated to the key. Returns if the key was already present. An error may occur is the cuckoo hash cannot grow any more.