haxmap

README

HaxMap

A blazing fast concurrent hashmap

This work is derived from cornelk-hashmap and further performance and API improvements have been made

Installation

You need Golang 1.19.x or above

$ go get github.com/alphadose/haxmap

Usage

Supported map key types -> int, uint, uintptr, string

package main

import (
	"fmt"

	"github.com/alphadose/haxmap"
)

func main() {
	// initialize map with key type `int` and value type `string`
	mep := haxmap.New[int, string]()

	// set a value (overwrites existing value if present)
	mep.Set(1, "one")

	// get the value and print it
	val, ok := mep.Get(1)
	if ok {
		println(val)
	}

	mep.Set(2, "two")
	mep.Set(3, "three")

	// ForEach loop to iterate over all key-value pairs and execute the given lambda
	mep.ForEach(func(key int, value string) {
		fmt.Printf("Key -> %d | Value -> %s\n", key, value)
	})

	// delete values
	mep.Del(1)
	mep.Del(2)
	mep.Del(3)
	mep.Del(0) // delete is safe even if a key doesn't exists

	if mep.Len() == 0 {
		println("cleanup complete")
	}
}

Benchmarks

Benchmarks were performed against golang sync.Map and cornelk-hashmap

All results were computed from benchstat of 30 runs (code available here)

1. Concurrent Reads Only

name                         time/op
HaxMapReadsOnly-8            11.1µs ±12%
GoSyncMapReadsOnly-8         22.0µs ±13%
CornelkMapReadsOnly-8        16.7µs ± 6%

name                         alloc/op
HaxMapReadsOnly-8             0.00B
GoSyncMapReadsOnly-8          0.00B
CornelkMapReadsOnly-8         7.43B ± 8%

name                         allocs/op
HaxMapReadsOnly-8              0.00
GoSyncMapReadsOnly-8           0.00
CornelkMapReadsOnly-8          0.00

1. Concurrent Reads with Writes

name                         time/op
HaxMapReadsWithWrites-8      13.1µs ±11%
GoSyncMapReadsWithWrites-8   25.0µs ±12%
CornelkMapReadsWithWrites-8  20.0µs ± 6%

name                         alloc/op
HaxMapReadsWithWrites-8      6.71kB ± 9%
GoSyncMapReadsWithWrites-8   6.32kB ± 6%
CornelkMapReadsWithWrites-8  10.0kB ± 9%

name                         allocs/op
HaxMapReadsWithWrites-8         239 ± 9%
GoSyncMapReadsWithWrites-8      585 ± 6%
CornelkMapReadsWithWrites-8     407 ± 9%

From the above results it is evident that haxmap is currently the fastest golang concurrent hashmap having the least number of allocs/op and low dynamic memory footprint

Tips

1. HaxMap by default uses xxHash algorithm, but you can override this and plug-in your own custom hash function. Beneath lies an example for the same.

package main

import (
	"github.com/alphadose/haxmap"
)

// your custom hash function
// the hash function signature must adhere to `func(keyType) uintptr`
// where keyType ∈ {int, uint, uintptr, string}
func customStringHasher(s string) uintptr {
	return uintptr(len(s))
}

func main() {
	// initialize a string-string map with your custom hash function
	// this overrides the default xxHash algorithm
	m := &haxmap.HashMap[string, string]{Hasher: customStringHasher}

	m.Set("one", "1")
	val, ok := m.Get("one")
	if ok {
		println(val)
	}
}

1. You can pre-allocate the size of the map which will improve performance in some cases.

package main

import (
	"github.com/alphadose/haxmap"
)

func main() {
	const initialSize = 1 << 10

	// pre-allocating the size of the map will prevent all grow operations
	// until that limit is hit thereby improving performance
	m := haxmap.New[int, string](initialSize)

	m.Set(1, "1")
	val, ok := m.Get(1)
	if ok {
		println(val)
	}
}

Documentation

Index

• Constants
• type HashMap
  • func New[K hashable, V any](size ...uintptr) *HashMap[K, V]
  • func (m *HashMap[K, V]) Del(key K)
  • func (m *HashMap[K, V]) Fillrate() uintptr
  • func (m *HashMap[K, V]) ForEach(lambda func(K, V))
  • func (m *HashMap[K, V]) Get(key K) (value V, ok bool)
  • func (m *HashMap[K, V]) Grow(newSize uintptr)
  • func (m *HashMap[K, V]) Len() uintptr
  • func (m *HashMap[K, V]) Set(key K, value V)
• type List
  • func NewList[K hashable, V any]() *List[K, V]
  • func (l *List[K, V]) AddOrUpdate(element *ListElement[K, V], searchStart *ListElement[K, V]) bool
  • func (l *List[K, V]) Delete(element *ListElement[K, V])
  • func (l *List[K, V]) First() *ListElement[K, V]
  • func (l *List[K, V]) Len() uintptr
• type ListElement
  • func (e *ListElement[K, V]) Next() *ListElement[K, V]
  • func (e *ListElement[K, V]) Previous() *ListElement[K, V]
  • func (e *ListElement[K, V]) Value() (value V)

Constants

const (
	// DefaultSize is the default size for a zero allocated map
	DefaultSize = 8

	// MaxFillRate is the maximum fill rate for the slice before a resize  will happen.
	MaxFillRate = 50
)

Types

type HashMap

type HashMap[K hashable, V any] struct {
	Hasher func(K) uintptr
	// contains filtered or unexported fields
}

HashMap implements a read optimized hash map.

func New

func New[K hashable, V any](size ...uintptr) *HashMap[K, V]

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

func (*HashMap[K, V]) Del

func (m *HashMap[K, V]) Del(key K)

Del deletes the key from the map.

func (*HashMap[K, V]) Fillrate

func (m *HashMap[K, V]) Fillrate() uintptr

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

func (*HashMap[K, V]) ForEach

func (m *HashMap[K, V]) ForEach(lambda func(K, V))

ForEach iterates over key-value pairs and executes the lambda provided for each such pair.

func (*HashMap[K, V]) Get

func (m *HashMap[K, V]) Get(key K) (value V, 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[K, V]) Grow

func (m *HashMap[K, V]) 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[K, V]) Len

func (m *HashMap[K, V]) Len() uintptr

Len returns the number of key-value pairs within the map.

func (*HashMap[K, V]) Set

func (m *HashMap[K, V]) Set(key K, value V)

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.

type List

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

List is a sorted doubly linked list.

func NewList

func NewList[K hashable, V any]() *List[K, V]

NewList returns an initialized list.

func (*List[K, V]) AddOrUpdate

func (l *List[K, V]) AddOrUpdate(element *ListElement[K, V], searchStart *ListElement[K, V]) bool

AddOrUpdate adds or updates an item to the list.

func (*List[K, V]) Delete

func (l *List[K, V]) Delete(element *ListElement[K, V])

Delete deletes an element from the list.

func (*List[K, V]) First

func (l *List[K, V]) First() *ListElement[K, V]

First returns the first item of the list.

func (*List[K, V]) Len

func (l *List[K, V]) Len() uintptr

Len returns the number of elements within the list.

type ListElement

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

ListElement is an element of a list.

func (*ListElement[K, V]) Next

func (e *ListElement[K, V]) Next() *ListElement[K, V]

Next returns the item on the right.

func (*ListElement[K, V]) Previous

func (e *ListElement[K, V]) Previous() *ListElement[K, V]

Previous returns the item on the left.

func (*ListElement[K, V]) Value

func (e *ListElement[K, V]) Value() (value V)

Value returns the value of the list item.