README
¶
Golang Hash Maps
This package collects several hash maps. The first one is a robin hood hash map implementation.
Getting Started
go get -u github.com/EinfachAndy/hashmaps
Robin Hood Hash Map
The example code can be try out here.
package main
import (
"fmt"
"github.com/EinfachAndy/hashmaps"
)
func main() {
m := hashmaps.NewRobinHood[int, int]()
// insert some elements
m.Put(2, 2)
isNew := m.Put(1, 5)
if !isNew {
panic("broken")
}
// lookup a key
val, found := m.Get(1)
if !found || val != 5 {
panic("broken")
}
// iterate the map
m.Each(func(key int, val int) bool {
fmt.Println(key, "->", val)
return false
})
// Print some metrics
fmt.Println("Size:", m.Size(), "load:", m.Load())
// remove keys
wasIn := m.Remove(1)
if !wasIn {
panic("broken")
}
}
Benchmarks
The benchmarks are implemented and maintained here.
Contributing
If you would like to contribute a new feature or maps, please let me know first what you would like to add (via email or issue tracker).
Documentation
¶
Overview ¶
Package hashmaps implements several types of hash tables.
Example ¶
package main
import (
"fmt"
"github.com/EinfachAndy/hashmaps"
)
func main() {
m := hashmaps.NewRobinHood[string, int]()
m.Put("foo", 42)
m.Put("bar", 13)
fmt.Println(m.Get("foo"))
fmt.Println(m.Get("baz"))
m.Remove("foo")
fmt.Println(m.Get("foo"))
fmt.Println(m.Get("bar"))
m.Clear()
fmt.Println(m.Get("foo"))
fmt.Println(m.Get("bar"))
}
Output: 42 true 0 false 0 false 13 true 0 false 0 false
Index ¶
- Variables
- func Log2(value uint64) uint64
- func Max[T Ordered](a, b T) T
- func Min[T Ordered](a, b T) T
- func NextPowerOf2(i uint64) uint64
- type HashFn
- type IHashMap
- type Ordered
- type RobinHood
- func (m *RobinHood[K, V]) Clear()
- func (m *RobinHood[K, V]) Copy() *RobinHood[K, V]
- func (m *RobinHood[K, V]) Each(fn func(key K, val V) bool)
- func (m *RobinHood[K, V]) Get(key K) (V, bool)
- func (m *RobinHood[K, V]) Load() float32
- func (m *RobinHood[K, V]) MaxLoad(lf float32) error
- func (m *RobinHood[K, V]) Put(key K, val V) bool
- func (m *RobinHood[K, V]) Remove(key K) bool
- func (m *RobinHood[K, V]) Reserve(n uintptr)
- func (m *RobinHood[K, V]) Size() int
- type Unordered
- func (m *Unordered[K, V]) Clear()
- func (m *Unordered[K, V]) Each(fn func(key K, val V) bool)
- func (m *Unordered[K, V]) Get(key K) (V, bool)
- func (m *Unordered[K, V]) Insert(key K) (*V, bool)
- func (m *Unordered[K, V]) Load() float32
- func (m *Unordered[K, V]) Lookup(key K) *V
- func (m *Unordered[K, V]) Put(key K, val V) bool
- func (m *Unordered[K, V]) Remove(key K) bool
- func (m *Unordered[K, V]) Reserve(n uintptr)
- func (m *Unordered[K, V]) Size() int
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrOutOfRange signals an out of range request ErrOutOfRange = errors.New("out of range") )
Functions ¶
func Log2 ¶
Log2 is a fast computation of log2(x) https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
func NextPowerOf2 ¶
NextPowerOf2 is a fast computation of 2^x see: https://stackoverflow.com/questions/466204/rounding-up-to-next-power-of-2
Types ¶
type IHashMap ¶
type IHashMap[K comparable, V any] struct { Get func(key K) (V, bool) Reserve func(n uintptr) Load func() float32 Put func(key K, val V) bool Remove func(key K) bool Clear func() Size func() int Each func(fn func(key K, val V) bool) }
IHashMap collects the basic hash maps operations as function points.
type Ordered ¶
type Ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
~float32 | ~float64 |
~string
}
Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >.
type RobinHood ¶
type RobinHood[K comparable, V any] struct { // contains filtered or unexported fields }
RobinHood is a hash map that uses linear probing in combination with robin hood hashing as collision strategy. The hashmap resizes if the max PSL reached log2(n). This means that all operations including Get, Put, Remove have a worse case performance of O(log(n)). The expected max PSL for a full robin hood hash map is O(ln(n)), means a resizing happens at a expected default load of 0.8. The max load factor can be changed with `MaxLoad()`. The result is a good trade off between performance and memory consumption. Note that the performance for a open addressing hash map depends also on the key and value size. For higher storage sizes for the keys and values use a hashmap that uses another strategy like the golang std map.
func NewRobinHood ¶
func NewRobinHood[K comparable, V any]() *RobinHood[K, V]
NewRobinHood creates a ready to use `RobinHood` hash map with default settings.
func NewRobinHoodWithHasher ¶
func NewRobinHoodWithHasher[K comparable, V any](hasher HashFn[K]) *RobinHood[K, V]
NewRobinHoodWithHasher same as `NewRobinHood` but with a given hash function.
func (*RobinHood[K, V]) Clear ¶
func (m *RobinHood[K, V]) Clear()
Clear removes all key-value pairs from the map.
func (*RobinHood[K, V]) Each ¶
Each calls 'fn' on every key-value pair in the hash map in no particular order. If 'fn' returns true, the iteration stops.
func (*RobinHood[K, V]) Get ¶
Get returns the value stored for this key, or false if there is no such value.
Note:
- There exists also other search strategies like organ-pipe search or smart search, where searching starts around the mean value (mean, mean − 1, mean + 1, mean − 2, mean + 2, ...)
- Here it is used the simplest technic, which is more cache friendly and does not track other metic values.
func (*RobinHood[K, V]) MaxLoad ¶
MaxLoad forces resizing if the ratio is reached. Useful values are in range [0.5-0.9]. Returns ErrOutOfRange if `lf` is not in the open range (0.0,1.0).
func (*RobinHood[K, V]) Put ¶
Put maps the given key to the given value. If the key already exists its value will be overwritten with the new value. Returns true, if the element is a new item in the hash map. go:inline
func (*RobinHood[K, V]) Remove ¶
Remove removes the specified key-value pair from the map. Returns true, if the element was in the hash map.
type Unordered ¶ added in v0.2.0
type Unordered[K comparable, V any] struct { // contains filtered or unexported fields }
Unordered is a hash map implementation, where the elements are organized into buckets depending on their hash values. Collisions are chained in a single linked list. An inserted value keeps its memory address, means a element in a bucket will not copied or swapped. That supports holding points instead of copy by value. see: `Insert` and `lookup`.
func NewUnordered ¶ added in v0.2.0
func NewUnordered[K comparable, V any]() *Unordered[K, V]
NewUnordered creates a ready to use `unordered` hash map with default settings.
func NewUnorderedWithHasher ¶ added in v0.2.0
func NewUnorderedWithHasher[K comparable, V any](hasher HashFn[K]) *Unordered[K, V]
NewUnorderedWithHasher same as `NewUnordered` but with a given hash function.
func (*Unordered[K, V]) Clear ¶ added in v0.2.0
func (m *Unordered[K, V]) Clear()
Clear removes all key-value pairs from the map.
func (*Unordered[K, V]) Each ¶ added in v0.2.0
Each calls 'fn' on every key-value pair in the hash map in no particular order. If 'fn' returns true, the iteration stops.
func (*Unordered[K, V]) Get ¶ added in v0.2.0
Get returns the value stored for this key, or false if not found.
func (*Unordered[K, V]) Insert ¶ added in v0.2.0
Insert returns a pointer to a zero allocated value. These pointer is valid until the key is part of the hash map. Note, use `Put` for small values.
func (*Unordered[K, V]) Lookup ¶ added in v0.2.0
func (m *Unordered[K, V]) Lookup(key K) *V
Lookup returns a pointer to the stored value for this key or nil if not found. The pointer is valid until the key is part of the hash map. Note, use `Get` for small values.
func (*Unordered[K, V]) Put ¶ added in v0.2.0
Put maps the given key to the given value. If the key already exists its value will be overwritten with the new value. Returns true, if the element is a new item in the hash map. go:inline
func (*Unordered[K, V]) Remove ¶ added in v0.2.0
Remove removes the specified key-value pair from the map. Returns true, if the element was in the hash map.
Source Files