hashmap

README

hashmap

Overview

A Golang lock-free thread-safe HashMap optimized for fastest read access.

It requires Golang 1.19+ as it makes use of Generics and the new atomic package helpers.

Warning: This library and derived work is experimental and should not be used in production. It contains an unfixed bug that can cause writes to be lost.

Usage

The supported key types are string, int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr.

Set a value for a key in the map:

m := New[string, int]()
m.Set("amount", 123)

Read a value for a key from the map:

value, ok := m.Get("amount")

Use the map to count URL requests:

m := New[string, *int64]()
var i int64
counter, _ := m.GetOrInsert("api/123", &i)
atomic.AddInt64(counter, 1) // increase counter
...
count := atomic.LoadInt64(counter) // read counter

Benchmarks

Reading from the hash map in a thread-safe way is nearly as fast as reading from a standard Golang map in an unsafe way and twice as fast as Go's sync.Map:

BenchmarkReadHashMapUint-8                       2477167               481.8 ns/op
BenchmarkReadHaxMapUint-8                        2354264               512.0 ns/op
BenchmarkReadGoMapUintUnsafe-8                   3317725               355.6 ns/op
BenchmarkReadGoMapUintMutex-8                      82105             14534 ns/op
BenchmarkReadGoSyncMapUint-8                      980110              1273 ns/op

Reading from the map while writes are happening:

BenchmarkReadHashMapWithWritesUint-8             1855539               649.4 ns/op
BenchmarkReadHaxMapWithWritesUint-8              1719477               672.6 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8            770605              1474 ns/op

Write performance without any concurrent reads:

BenchmarkWriteHashMapUint-8                        29740             45577 ns/op
BenchmarkWriteGoMapMutexUint-8                    179068              6989 ns/op
BenchmarkWriteGoSyncMapUint-8                      21388             54012 ns/op

The benchmarks were run with Golang 1.18.3 on Linux using make benchmark.

Benefits over Golang's builtin map

• Faster

• thread-safe access without need of a(n extra) mutex

• Compare-and-swap access for values

Benefits over Golang's sync.Map

• Faster

Technical details

• Technical design decisions have been made based on benchmarks that are stored in an external repository: go-benchmark

• The library uses a sorted doubly linked list and a slice as an index into that list.

• The Get() function contains helper functions that have been inlined manually until the Golang compiler will inline them automatically.

• It optimizes the slice access by circumventing the Golang size check when reading from the slice. Once a slice is allocated, the size of it does not change. The library limits the index into the slice, therefore the Golang size check is obsolete. When the slice reaches a defined fill rate, a bigger slice is allocated and all keys are recalculated and transferred into the new slice.

Documentation

Overview

Package hashmap provides a lock-free and thread-safe HashMap.

Index

• Constants
• type HashMap
  • func New[Key keyConstraint, Value any]() *HashMap[Key, Value]
  • func NewSized[Key keyConstraint, Value any](size uintptr) *HashMap[Key, Value]
  • func (m *HashMap[Key, Value]) Del(key Key) bool
  • func (m *HashMap[Key, Value]) FillRate() int
  • func (m *HashMap[Key, Value]) Get(key Key) (Value, bool)
  • func (m *HashMap[Key, Value]) GetOrInsert(key Key, value Value) (Value, bool)
  • func (m *HashMap[Key, Value]) Grow(newSize uintptr)
  • func (m *HashMap[Key, Value]) Insert(key Key, value Value) bool
  • func (m *HashMap[Key, Value]) Iter() <-chan KeyValue[Key, Value]
  • func (m *HashMap[Key, Value]) Len() int
  • func (m *HashMap[Key, Value]) Set(key Key, value Value)
  • func (m *HashMap[Key, Value]) String() string
• type KeyValue
• type List
  • func NewList[Key keyConstraint, Value any]() *List[Key, Value]
  • func (l *List[Key, Value]) Add(element, searchStart *ListElement[Key, Value]) (existed bool, inserted bool)
  • func (l *List[Key, Value]) AddOrUpdate(element, searchStart *ListElement[Key, Value]) bool
  • func (l *List[Key, Value]) Cas(element *ListElement[Key, Value], oldValue *Value, ...) bool
  • func (l *List[Key, Value]) Delete(element *ListElement[Key, Value])
  • func (l *List[Key, Value]) First() *ListElement[Key, Value]
  • func (l *List[Key, Value]) Head() *ListElement[Key, Value]
  • func (l *List[Key, Value]) Len() int
• type ListElement
  • func (e *ListElement[Key, Value]) Next() *ListElement[Key, Value]
  • func (e *ListElement[Key, Value]) Previous() *ListElement[Key, Value]
  • func (e *ListElement[Key, Value]) Value() Value

Constants

const DefaultSize = 8

DefaultSize is the default size for a zero allocated map.

const MaxFillRate = 50

MaxFillRate is the maximum fill rate for the slice before a resize will happen.

Types

type HashMap

type HashMap[Key keyConstraint, Value any] struct {
	// contains filtered or unexported fields
}

HashMap implements a read optimized hash map.

func New

func New[Key keyConstraint, Value any]() *HashMap[Key, Value]

New returns a new HashMap instance.

func NewSized

func NewSized[Key keyConstraint, Value any](size uintptr) *HashMap[Key, Value]

NewSized returns a new HashMap instance with a specific initialization size.

func (*HashMap[Key, Value]) Del

func (m *HashMap[Key, Value]) Del(key Key) bool

Del deletes the key from the map and returns whether the key was deleted.

func (*HashMap[Key, Value]) FillRate

func (m *HashMap[Key, Value]) FillRate() int

FillRate returns the fill rate of the map as a percentage integer.

func (*HashMap[Key, Value]) Get

func (m *HashMap[Key, Value]) Get(key Key) (Value, bool)

Get retrieves an element from the map under given hash key.

func (*HashMap[Key, Value]) GetOrInsert

func (m *HashMap[Key, Value]) GetOrInsert(key Key, value Value) (Value, bool)

GetOrInsert returns the existing value for the key if present. Otherwise, it stores and returns the given value. The returned bool is true if the value was loaded, false if stored.

func (*HashMap[Key, Value]) Grow

func (m *HashMap[Key, Value]) Grow(newSize uintptr)

Grow resizes the hashmap to a new size, the size gets rounded up to next power of 2. To double the size of the hashmap use newSize 0. This function returns immediately, the resize operation is done in a goroutine. No resizing is done in case of another resize operation already being in progress.

func (*HashMap[Key, Value]) Insert

func (m *HashMap[Key, Value]) Insert(key Key, value Value) bool

Insert sets the value under the specified key to the map if it does not exist yet. If a resizing operation is happening concurrently while calling Insert, the item might show up in the map after the resize operation is finished. Returns true if the item was inserted or false if it existed.

func (*HashMap[Key, Value]) Iter

func (m *HashMap[Key, Value]) Iter() <-chan KeyValue[Key, Value]

Iter returns an iterator which can be used in a for range loop. The order of the items is sorted by hash keys.

func (*HashMap[Key, Value]) Len

func (m *HashMap[Key, Value]) Len() int

Len returns the number of elements within the map.

func (*HashMap[Key, Value]) Set

func (m *HashMap[Key, Value]) Set(key Key, value Value)

Set sets the value under the specified key to the map. An existing item for this key will be overwritten. If a resizing operation is happening concurrently while calling Set, the item might show up in the map after the resize operation is finished.

func (*HashMap[Key, Value]) String

func (m *HashMap[Key, Value]) String() string

String returns the map as a string, only hashed keys are printed.

type KeyValue

type KeyValue[Key keyConstraint, Value any] struct {
	Key   Key
	Value Value
}

KeyValue represents a key/value that is returned by the iterator.

type List

type List[Key keyConstraint, Value any] struct {
	// contains filtered or unexported fields
}

List is a sorted doubly linked list.

func NewList

func NewList[Key keyConstraint, Value any]() *List[Key, Value]

NewList returns an initialized list.

func (*List[Key, Value]) Add

func (l *List[Key, Value]) Add(element, searchStart *ListElement[Key, Value]) (existed bool, inserted bool)

Add adds an item to the list and returns false if an item for the hash existed. searchStart = nil will start to search at the head item.

func (*List[Key, Value]) AddOrUpdate

func (l *List[Key, Value]) AddOrUpdate(element, searchStart *ListElement[Key, Value]) bool

AddOrUpdate adds or updates an item to the list.

func (*List[Key, Value]) Cas

func (l *List[Key, Value]) Cas(element *ListElement[Key, Value], oldValue *Value, searchStart *ListElement[Key, Value]) bool

Cas compares and swaps the value of an item in the list.

func (*List[Key, Value]) Delete

func (l *List[Key, Value]) Delete(element *ListElement[Key, Value])

Delete deletes an element from the list.

func (*List[Key, Value]) First

func (l *List[Key, Value]) First() *ListElement[Key, Value]

First returns the first item of the list.

func (*List[Key, Value]) Head

func (l *List[Key, Value]) Head() *ListElement[Key, Value]

Head returns the head item of the list.

func (*List[Key, Value]) Len

func (l *List[Key, Value]) Len() int

Len returns the number of elements within the list.

type ListElement

type ListElement[Key keyConstraint, Value any] struct {
	// contains filtered or unexported fields
}

ListElement is an element of a list.

func (*ListElement[Key, Value]) Next

func (e *ListElement[Key, Value]) Next() *ListElement[Key, Value]

Next returns the item on the right.

func (*ListElement[Key, Value]) Previous

func (e *ListElement[Key, Value]) Previous() *ListElement[Key, Value]

Previous returns the item on the left.

func (*ListElement[Key, Value]) Value

func (e *ListElement[Key, Value]) Value() Value

Value returns the value of the list item.