M.V. Hutz
717408239b
Moved the implementation of this hash table from `tools/dsa` #1. Reviewed-on: #1 Co-authored-by: M.V. Hutz <git@maximhutz.me> Co-committed-by: M.V. Hutz <git@maximhutz.me>
28 lines
827 B
Go
28 lines
827 B
Go
package cuckoo
|
|
|
|
import (
|
|
"hash/maphash"
|
|
)
|
|
|
|
// A Hash function maps any data to a fixed-length value (in this case, a
|
|
// [uint64]).
|
|
//
|
|
// It is used by the [Table] to evenly distribute values
|
|
// amongst its slots. A good hash function is uniform, [chaotic], and
|
|
// deterministic. [Table] uses [NewDefaultHash] by default, which is built on
|
|
// [maphash.Comparable].
|
|
//
|
|
// [chaotic]: https://en.wikipedia.org/wiki/Avalanche_effect
|
|
type Hash[K any] = func(key K) (digest uint64)
|
|
|
|
// NewDefaultHash returns a new [Hash] which uses [maphash.Comparable].
|
|
//
|
|
// Each hash has a random seed, so calling this function again will return a new
|
|
// hash. Do not use this for testing.
|
|
func NewDefaultHash[K comparable]() Hash[K] {
|
|
seed := maphash.MakeSeed()
|
|
return func(key K) (digest uint64) {
|
|
return maphash.Comparable(seed, key)
|
|
}
|
|
}
|