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
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-inmap
has special cases for handling this, butMap
does not. -
If a key in a
Map
contains 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.
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.
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.