hashmap

README

hashmap

An efficient hashmap implementation in Go.

Features

• Support for Generics.
• Map and Set types for unordered key-value maps and sets,
• xxh3 algorithm
• Open addressing with Robin hood hashing
• Automatically shinks memory on deletes (no memory leaks).
• Pretty darn good performance. 🚀 (benchmarks).

For ordered key-value data, check out the tidwall/btree package.

Getting Started

Installing

To start using hashmap, install Go and run go get:

go get github.com/tidwall/hashmap

This will retrieve the library.

Usage

The Map type works similar to a standard Go map, and includes the methods: Set, Get, Delete, Len, Scan, Keys, Values, and Copy.

var m hashmap.Map[string, string]
m.Set("Hello", "Dolly!")
val, _ := m.Get("Hello")
fmt.Printf("%v\n", val)
val, _ = m.Delete("Hello")
fmt.Printf("%v\n", val)
val, _ = m.Get("Hello")
fmt.Printf("%v\n", val)

// Output:
// Dolly!
// Dolly!
//

The Set type is like Map but only for keys. It includes the methods: Insert, Contains, Delete, Len, Scan and Keys.

var m hashmap.Set[string]
m.Insert("Andy")
m.Insert("Kate")
m.Insert("Janet")

fmt.Printf("%v\n", m.Contains("Kate"))
fmt.Printf("%v\n", m.Contains("Bob"))
fmt.Printf("%v\n", m.Contains("Andy"))

// Output:
// true
// false
// true

Performance

See BENCH.md for more info.

Contact

Josh Baker @tidwall

License

Source code is available under the MIT License.

Documentation

Index

• type Map
  • func New[K comparable, V any](cap int) *Map[K, V]
  • func (m *Map[K, V]) Copy() *Map[K, V]
  • func (m *Map[K, V]) Delete(key K) (prev V, deleted bool)
  • func (m *Map[K, V]) Get(key K) (value V, ok bool)
  • func (m *Map[K, V]) GetPos(pos uint64) (key K, value V, ok bool)
  • func (m *Map[K, V]) Keys() []K
  • func (m *Map[K, V]) Len() int
  • func (m *Map[K, V]) Scan(iter func(key K, value V) bool)
  • func (m *Map[K, V]) Set(key K, value V) (V, bool)
  • func (m *Map[K, V]) Values() []V
• type Set
  • func (tr *Set[K]) Contains(key K) bool
  • func (tr *Set[K]) Copy() *Set[K]
  • func (tr *Set[K]) Delete(key K)
  • func (s *Set[K]) GetPos(pos uint64) (key K, ok bool)
  • func (tr *Set[K]) Insert(key K)
  • func (tr *Set[K]) Keys() []K
  • func (tr *Set[K]) Len() int
  • func (tr *Set[K]) Scan(iter func(key K) bool)

Types

type Map

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

Map is a hashmap. Like map[string]interface{}

func New

func New[K comparable, V any](cap int) *Map[K, V]

New returns a new Map. Like map[string]interface{}

func (*Map[K, V]) Copy

func (m *Map[K, V]) Copy() *Map[K, V]

Copy the hashmap.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K) (prev V, deleted bool)

Delete deletes a value for a key. Returns the deleted value, or false when no value was assigned.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (value V, ok bool)

Get returns a value for a key. Returns false when no value has been assign for key.

func (*Map[K, V]) GetPos

func (m *Map[K, V]) GetPos(pos uint64) (key K, value V, ok bool)

GetPos gets a single keys/value nearby a position. The pos param can be any valid uint64. Useful for grabbing a random item from the map.

func (*Map[K, V]) Keys

func (m *Map[K, V]) Keys() []K

Keys returns all keys as a slice

func (*Map[K, V]) Len

func (m *Map[K, V]) Len() int

Len returns the number of values in map.

func (*Map[K, V]) Scan

func (m *Map[K, V]) Scan(iter func(key K, value V) bool)

Scan iterates over all key/values. It's not safe to call or Set or Delete while scanning.

func (*Map[K, V]) Set

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

Set assigns a value to a key. Returns the previous value, or false when no value was assigned.

func (*Map[K, V]) Values

func (m *Map[K, V]) Values() []V

Values returns all values as a slice

type Set

type Set[K comparable] struct {
	// contains filtered or unexported fields
}

func (*Set[K]) Contains

func (tr *Set[K]) Contains(key K) bool

Get a value for key

func (*Set[K]) Copy

func (tr *Set[K]) Copy() *Set[K]

Copy the set. This is a copy-on-write operation and is very fast because it only performs a shadow copy.

func (*Set[K]) Delete

func (tr *Set[K]) Delete(key K)

Delete an item

func (*Set[K]) GetPos

func (s *Set[K]) GetPos(pos uint64) (key K, ok bool)

GetPos gets a single keys/value nearby a position. The pos param can be any valid uint64. Useful for grabbing a random item from the Set.

func (*Set[K]) Insert

func (tr *Set[K]) Insert(key K)

Insert an item

func (*Set[K]) Keys

func (tr *Set[K]) Keys() []K

Keys returns all keys as a slice

func (*Set[K]) Len

func (tr *Set[K]) Len() int

Len returns the number of items in the tree

func (*Set[K]) Scan

func (tr *Set[K]) Scan(iter func(key K) bool)