genmap

README

genmap

Go native map only accept comparable types as key. This prominently prevents the use of slices and maps as keys.

genmap provides a generic map implementation that does not have such limitation.

Features

• Get, Put, Delete, Upsert
• Len, Clear
• Iterator allowing Delete while iterating

It's up to the user to provide a hash and an equality function for the key type (Helpers are provided for the common cases).

Limitations

The rather simple implementation is designed for the case where the number of keys is roughly known in advance. Performance will suffer if the number of keys is much larger than the number of buckets.

Example usage

m := genmap.NewMap[MyKey, MyValue](MyKeyEquals, NewMyKeyHasher())

m.Put(MyKey{1, []string{"a", "b"}}, MyValue{1, "a"})
m.Put(MyKey{2, []string{"c", "d"}}, MyValue{2, "b"})
m.Put(MyKey{1, []string{"a", "b"}}, MyValue{3, "c"})

// increment the value for a key
m.Upsert(MyKey{1, []string{"a", "b"}}, func(elem *genmap.MapElement[MyKey, MyValue], exists bool) {
	elem.Value.v1++
})

// Get the value for a key
v := m.Get(MyKey{1, []string{"a", "b"}})
if v != nil {
	println(v.v1)
	// prints 4
}

// Iterate over the map
it := m.Iterator()
for it.Next() {
	fmt.Printf("Key: %v, Value: %v\n", it.Cur().Key, it.Cur().Value)
}
// prints:
// Key: {1 [a b]}, Value: {4 c}
// Key: {2 [c d]}, Value: {2 b}

Benchmarks

Benchmarked against the standard map implementation. Use of a 64k bucket size for 100k keys.

BenchmarkMapGet-10                   	26824383	        45.86 ns/op	       0 B/op	       0 allocs/op
BenchmarkStdMapGet-10                	28797897	        40.86 ns/op	       0 B/op	       0 allocs/op
BenchmarkMapPut100k-10               	     294	   4057501 ns/op	 7716181 B/op	    1440 allocs/op
BenchmarkStdMapPut100k-10            	     390	   3043593 ns/op	 5208164 B/op	    1645 allocs/op
BenchmarkMapPutOverwrite-10          	22302621	        51.56 ns/op	       0 B/op	       0 allocs/op
BenchmarkStdMapPutOverwrite-10       	29951390	        40.65 ns/op	       0 B/op	       0 allocs/op
BenchmarkMapUpsert100k-10            	     313	   3790824 ns/op	 7715365 B/op	    1445 allocs/op
BenchmarkStdMapUpsert100k-10         	     360	   3426847 ns/op	 5207400 B/op	    1642 allocs/op
BenchmarkMapUpsertIncrement-10       	24000559	        51.03 ns/op	       0 B/op	       0 allocs/op
BenchmarkStdMapUpsertIncrement-10    	20924194	        57.68 ns/op	       0 B/op	       0 allocs/op
BenchmarkMapUpsertDelete-10          	25785609	        44.60 ns/op	       0 B/op	       0 allocs/op
BenchmarkStdMapUpsertDelete-10       	20577380	        57.61 ns/op	       0 B/op	       0 allocs/op
BenchmarkMapIterator-10              	    1669	    712207 ns/op	       0 B/op	       0 allocs/op
BenchmarkStdMapIterator-10           	    1566	    766186 ns/op	       0 B/op	       0 allocs/op

Credits

• dolthub maphash generic hash function for comparables

Documentation

Index

• Constants
• func CombineHash(seed, hash uint64) uint64
• func CombineHashes(hashes ...uint64) uint64
• func DeepEqual[T any](a, b T) bool
• func Equal[K comparable](k1, k2 K) bool
• func NewHasher[T comparable]() func(T) uint64
• type Map
  • func NewMap[K any, V any](equal func(k1, k2 K) bool, hash func(k K) uint64, bucketSizeOpt ...int) *Map[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Get(key K) (V, bool)
  • func (m *Map[K, V]) Iterator() *MapIterator[K, V]
  • func (m *Map[K, V]) Len() int
  • func (m *Map[K, V]) Put(key K, val V)
  • func (m *Map[K, V]) Remove(key K) (MapElement[K, V], bool)
  • func (m *Map[K, V]) Upsert(key K, update func(elem *MapElement[K, V], exists bool))
• type MapElement
• type MapIterator
  • func (it *MapIterator[K, V]) Cur() *MapElement[K, V]
  • func (it *MapIterator[K, V]) Next() bool
  • func (it *MapIterator[K, V]) Remove() MapElement[K, V]
  • func (it *MapIterator[K, V]) Reset()

Constants

const (
	HashSeed uint64 = 14695981039346656037 // Seed value for the initial hash
)

Functions

func CombineHash

func CombineHash(seed, hash uint64) uint64

CombineHash Combine two uint64 hashes into a single hash

func CombineHashes

func CombineHashes(hashes ...uint64) uint64

CombineHashes Combine a list of uint64 hashes into a single hash

func DeepEqual

func DeepEqual[T any](a, b T) bool

DeepEqual Deep equal comparison of two values

func Equal

func Equal[K comparable](k1, k2 K) bool

Equal Compares two `comparable` values

func NewHasher

func NewHasher[T comparable]() func(T) uint64

Hasher Returns a hash function for `comparable`

Types

type Map

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

Map is a generic hash map implementation that allows any type for keys. Map instance should be instantiated using the NewMap function.

func NewMap

func NewMap[K any, V any](equal func(k1, k2 K) bool, hash func(k K) uint64, bucketSizeOpt ...int) *Map[K, V]

NewMap returns a new instance of Map[K, V] with the given equality and hash functions. The optional bucketSizeOpt parameter specifies the size of each bucket in the map. If not provided, a default bucket size (64k) is used. Special care should be taken when choosing a bucket size as it can have a significant impact on performance. For good performance, the bucket size should be close to the expected number of elements in the map.

func (*Map[K, V]) Clear

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

Clear removes all elements from the map.

func (*Map[K, V]) Get

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

returns the value associated with the given key.

func (*Map[K, V]) Iterator

func (m *Map[K, V]) Iterator() *MapIterator[K, V]

Iterator returns a new iterator over the map.

func (*Map[K, V]) Len

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

returns the number of elements in the map.

func (*Map[K, V]) Put

func (m *Map[K, V]) Put(key K, val V)

Put inserts the given key-value pair into the map.

func (*Map[K, V]) Remove

func (m *Map[K, V]) Remove(key K) (MapElement[K, V], bool)

Remove removes the given key from the map and returns it.

func (*Map[K, V]) Upsert

func (m *Map[K, V]) Upsert(key K, update func(elem *MapElement[K, V], exists bool))

Upsert inserts or modifies the given entry into the map. The update function is called with the current value or the new one.

type MapElement

type MapElement[K any, V any] struct {
	Key   K
	Value V
	// contains filtered or unexported fields
}

MapElement is a generic key-value pair used in the Map[K, V] implementation.

type MapIterator

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

MapIterator is an iterator over a map.

func (*MapIterator[K, V]) Cur

func (it *MapIterator[K, V]) Cur() *MapElement[K, V]

Cur returns the current element

func (*MapIterator[K, V]) Next

func (it *MapIterator[K, V]) Next() bool

Next advances the iterator and returns true if there is another element

func (*MapIterator[K, V]) Remove

func (it *MapIterator[K, V]) Remove() MapElement[K, V]

Remove removes the current element from the map and returns it. After calling Remove, Next must be called before calling Cur again.

func (*MapIterator[K, V]) Reset

func (it *MapIterator[K, V]) Reset()

Reset resets the iterator to the beginning of the map.