robin

Documentation

Index

• type RobinHood
  • func New[K comparable, V any]() *RobinHood[K, V]
  • func NewWithHasher[K comparable, V any](hasher shared.HashFn[K]) *RobinHood[K, V]
  • 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

Types

type RobinHood

type RobinHood[K comparable, V any] struct {
	// contains filtered or unexported fields
}

RobinHood is a hashmap that uses linear probing in combination with robin hood hashing as collision strategy. The hashmap tacks the distance from the optimum bucket and minimized the variance over all buckets. The expected max PSL for a full robin hood hashmap 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 hashmap 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 hashmap. the Unordered hashmap.

func New

func New[K comparable, V any]() *RobinHood[K, V]

New creates a ready to use `RobinHood` hashmap with default settings.

func NewWithHasher

func NewWithHasher[K comparable, V any](hasher shared.HashFn[K]) *RobinHood[K, V]

NewWithHasher 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 hashmap.

func (*RobinHood[K, V]) Copy

func (m *RobinHood[K, V]) Copy() *RobinHood[K, V]

Copy returns a copy of this hashmap.

func (*RobinHood[K, V]) Each

func (m *RobinHood[K, V]) Each(fn func(key K, val V) bool)

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

func (m *RobinHood[K, V]) Get(key K) (V, bool)

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]) Load

func (m *RobinHood[K, V]) Load() float32

Load return the current load of the hashmap.

func (*RobinHood[K, V]) MaxLoad

func (m *RobinHood[K, V]) MaxLoad(lf float32) error

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

func (m *RobinHood[K, V]) Put(key K, val V) bool

Put adds the given key-value pair to the hashmap. 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 hashmap.

func (*RobinHood[K, V]) Remove

func (m *RobinHood[K, V]) Remove(key K) bool

Remove removes the specified key-value pair from the hashmap. Returns true, if the element was in the hashmap.

func (*RobinHood[K, V]) Reserve

func (m *RobinHood[K, V]) Reserve(n uintptr)

Reserve sets the number of buckets to the most appropriate to contain at least n elements. If n is lower than that, the function may have no effect.

func (*RobinHood[K, V]) Size

func (m *RobinHood[K, V]) Size() int

Size returns the number of items in the hashmap.