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 ¶
- 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
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
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.
func (*RobinHood[K, V]) MaxLoad ¶
MaxLoad forces resizing if the ratio is reached. useful values are in range [0.5-0.9]
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. Signals if the key is new in the map.
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.
Source Files