gomap

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:

1. equal(a, b) => hash(a) == hash(b)

2. 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.

3. 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.

4. 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
  • func (it *Iterator[K, E]) Elem() E
  • func (it *Iterator[K, E]) Key() K
  • func (it *Iterator[K, E]) Next() bool
• type KeyElem
• type Map
  • func New[K, E any](equal func(a, b K) bool, hash func(maphash.Seed, K) uint64, ...) *Map[K, E]
  • func NewHint[K, E any](hint int, equal func(a, b K) bool, hash func(maphash.Seed, K) uint64) *Map[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]) 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)

Examples

• Map.Iter
• New

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

func EqualFunc[K, E any](m1, m2 *Map[K, E], eq func(E, E) bool) bool

Equal returns true if the same set of keys and elems are in m1 and m2. Elements are compared using eq.

func String

func String[K fmt.Stringer, E fmt.Stringer](m *Map[K, E]) string

String converts m to a string representation using K's and E's String functions.

func StringFunc

func StringFunc[K any, E any](m *Map[K, E],
	strK func(key K) string,
	strE func(elem E) string) string

StringFunc converts m to a string representation with the help of strK and strE functions to stringify m's keys and elems.

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.

func (*Iterator[K, E]) Key

func (it *Iterator[K, E]) Key() K

Key returns the key at the iterator's current position. This is only valid after a call to Next() that returns true.

func (*Iterator[K, E]) Next

func (it *Iterator[K, E]) Next() bool

Next moves the iterator to the next element. Next returns false when the iterator is complete.

type KeyElem

type KeyElem[K, E any] struct {
	Key  K
	Elem E
}

KeyElem contains a Key and Elem.

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]) Clear

func (m *Map[K, E]) Clear()

Clear deletes all keys from m.

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

func (m *Map[K, E]) Get(key K) (E, bool)

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

func (m *Map[K, E]) Iter() *Iterator[K, E]

Iter instantiates an Iterator to explore the elements of the Map. Ordering is undefined and is intentionally randomized.

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]) Len

func (m *Map[K, E]) Len() int

Len returns the count of occupied elements in m.

func (*Map[K, E]) Set

func (m *Map[K, E]) Set(key K, elem E)

Set associates key with elem in m.

func (*Map[K, E]) String

func (m *Map[K, E]) String() 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.

func (*Map[K, E]) Update

func (m *Map[K, E]) Update(key K, fn func(elem E) E)

Update calls fn with the elem associated with key, or the zero value of E if key is not present, the value returned by fn will be set in the map.

Update is equivalent to:

elem, _ := m.Get(key)
m.Set(fn(elem))