hashmap

README

hashmap

Overview

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

Usage

Set a value for a key in the map:

m := &HashMap{}
m.Set("amount", 123)

Read a value for a key from the map:

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

Use the map to count URL requests:

var i int64
actual, _ := m.GetOrInsert("api/123", &i)
counter := (actual).(*int64)
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                	  200000	      6830 ns/op
BenchmarkReadGoMapUintUnsafe-8            	  300000	      4280 ns/op
BenchmarkReadGoMapUintMutex-8             	   30000	     51294 ns/op
BenchmarkReadGoSyncMapUint-8              	  200000	     10351 ns/op

If your keys for the map are already hashes, no extra hashing needs to be done by the map:

BenchmarkReadHashMapHashedKey-8           	 1000000	      1692 ns/op

Reading from the map while writes are happening:

BenchmarkReadHashMapWithWritesUint-8      	  200000	      8395 ns/op
BenchmarkReadGoMapWithWritesUintMutex-8   	   10000	    143793 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8    	  100000	     12221 ns/op

Write performance without any concurrent reads:

BenchmarkWriteHashMapUint-8               	   10000	    210383 ns/op
BenchmarkWriteGoMapMutexUint-8            	   30000	     53331 ns/op
BenchmarkWriteGoSyncMapUint-8             	   10000	    176903 ns/op

The benchmarks were run with Golang 1.10.1 on MacOS.

Benefits over Golangs builtin map

• Faster

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

• Compare-and-swap access for values

• Access functions for keys that are hashes and do not need to be hashed again

Benefits over Golangs sync.Map

• Faster

• Access functions for keys that are hashes and do not need to be hashed again

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, therefor 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

Index

• Constants
• type HashMap
  • func New(size uintptr) *HashMap
  • func (m *HashMap) Cas(key, from, to interface{}) bool
  • func (m *HashMap) CasHashedKey(hashedKey uintptr, from, to interface{}) bool
  • func (m *HashMap) Del(key interface{})
  • func (m *HashMap) DelHashedKey(hashedKey uintptr)
  • func (m *HashMap) Fillrate() uintptr
  • func (m *HashMap) Get(key interface{}) (value interface{}, ok bool)
  • func (m *HashMap) GetHashedKey(hashedKey uintptr) (value interface{}, ok bool)
  • func (m *HashMap) GetOrInsert(key interface{}, value interface{}) (actual interface{}, loaded bool)
  • func (m *HashMap) GetStringKey(key string) (value interface{}, ok bool)
  • func (m *HashMap) GetUintKey(key uintptr) (value interface{}, ok bool)
  • func (m *HashMap) Grow(newSize uintptr)
  • func (m *HashMap) Insert(key interface{}, value interface{}) bool
  • func (m *HashMap) Iter() <-chan KeyValue
  • func (m *HashMap) Len() int
  • func (m *HashMap) Set(key interface{}, value interface{})
  • func (m *HashMap) SetHashedKey(hashedKey uintptr, value interface{})
  • func (m *HashMap) String() string
• type KeyValue
• type List
  • func NewList() *List
  • func (l *List) Add(element *ListElement, searchStart *ListElement) (existed bool, inserted bool)
  • func (l *List) AddOrUpdate(element *ListElement, searchStart *ListElement) bool
  • func (l *List) Cas(element *ListElement, oldValue interface{}, searchStart *ListElement) bool
  • func (l *List) Delete(element *ListElement)
  • func (l *List) First() *ListElement
  • func (l *List) Head() *ListElement
  • func (l *List) Len() int
• type ListElement
  • func (e *ListElement) Next() *ListElement
  • func (e *ListElement) Previous() *ListElement
  • func (e *ListElement) Value() (value interface{})

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 struct {
	// contains filtered or unexported fields
}

HashMap implements a read optimized hash map.

func New

func New(size uintptr) *HashMap

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

func (*HashMap) Cas

func (m *HashMap) Cas(key, from, to interface{}) bool

Cas performs a compare and swap operation sets the value under the specified hash key to the map. An existing item for this key will be overwritten.

func (*HashMap) CasHashedKey

func (m *HashMap) CasHashedKey(hashedKey uintptr, from, to interface{}) bool

CasHashedKey performs a compare and swap operation sets the value under the specified hash key to the map. An existing item for this key will be overwritten.

func (*HashMap) Del

func (m *HashMap) Del(key interface{})

Del deletes the key from the map.

func (*HashMap) DelHashedKey

func (m *HashMap) DelHashedKey(hashedKey uintptr)

DelHashedKey deletes the hashed key from the map.

func (*HashMap) Fillrate

func (m *HashMap) Fillrate() uintptr

Fillrate returns the fill rate of the map as an percentage integer.

func (*HashMap) Get

func (m *HashMap) Get(key interface{}) (value interface{}, ok bool)

Get retrieves an element from the map under given hash key. Using interface{} adds a performance penalty. Please consider using GetUintKey or GetStringKey instead.

func (*HashMap) GetHashedKey

func (m *HashMap) GetHashedKey(hashedKey uintptr) (value interface{}, ok bool)

GetHashedKey retrieves an element from the map under given hashed key.

func (*HashMap) GetOrInsert

func (m *HashMap) GetOrInsert(key interface{}, value interface{}) (actual interface{}, loaded bool)

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

func (*HashMap) GetStringKey

func (m *HashMap) GetStringKey(key string) (value interface{}, ok bool)

GetStringKey retrieves an element from the map under given string key.

func (*HashMap) GetUintKey

func (m *HashMap) GetUintKey(key uintptr) (value interface{}, ok bool)

GetUintKey retrieves an element from the map under given integer key.

func (*HashMap) Grow

func (m *HashMap) Grow(newSize uintptr)

Grow resizes the hashmap to a new 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) Insert

func (m *HashMap) Insert(key interface{}, value interface{}) 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 Set, the item might show up in the map only after the resize operation is finished. Returns true if the item was inserted or false if it existed.

func (*HashMap) Iter

func (m *HashMap) Iter() <-chan KeyValue

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

func (*HashMap) Len

func (m *HashMap) Len() int

Len returns the number of elements within the map.

func (*HashMap) Set

func (m *HashMap) Set(key interface{}, value interface{})

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 only after the resize operation is finished.

func (*HashMap) SetHashedKey

func (m *HashMap) SetHashedKey(hashedKey uintptr, value interface{})

SetHashedKey sets the value under the specified hash key to the map. An existing item for this key will be overwritten. You can use this function if your keys are already hashes and you want to avoid another hashing of the key. Do not use non hashes as keys for this function, the performance would decrease! If a resizing operation is happening concurrently while calling Set, the item might show up in the map only after the resize operation is finished.

func (*HashMap) String

func (m *HashMap) String() string

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

type KeyValue

type KeyValue struct {
	Key   interface{}
	Value interface{}
}

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

type List

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

List is a sorted doubly linked list.

func NewList

func NewList() *List

NewList returns an initialized list.

func (*List) Add

func (l *List) Add(element *ListElement, searchStart *ListElement) (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) AddOrUpdate

func (l *List) AddOrUpdate(element *ListElement, searchStart *ListElement) bool

AddOrUpdate adds or updates an item to the list.

func (*List) Cas

func (l *List) Cas(element *ListElement, oldValue interface{}, searchStart *ListElement) bool

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

func (*List) Delete

func (l *List) Delete(element *ListElement)

Delete deletes an element from the list.

func (*List) First

func (l *List) First() *ListElement

First returns the first item of the list.

func (*List) Head

func (l *List) Head() *ListElement

First returns the head item of the list.

func (*List) Len

func (l *List) Len() int

Len returns the number of elements within the list.

type ListElement

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

ListElement is an element of a list.

func (*ListElement) Next

func (e *ListElement) Next() *ListElement

Next returns the item on the right.

func (*ListElement) Previous

func (e *ListElement) Previous() *ListElement

Previous returns the item on the left.

func (*ListElement) Value

func (e *ListElement) Value() (value interface{})

Value returns the value of the list item.