README
¶
Fast hashmap with integer keys for Golang
intmap
import "github.com/kamstrup/intmap"
Package intmap is a fast hashmap implementation for Golang, specialized for maps with integer type keys. The values can be of any type.
It is a full port of https://github.com/brentp/intintmap to use type parameters (aka generics).
It interleaves keys and values in the same underlying array to improve locality. This is also known as open addressing with linear probing.
It is up to 3X faster than the builtin map:
name time/op
Map64Fill-8 201ms ± 5%
IntIntMapFill-8 207ms ±31%
StdMapFill-8 371ms ±11%
Map64Get10PercentHitRate-8 148µs ±40%
IntIntMapGet10PercentHitRate-8 171µs ±50%
StdMapGet10PercentHitRate-8 171µs ±33%
Map64Get100PercentHitRate-8 4.50ms ± 5%
IntIntMapGet100PercentHitRate-8 4.82ms ± 6%
StdMapGet100PercentHitRate-8 15.5ms ±32%
Usage
m := intmap.New[int64,int64](32768)
m.Put(int64(1234), int64(-222))
m.Put(int64(123), int64(33))
v, ok := m.Get(int64(222))
v, ok := m.Get(int64(333))
m.Del(int64(222))
m.Del(int64(333))
fmt.Println(m.Len())
m.ForEach(func(k int64, v int64) {
fmt.Printf("key: %d, value: %d\n", k, v)
})
m.Clear() // all gone, but buffers kept
Documentation
¶
Overview ¶
Package intmap contains a fast hashmap implementation for maps with keys of any integer type
Index ¶
- type IntKey
- type Map
- func (m *Map[K, V]) All() iter.Seq2[K, V]
- func (m *Map[K, V]) Clear()
- func (m *Map[K, V]) Del(key K) bool
- func (m *Map[K, V]) ForEach(f func(K, V) bool)
- func (m *Map[K, V]) Get(key K) (V, bool)
- func (m *Map[K, V]) Has(key K) bool
- func (m *Map[K, V]) Keys() iter.Seq[K]
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Put(key K, val V)
- func (m *Map[K, V]) PutIfNotExists(key K, val V) (V, bool)
- func (m *Map[K, V]) Values() iter.Seq[V]
- type Set
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IntKey ¶
type IntKey interface {
~int | ~uint | ~int64 | ~uint64 | ~int32 | ~uint32 | ~int16 | ~uint16 | ~int8 | ~uint8 | ~uintptr
}
IntKey is a type constraint for values that can be used as keys in Map
type Map ¶
Map is a hashmap where the keys are some any integer type. It is valid to call methods that read a nil map, similar to a standard Go map. Methods valid on a nil map are Has, Get, Len, and ForEach.
func New ¶
New creates a new map with keys being any integer subtype. The map can store up to the given capacity before reallocation and rehashing occurs.
func (*Map[K, V]) All ¶ added in v0.5.0
All returns an iterator over key-value pairs from m. The iterator returns immediately if invoked on a nil map.
The iteration order of a Map is not defined, so please avoid relying on it.
func (*Map[K, V]) Clear ¶
func (m *Map[K, V]) Clear()
Clear removes all items from the map, but keeps the internal buffers for reuse.
func (*Map[K, V]) ForEach ¶
ForEach iterates through key-value pairs in the map while the function f returns true. This method returns immediately if invoked on a nil map.
The iteration order of a Map is not defined, so please avoid relying on it.
func (*Map[K, V]) Get ¶
Get returns the value if the key is found. If you just need to check for existence it is easier to use Has. Calling this method on a nil map will return the zero value for V and false.
func (*Map[K, V]) Has ¶ added in v0.1.2
Has checks if the given key exists in the map. Calling this method on a nil map will return false.
func (*Map[K, V]) Keys ¶ added in v0.5.0
Keys returns an iterator over keys in m. The iterator returns immediately if invoked on a nil map.
The iteration order of a Map is not defined, so please avoid relying on it.
func (*Map[K, V]) Len ¶
Len returns the number of elements in the map. The length of a nil map is defined to be zero.
func (*Map[K, V]) Put ¶
func (m *Map[K, V]) Put(key K, val V)
Put adds or updates key with value val.
func (*Map[K, V]) PutIfNotExists ¶ added in v0.1.2
PutIfNotExists adds the key-value pair only if the key does not already exist in the map, and returns the current value associated with the key and a boolean indicating whether the value was newly added or not.
type Set ¶ added in v0.3.0
Set is a specialization of Map modelling a set of integers. Like Map, methods that read from the set are valid on the nil Set. This include Has, Len, and ForEach.
func (*Set[K]) Add ¶ added in v0.3.0
Add an element to the set. Returns true if the element was not already present.
func (*Set[K]) All ¶ added in v0.5.0
All returns an iterator over keys from the set. The iterator returns immediately if the set is nil.
The iteration order of a Set is not defined, so please avoid relying on it.
func (*Set[K]) Clear ¶ added in v0.4.0
func (s *Set[K]) Clear()
Clear removes all items from the Set, but keeps the internal buffers for reuse.
func (*Set[K]) ForEach ¶ added in v0.3.0
ForEach iterates over the elements in the set while the visit function returns true. This method returns immediately if the set is nil.
The iteration order of a Set is not defined, so please avoid relying on it.
Source Files