README
¶
rhmap - a robin-hood hashmap in golang
In other words: map[[]byte][]byte or map[[]byte]SomeOtherType
Example
var size = 97 // Ideally, some prime number.
m := rhmap.New(size)
wasNew, err := m.Set([]byte("hi"), []byte("world"))
// wasNew == true
v, ok := m.Get([]byte("hi"))
// ok == true
// v == []byte("world")
previous, existed := m.Del([]byte("hi"))
// existed == true
// previous == []byte("world")
Some features
KeyandValtypes are[]byteGet(),Set(), andDel()methods.Visit()method with key-val callback.CopyTo(anotherRHMap)method.- Overridable hash function -- see the
HashFuncfield. - Overridable growth multiplier function -- see the
Growthfield. - Overridable grow function -- see the
Growfield. - Automatic growth when linear probe distances become larger than a
configured maximum distance -- see the
MaxDistancefield. - All fields are public for advanced user tweaking.
- An RHMap is not concurrent safe -- please use your own favorite outside sync approaches.
- Makefile shows how to codegen maps of different types using sed.
Reset()method allows an RHMap to be efficiently cleared, and the underlying, already allocated memory will be recycled for reuse, which can reduce garbage memory pressure for some applications.- The
storesubpackage provides map and heap implementations that can optionally spill out to files when memory usage grows too large.
Motivations
The RHMap was intended for a use case where many application data
objects needed to be processed, where the processing of a single data
object needed its own temporary hashmap instance. The standard golang
hashmap did not support []byte keys, so conversions from []byte
to-and-from strings (i.e., we were using map[string][]byte) was
creating garbage. Instead, we needed a (mythical)
map[[]byte][]byte.
License
Apache 2.0
Documentation
¶
Overview ¶
Package rhmap provides a map[[]byte][]byte based on the robin-hood hashmap algorithm.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrNilKey = errors.New("nil key")
ErrNilKey means a key was nil.
Functions ¶
Types ¶
type RHMap ¶
type RHMap struct {
// Items are the slots of the hashmap for items.
Items []Item
// Number of keys in the RHMap.
Count int
// Overridable hash func. Defaults to hash/fnv.New32a().
HashFunc func(Key) uint32
// When any item's distance gets too large, grow the RHMap.
// Defaults to 10.
MaxDistance int
// Overridable func to calculate a size multiplier when resizing
// for growth is needed. Default returns a constant 2.0.
Growth func(*RHMap) float64
// Overridable func to grow the RHMap.
Grow func(m *RHMap, newSize int)
}
RHMap is a hashmap that uses the robinhood algorithm. This implementation is not concurrent safe.
func (*RHMap) Del ¶
Del removes a key/val from the RHMap. The previous val, if it existed, is returned.
func (*RHMap) Reset ¶
func (m *RHMap) Reset()
Reset clears RHMap, where already allocated memory will be reused.
func (*RHMap) Set ¶
Set inserts or updates a key/val into the RHMap. The returned wasNew will be true if the mutation was on a newly seen, inserted key, and wasNew will be false if the mutation was an update to an existing key.
NOTE: RHMap does not keep its own copy of the key/val's. Especially, applications should take care not to mutate the key. Careful mutations to the val bytes that do not resize the val slice, however, should work.
Source Files
Directories