hashmap

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

1,756

110

1,756

View on GitHub

Top Related Projects

generic

1,285

A collection of generic data structures written in Go.

gods

16,091

GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more

Quick Overview

cornelk/hashmap is a high-performance, concurrent hashmap implementation in Go. It provides a thread-safe alternative to the built-in Go map with better performance characteristics for concurrent read and write operations.

Pros

Excellent performance for concurrent read and write operations
Lock-free implementation for improved scalability
Supports generics for type-safe usage
Minimal memory overhead compared to sync.Map

Cons

May have slightly higher memory usage than the built-in Go map for small datasets
Not as widely adopted or battle-tested as the standard library alternatives
Limited feature set compared to more complex concurrent data structures

Code Examples

Creating and using a hashmap:

package main

import (
    "fmt"
    "github.com/cornelk/hashmap"
)

func main() {
    m := hashmap.New[string, int]()
    m.Set("key", 123)
    value, ok := m.Get("key")
    fmt.Printf("Value: %d, Exists: %t\n", value, ok)
}

Concurrent access:

package main

import (
    "fmt"
    "github.com/cornelk/hashmap"
    "sync"
)

func main() {
    m := hashmap.New[int, int]()
    var wg sync.WaitGroup

    for i := 0; i < 100; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            m.Set(i, i*2)
        }(i)
    }

    wg.Wait()
    fmt.Printf("Map size: %d\n", m.Len())
}

Using the ForEach method:

package main

import (
    "fmt"
    "github.com/cornelk/hashmap"
)

func main() {
    m := hashmap.New[string, int]()
    m.Set("a", 1)
    m.Set("b", 2)
    m.Set("c", 3)

    m.ForEach(func(key string, value int) bool {
        fmt.Printf("Key: %s, Value: %d\n", key, value)
        return true
    })
}

Getting Started

To use cornelk/hashmap in your Go project, follow these steps:

Install the package:
```
go get github.com/cornelk/hashmap
```
Import the package in your Go code:
```
import "github.com/cornelk/hashmap"
```

Create a new hashmap and start using it:

m := hashmap.New[string, int]()
m.Set("key", 42)
value, exists := m.Get("key")

That's it! You can now use the hashmap in your Go applications for high-performance concurrent access to key-value pairs.

Competitor Comparisons

generic

1,285

A collection of generic data structures written in Go.

Pros of generic

Offers a wider range of generic data structures (e.g., lists, trees, sets) beyond just maps
Provides more flexibility with customizable comparison functions
Supports Go 1.18+ generics, allowing for type-safe implementations

Cons of generic

Less specialized for hash map performance compared to hashmap
May have a steeper learning curve due to its broader scope
Potentially larger codebase to include in projects

Code Comparison

hashmap:

m := hashmap.New[string, int]()
m.Set("key", 123)
value, ok := m.Get("key")

generic:

m := generic.NewMap[string, int]()
m.Put("key", 123)
value, ok := m.Get("key")

Summary

hashmap focuses specifically on high-performance hash maps, while generic offers a broader range of data structures with more flexibility. hashmap may be preferable for projects requiring optimized hash map operations, whereas generic provides a more comprehensive toolkit for various data structure needs. The choice between the two depends on the specific requirements of the project and the desired balance between specialization and versatility.

gods

16,091

GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more

Pros of gods

Offers a wider variety of data structures and algorithms
More comprehensive documentation and examples
Higher test coverage and better maintained

Cons of gods

Slightly lower performance in some operations
Larger codebase, which may increase complexity for simple use cases
Less focused on specific optimizations for hash maps

Code Comparison

hashmap:

m := hashmap.New[string, int]()
m.Set("key", 123)
value, _ := m.Get("key")

gods:

m := treemap.NewWithStringComparator()
m.Put("key", 123)
value, _ := m.Get("key")

Both libraries provide similar functionality for basic map operations. hashmap focuses specifically on hash maps with a simpler API, while gods offers a broader range of data structures with a more consistent interface across different types.

hashmap is generally faster for basic operations but lacks some of the additional features and flexibility provided by gods. The choice between the two depends on the specific requirements of your project, such as performance needs, variety of data structures required, and desired level of abstraction.

xsync

1,051

Concurrent data structures for Go

Pros of xsync

Offers a wider range of concurrent data structures (Map, RWMutex, AtomicDuration)
Provides better performance for read-heavy workloads due to its sharded design
Supports generic types in Go 1.18+, allowing for type-safe usage

Cons of xsync

May have higher memory overhead due to its sharded structure
Potentially more complex implementation, which could impact maintainability
Lacks some specialized features found in hashmap, like string-optimized maps

Code Comparison

xsync:

m := xsync.NewMapOf[string, int]()
m.Store("key", 42)
value, ok := m.Load("key")

hashmap:

m := hashmap.New[string, int]()
m.Set("key", 42)
value, ok := m.Get("key")

Both libraries provide similar basic functionality for concurrent maps, but xsync offers a more extensive set of concurrent data structures. hashmap focuses on optimized hash map implementations, particularly for string keys. The choice between the two depends on specific use cases and performance requirements.

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

hashmap

Overview

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

It is not a general-use HashMap and currently has slow write performance for write heavy uses.

The minimal supported Golang version is 1.19 as it makes use of Generics and the new atomic package helpers.

Usage

Example uint8 key map uses:

m := New[uint8, int]()
m.Set(1, 123)
value, ok := m.Get(1)

Example string key map uses:

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

Using 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 for numeric key types in a thread-safe way is faster than reading from a standard Golang map in an unsafe way and four times faster than Golang's sync.Map:

ReadHashMapUint-8                676ns Â± 0%
ReadHaxMapUint-8                 689ns Â± 1%
ReadGoMapUintUnsafe-8            792ns Â± 0%
ReadXsyncMapUint-8               954ns Â± 0%
ReadGoSyncMapUint-8             2.62Âµs Â± 1%
ReadSkipMapUint-8               3.27Âµs Â±10%
ReadGoMapUintMutex-8            29.6Âµs Â± 2%

Reading from the map while writes are happening:

ReadHashMapWithWritesUint-8      860ns Â± 1%
ReadHaxMapWithWritesUint-8       930ns Â± 1%
ReadGoSyncMapWithWritesUint-8   3.06Âµs Â± 2%

Write performance without any concurrent reads:

WriteGoMapMutexUint-8           14.8Âµs Â± 2%
WriteHashMapUint-8              22.3Âµs Â± 1%
WriteGoSyncMapUint-8            69.3Âµs Â± 0%

The benchmarks were run with Golang 1.19.1 on Linux and a Ryzen 9 5900X CPU using make benchmark-perflock.

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

Top Related Projects

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot