rhh

Documentation

Index

• Variables
• func Dist(hash, i, capacity int64) int64
• func HashKey(key []byte) int64
• func HashUint64(key uint64) int64
• type HashMap
  • func NewHashMap(opt Options) *HashMap
  • func (m *HashMap) AverageProbeCount() float64
  • func (m *HashMap) Cap() int64
  • func (m *HashMap) Elem(i int64) (key []byte, value interface{})
  • func (m *HashMap) Get(key []byte) interface{}
  • func (m *HashMap) Grow(sz int64)
  • func (m *HashMap) Keys() [][]byte
  • func (m *HashMap) Len() int64
  • func (m *HashMap) LoadFactor() int
  • func (m *HashMap) PrometheusCollectors() []prometheus.Collector
  • func (m *HashMap) Put(key []byte, val interface{})
  • func (m *HashMap) PutQuiet(key []byte, val interface{})
  • func (m *HashMap) Reset()
• type Metrics
  • func NewMetrics(namespace, subsystem string, labels prometheus.Labels) *Metrics
  • func (m *Metrics) PrometheusCollectors() []prometheus.Collector
• type Options

Variables

var DefaultOptions = Options{
	Capacity:       256,
	LoadFactor:     90,
	MetricsEnabled: true,
}

DefaultOptions represents a default set of options to pass to NewHashMap().

Functions

func Dist

func Dist(hash, i, capacity int64) int64

Dist returns the probe distance for a hash in a slot index. NOTE: Capacity must be a power of 2.

func HashKey

func HashKey(key []byte) int64

HashKey computes a hash of key. Hash is always non-zero.

func HashUint64

func HashUint64(key uint64) int64

HashUint64 computes a hash of an int64. Hash is always non-zero.

Types

type HashMap

type HashMap struct {
	// contains filtered or unexported fields
}

HashMap represents a hash map that implements Robin Hood Hashing. https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf

func NewHashMap

func NewHashMap(opt Options) *HashMap

NewHashMap initialises a new Hashmap with the provided options.

func (*HashMap) AverageProbeCount

func (m *HashMap) AverageProbeCount() float64

AverageProbeCount returns the average number of probes for each element.

func (*HashMap) Cap

func (m *HashMap) Cap() int64

Cap returns the number of key/values set in map.

func (*HashMap) Elem

func (m *HashMap) Elem(i int64) (key []byte, value interface{})

Elem returns the i-th key/value pair of the hash map.

func (*HashMap) Get

func (m *HashMap) Get(key []byte) interface{}

Get returns the value for a key from the Hashmap, or nil if no key exists.

func (*HashMap) Grow

func (m *HashMap) Grow(sz int64)

Grow increases the capacity and reinserts all existing hashes & elements.

func (*HashMap) Keys

func (m *HashMap) Keys() [][]byte

Keys returns a list of sorted keys.

func (*HashMap) Len

func (m *HashMap) Len() int64

Len returns the number of key/values set in map.

func (*HashMap) LoadFactor

func (m *HashMap) LoadFactor() int

func (*HashMap) PrometheusCollectors

func (m *HashMap) PrometheusCollectors() []prometheus.Collector

PrometheusCollectors returns the metrics associated with this hashmap.

func (*HashMap) Put

func (m *HashMap) Put(key []byte, val interface{})

Put stores the value at key in the Hashmap, overwriting an existing value if one exists. If the maximum load of the Hashmap is reached, the Hashmap will first resize itself.

func (*HashMap) PutQuiet

func (m *HashMap) PutQuiet(key []byte, val interface{})

PutQuiet is equivalent to Put, but no instrumentation code is executed. It can be faster when many keys are being inserted into the Hashmap.

func (*HashMap) Reset

func (m *HashMap) Reset()

Reset clears the values in the map without deallocating the space.

type Metrics

type Metrics struct {
	LoadFactor         *prometheus.GaugeVec     // Load factor of the hashmap.
	Size               *prometheus.GaugeVec     // Number of items in hashmap.
	GetDuration        *prometheus.HistogramVec // Sample of get times.
	LastGetDuration    *prometheus.GaugeVec     // Sample of most recent get time.
	InsertDuration     *prometheus.HistogramVec // Sample of insertion times.
	LastInsertDuration *prometheus.GaugeVec     // Sample of most recent insertion time.
	LastGrowDuration   *prometheus.GaugeVec     // Most recent growth time.
	MeanProbeCount     *prometheus.GaugeVec     // Average number of probes for each element.

	// These metrics have an extra label status = {"hit", "miss"}
	Gets *prometheus.CounterVec // Number of times item retrieved.
	Puts *prometheus.CounterVec // Number of times item inserted.
}

func NewMetrics

func NewMetrics(namespace, subsystem string, labels prometheus.Labels) *Metrics

NewMetrics initialises prometheus metrics for tracking an RHH hashmap.

func (*Metrics) PrometheusCollectors

func (m *Metrics) PrometheusCollectors() []prometheus.Collector

PrometheusCollectors satisfies the prom.PrometheusCollector interface.

type Options

type Options struct {
	Capacity       int64
	LoadFactor     int
	MetricsEnabled bool
	Metrics        *Metrics
	Labels         prometheus.Labels
}

Options represents initialization options that are passed to NewHashMap().