haxmap

README

HaxMap

A blazing fast concurrent hashmap

The hashing algorithm used was xxHash and the hashmap's buckets were implemented using Harris lock-free list

Installation

You need Golang 1.19.x or above

$ go get github.com/alphadose/haxmap

Usage

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 the latest generics-enabled cornelk-hashmap

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

1. Concurrent Reads Only

name                         time/op
HaxMapReadsOnly-8            10.9µs ±11%
GoSyncMapReadsOnly-8         23.0µs ± 7%
CornelkMapReadsOnly-8        12.3µs ±11%

name                         alloc/op
HaxMapReadsOnly-8             0.00B
GoSyncMapReadsOnly-8          0.00B
CornelkMapReadsOnly-8         0.00B

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      12.6µs ±11%
GoSyncMapReadsWithWrites-8   25.6µs ±10%
CornelkMapReadsWithWrites-8  14.3µs ±13%

name                         alloc/op
HaxMapReadsWithWrites-8      1.46kB ± 3%
GoSyncMapReadsWithWrites-8   6.19kB ± 6%
CornelkMapReadsWithWrites-8  6.70kB ± 9%

name                         allocs/op
HaxMapReadsOnly-8              0.00
HaxMapReadsWithWrites-8         183 ± 3%
GoSyncMapReadsOnly-8           0.00
GoSyncMapReadsWithWrites-8      573 ± 7%
CornelkMapReadsOnly-8          0.00
CornelkMapReadsWithWrites-8     239 ± 9%

From the above results it is evident that haxmap takes the least time, memory and allocations in all cases making it the best golang concurrent hashmap in this period of time

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`
func customStringHasher(s string) uintptr {
	return uintptr(len(s))
}

func main() {
	m := haxmap.New[string, string]() // initialize a string-string map
	m.SetHasher(customStringHasher) // this overrides the default xxHash algorithm

	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)
  • func (m *HashMap[K, V]) SetHasher(hs func(K) uintptr)

Constants

const (

	// DefaultSize is the default size for a zero allocated map
	DefaultSize = 256

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

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.

func (*HashMap[K, V]) SetHasher

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

SetHasher sets the hash function to the one provided by the user