README
¶
gomap
This package reimplements Go's built-in map as a library using
generics. The major difference between gomap.Map and map is that
users of gomap.Map must provide their own equal and hash
functions.
The use case for gomap.Map is when you want to use map, but can't
because your key type is not
comparable.
gomap.Map has similar performance and most of the features of the
built-in map including:
-
iteration that is not invalidated by modifications to the map
-
randomized hash seeds and randomized iteration order
-
incremental rehash
-
cheap best effort detection of unsafe concurrent accesses
Requirements
There is a reason that Go's built-in map uses compiler generated equal and hash functions that users don't have control over: there are subtle requirements of a hash table that when invalidated cause hard to diagnose bugs.
The following requirements are the user's responsibility to follow:
-
equal(a, b)=>hash(a) == hash(b) -
equal(a, a)must be true for all values ofa. Be careful around NaN float values. Go's built-inmaphas special cases for handling this, butMapdoes not. -
If a key in a
Mapcontains references -- such as pointers, maps, or slices -- modifying the referenced data in a way that effects the result of the equal or hash functions will result in undefined behavior. -
For good performance hash functions should return uniformly distributed data across the entire 64-bits of the value.
Stability
The APIs of Map are subject to change at this early stage. In
particular, Iter is likely to change depending on the outcome of
this discussion for a standard iterator
interface.
Implementation
The implementation of Map is largely copy-pasted from Go's map
implementation.
It implements a chaining hash table with buckets that contain 8
entries.
Documentation
¶
Overview ¶
Pacakge gomap provides the Map type, which implements a hash table. It's implementation is heavily inspired by Go's built-in map, with the additional requirement that users provide a equal and hash function.
The following requirements are the user's responsibility to follow:
- equal(a, b) => hash(a) == hash(b)
- equal(a, a) must be true for all values of a. Be careful around NaN float values. Go's built-in `map` has special cases for handling this, but `Map` does not.
- If a key in a `Map` contains references -- such as pointers, maps, or slices -- modifying the referefenced data in a way that effects the result of the equal or hash functions will result in undefined behavior.
- For good performance hash functions should return uniformly distributed data across the entire 64-bits of the value.
Index ¶
- func Equal[K any, E comparable](m1, m2 *Map[K, E]) bool
- func EqualFunc[K, E any](m1, m2 *Map[K, E], eq func(E, E) bool) bool
- func String[K fmt.Stringer, E fmt.Stringer](m *Map[K, E]) string
- func StringFunc[K any, E any](m *Map[K, E], strK func(key K) string, strE func(elem E) string) string
- type Iterator
- type KeyElem
- type Map
- func (m *Map[K, E]) All() iter.Seq2[K, E]
- func (m *Map[K, E]) Clear()
- func (m *Map[K, E]) Delete(key K)
- func (m *Map[K, E]) Get(key K) (E, bool)
- func (m *Map[K, E]) Iter() *Iterator[K, E]
- func (m *Map[K, E]) Keys() iter.Seq[K]
- func (m *Map[K, E]) Len() int
- func (m *Map[K, E]) Set(key K, elem E)
- func (m *Map[K, E]) String() string
- func (m *Map[K, E]) Update(key K, fn func(elem E) E)
- func (m *Map[K, E]) Values() iter.Seq[E]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Equal ¶
func Equal[K any, E comparable](m1, m2 *Map[K, E]) bool
Equal returns true if the same set of keys and elems are in m1 and m2. Elements are compared using ==.
func EqualFunc ¶
Equal returns true if the same set of keys and elems are in m1 and m2. Elements are compared using eq.
Types ¶
type Iterator ¶
type Iterator[K, E any] struct { // contains filtered or unexported fields }
Iterator is instantiated by a call Iter(). It allows iterating over a Map.
func (*Iterator[K, E]) Elem ¶
func (it *Iterator[K, E]) Elem() E
Elem returns the element at the iterator's current position. This is only valid after a call to Next() that returns true.
type Map ¶
type Map[K, E any] struct { // contains filtered or unexported fields }
Map implements a hashmap
func New ¶
func New[K, E any]( equal func(a, b K) bool, hash func(maphash.Seed, K) uint64, kes ...KeyElem[K, E]) *Map[K, E]
New instantiates a new Map initialized with any KeyElems passed. The equal func must return true for two values of K that are equal and false otherwise. The hash func should return a uniformly distributed hash value. If equal(a, b) then hash(a) == hash(b). The hash function is passed a hash/maphash.Seed, this is meant to be used with functions and types in the hash/maphash package, though can be ignored.
Example ¶
package main
import (
"bytes"
"hash/maphash"
"github.com/aristanetworks/gomap"
)
func main() {
// Some examples of different maps:
// Map that uses []byte as the key type
byteSliceMap := gomap.New[[]byte, int](bytes.Equal, maphash.Bytes)
byteSliceMap.Set([]byte("hello"), 42)
// Map that uses map[string]struct{} as the key type
stringSetEqual := func(a, b map[string]struct{}) bool {
if len(a) != len(b) {
return false
}
for k := range a {
_, ok := b[k]
if !ok {
return false
}
}
return true
}
stringSetHash := func(seed maphash.Seed, ss map[string]struct{}) uint64 {
var sum uint64
for s := range ss {
// combine hashes with addition so that iteration order does not matter
sum += maphash.String(seed, s)
}
return sum
}
stringSetMap := gomap.New[map[string]struct{}, int](stringSetEqual, stringSetHash)
stringSetMap.Set(map[string]struct{}{"foo": {}, "bar": {}}, 42)
}
func NewHint ¶
func NewHint[K, E any]( hint int, equal func(a, b K) bool, hash func(maphash.Seed, K) uint64) *Map[K, E]
NewHint instantiates a new Map with a hint as to how many elements will be inserted. See New for discussion of the equal and hash arguments.
func (*Map[K, E]) Delete ¶
func (m *Map[K, E]) Delete(key K)
Delete removes key and it's associated value from the map.
func (*Map[K, E]) Get ¶
Get returns the element associated with key and true if that key is in the Map, otherwise it returns the zero value of E and false.
func (*Map[K, E]) Iter ¶
Iter instantiates an Iterator to explore the elements of the Map. Ordering is undefined and is intentionally randomized.
Prefer Map.All over Iter when using go1.23 or later as it works with for-range loops and has less overhead.
Example ¶
package main
import (
"fmt"
"hash/maphash"
"github.com/aristanetworks/gomap"
)
func main() {
m := gomap.New(
func(a, b string) bool { return a == b },
maphash.String,
gomap.KeyElem[string, string]{"Avenue", "AVE"},
gomap.KeyElem[string, string]{"Street", "ST"},
gomap.KeyElem[string, string]{"Court", "CT"},
)
for i := m.Iter(); i.Next(); {
fmt.Printf("The abbreviation for %q is %q", i.Key(), i.Elem())
}
}
func (*Map[K, E]) String ¶
String converts m to a string. Keys and Elements are stringified using fmt.Sprint. Use String for better control over stringifying m's contents.
Source Files