README
¶
Golang Hash Maps
This package collects several hash map implementations:
UnorderedHash Map, a classic hash table with separate chaining in a single linked list per bucket to handle collisions.Robin HoodHash Map, an open addressing hash table with robin hood hashing and back shifting.HopscotchHash Map, an open addressing hash table with worst case constant runtime for lookup and delete operations.FlatHash Map, an open addressing hash table with linear probing.
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.
Index ¶
- Constants
- Variables
- func NextPowerOf2(i uint64) uint64
- type Flat
- func (m *Flat[K, V]) Clear()
- func (m *Flat[K, V]) Copy() *Flat[K, V]
- func (m *Flat[K, V]) Each(fn func(key K, val V) bool)
- func (m *Flat[K, V]) Get(key K) (V, bool)
- func (m *Flat[K, V]) Load() float32
- func (m *Flat[K, V]) Put(key K, val V) bool
- func (m *Flat[K, V]) Remove(key K) bool
- func (m *Flat[K, V]) Reserve(n uintptr)
- func (m *Flat[K, V]) Size() int
- type HashFn
- type Hopscotch
- func (m *Hopscotch[K, V]) Clear()
- func (m *Hopscotch[K, V]) Copy() *Hopscotch[K, V]
- func (m *Hopscotch[K, V]) Each(fn func(key K, val V) bool)
- func (m *Hopscotch[K, V]) Get(key K) (V, bool)
- func (m *Hopscotch[K, V]) Load() float32
- func (m *Hopscotch[K, V]) MaxLoad(lf float32) error
- func (m *Hopscotch[K, V]) Put(key K, val V) bool
- func (m *Hopscotch[K, V]) Remove(key K) bool
- func (m *Hopscotch[K, V]) Reserve(n uintptr)
- func (m *Hopscotch[K, V]) Size() int
- type IHashMap
- 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
Constants ¶
const ( // DefaultMaxLoad is the default value for the load factor for: // -Hopscotch // -Robin Hood // hashmaps, which can be changed with MaxLoad(). This value is a // trade-off of runtime and memory consumption. DefaultMaxLoad = 0.7 )
Variables ¶
var ( // ErrOutOfRange signals an out of range request. ErrOutOfRange = errors.New("out of range") )
Functions ¶
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 Flat ¶ added in v0.3.0
type Flat[K comparable, V any] struct { // contains filtered or unexported fields }
Flat is a open addressing hash map implementation which uses linear probing as conflict resolution.
func NewFlat ¶ added in v0.3.0
func NewFlat[K comparable, V any]() *Flat[K, V]
NewFlat creates a new ready to use flat hash map.
Note: This map has zero memory overhead per bucket and uses therefore the golang default variable initialization representation as tracking. This means in details a Get, Put or Remove call fails, if the key is:
- 0 (int, uint, uint64, ...)
- 0.0 (float32, float64)
- "" (string)
func NewFlatWithHasher ¶ added in v0.3.0
func NewFlatWithHasher[K comparable, V any](empty K, hasher HashFn[K]) *Flat[K, V]
NewFlatWithHasher constructs a new map with the given hasher. Furthermore the representation for a empty bucket can be set.
func (*Flat[K, V]) Clear ¶ added in v0.3.0
func (m *Flat[K, V]) Clear()
Clear removes all key-value pairs from the map.
func (*Flat[K, V]) Each ¶ added in v0.3.0
Each calls 'fn' on every key-value pair in the hashmap in no particular order.
func (*Flat[K, V]) Get ¶ added in v0.3.0
Get returns the value stored for this key, or false if not found.
func (*Flat[K, V]) Put ¶ added in v0.3.0
Put maps the given key to the given value. If the key already exists its value will be overwritten with the new value.
func (*Flat[K, V]) Remove ¶ added in v0.3.0
Remove removes the specified key-value pair from the map.
type Hopscotch ¶ added in v0.4.0
type Hopscotch[K comparable, V any] struct { // contains filtered or unexported fields }
Hopscotch is a hashmap implementation which uses open addressing, where collisions are managed within a limited neighborhood. That is implemented as a dynamically growing bitmap with a default size of 4 and a upper bound of 63. From this it follows a constant lookup time for the Get function. To achieve this invariant linear probing is used for finding an empty slot in the table, if the next empty slot is not within the size of the neighborhood, subsequent swap of closer buckets are done or the size of the neighborhood is increased.
func NewHopscotch ¶ added in v0.4.0
func NewHopscotch[K comparable, V any]() *Hopscotch[K, V]
NewHopscotch creates a ready to use `Hopscotch` hash map with default settings.
func NewHopscotchWithHasher ¶ added in v0.4.0
func NewHopscotchWithHasher[K comparable, V any](hasher HashFn[K]) *Hopscotch[K, V]
NewHopscotchWithHasher same as `NewHopscotch` but with a given hash function.
func (*Hopscotch[K, V]) Clear ¶ added in v0.4.0
func (m *Hopscotch[K, V]) Clear()
Clear removes all key-value pairs from the map.
func (*Hopscotch[K, V]) Each ¶ added in v0.4.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 (*Hopscotch[K, V]) Get ¶ added in v0.4.0
Get returns the value stored for this key, or false if there is no such value.
func (*Hopscotch[K, V]) MaxLoad ¶ added in v0.4.2
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 (*Hopscotch[K, V]) Put ¶ added in v0.4.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.
func (*Hopscotch[K, V]) Remove ¶ added in v0.4.0
Remove removes the specified key-value pair from the map. Returns true, if the element was in the hash map.
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 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 map tracks the distance from the optimum bucket and minimized the variance over all buckets. The expected max PSL for a full robin hood hash map is O(ln(n)). 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 or the Unordered 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.
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