rhmap

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

• Key and Val types are []byte
• Get(), Set(), and Del() methods.
• Visit() method with key-val callback.
• CopyTo(anotherRHMap) method.
• Overridable hash function -- see the HashFunc field.
• Overridable growth multiplier function -- see the Growth field.
• Overridable grow function -- see the Grow field.
• Automatic growth when linear probe distances become larger than a configured maximum distance -- see the MaxDistance field.
• 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 store subpackage 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

• Variables
• func Grow(m *RHMap, newSize int)
• type Item
• type Key
• type RHMap
  • func New(size int) *RHMap
  • func (m *RHMap) CopyTo(dest *RHMap)
  • func (m *RHMap) Del(k Key) (prev Val, existed bool)
  • func (m *RHMap) Get(k Key) (v Val, found bool)
  • func (m *RHMap) Reset()
  • func (m *RHMap) Set(k Key, v Val) (wasNew bool, err error)
  • func (m *RHMap) Visit(callback func(k Key, v Val) (keepGoing bool))
• type Val

Variables

var ErrNilKey = errors.New("nil key")

ErrNilKey means a key was nil.

Functions

func Grow

func Grow(m *RHMap, newSize int)

Grow is the default implementation to grow a RHMap.

Types

type Item

type Item struct {
	Key Key
	Val Val

	Distance int // How far item is from its best position.
}

Item represents an entry in the RHMap.

type Key

type Key []byte

Key is the type for a key. A nil key is invalid.

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 New

func New(size int) *RHMap

New returns a new robinhood hashmap.

func (*RHMap) CopyTo

func (m *RHMap) CopyTo(dest *RHMap)

CopyTo copies key/val's to the dest RHMap.

func (*RHMap) Del

func (m *RHMap) Del(k Key) (prev Val, existed bool)

Del removes a key/val from the RHMap. The previous val, if it existed, is returned.

func (*RHMap) Get

func (m *RHMap) Get(k Key) (v Val, found bool)

Get retrieves the val for a given key.

func (*RHMap) Reset

func (m *RHMap) Reset()

Reset clears RHMap, where already allocated memory will be reused.

func (*RHMap) Set

func (m *RHMap) Set(k Key, v Val) (wasNew bool, err error)

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.

func (*RHMap) Visit

func (m *RHMap) Visit(callback func(k Key, v Val) (keepGoing bool))

Visit invokes the callback on key/val. The callback can return false to exit the visitation early.

type Val

type Val []byte

Val is the type for a val. A nil val is valid.