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 is experimental, there are currently no known bugs but more battle-testing is needed.

Usage

Only Go comparable types are supported as keys.

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                	 1601247	       754.2 ns/op
BenchmarkReadHaxMapUint-8                 	 1519165	       788.3 ns/op
BenchmarkReadGoMapUintUnsafe-8            	 1560886	       762.8 ns/op
BenchmarkReadGoMapUintMutex-8             	   42284	     28232 ns/op
BenchmarkReadGoSyncMapUint-8              	  468338	      2672 ns/op

Reading from the map while writes are happening:

BenchmarkReadHashMapWithWritesUint-8      	 1268134	       941.6 ns/op
BenchmarkReadHaxMapWithWritesUint-8       	 1000000	      1045 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8    	  369918	      3149 ns/op

Write performance without any concurrent reads:

BenchmarkWriteHashMapUint-8               	   15384	     79032 ns/op
BenchmarkWriteGoMapMutexUint-8            	   74569	     14874 ns/op
BenchmarkWriteGoSyncMapUint-8             	   10000	    107094 ns/op

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

Benefits over Golang's builtin map

• Faster

• thread-safe access without need of a mutex

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

• For hashing, specialized xxhash implementations are used that match the size of the key type where available

Documentation

Overview

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

Index

• Constants
• type HashMap
  • func New[Key comparable, Value any]() *HashMap[Key, Value]
  • func NewSized[Key comparable, 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]) Len() int
  • func (m *HashMap[Key, Value]) Range(f func(Key, Value) bool)
  • func (m *HashMap[Key, Value]) Set(key Key, value Value)
  • func (m *HashMap[Key, Value]) SetHasher(hasher func(Key) uintptr)
  • func (m *HashMap[Key, Value]) String() string
• type KeyValue
• type List
  • func NewList[Key comparable, Value any]() *List[Key, Value]
  • func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *ListElement[Key, Value], existed bool, inserted bool)
  • func (l *List[Key, Value]) AddOrUpdate(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (*ListElement[Key, 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]) Len() int
• type ListElement
  • func (e *ListElement[Key, Value]) Next() *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 comparable, Value any] struct {
	// contains filtered or unexported fields
}

HashMap implements a read optimized hash map.

func New

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

New returns a new HashMap instance.

func NewSized

func NewSized[Key comparable, 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]) Len

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

Len returns the number of elements within the map.

func (*HashMap[Key, Value]) Range

func (m *HashMap[Key, Value]) Range(f func(Key, Value) bool)

Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

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

func (m *HashMap[Key, Value]) SetHasher(hasher func(Key) uintptr)

SetHasher sets a custom hasher.

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 comparable, Value any] struct {
	Key   Key
	Value Value
}

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

type List

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

List is a sorted linked list.

func NewList

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

NewList returns an initialized list.

func (*List[Key, Value]) Add

func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *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(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (*ListElement[Key, Value], bool)

AddOrUpdate adds or updates an item to 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]) Len

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

Len returns the number of elements within the list.

type ListElement

type ListElement[Key comparable, 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]) Value

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

Value returns the value of the list item.