swiss

README

SwissMap

SwissMap is a hash table adapated from the "SwissTable" family of hash tables from Abseil. It uses AES instructions for fast-hashing and performs key lookups in parallel using SSE instructions. Because of these optimizations, SwissMap is faster and more memory efficient than Golang's built-in map. If you'd like to learn more about its design and implementation, check out this blog post announcing its release.

Example

SwissMap exposes the same interface as the built-in map. Give it a try using this Go playground.

package main

import "github.com/dolthub/swiss"

func main() {
	m := swiss.NewMap[string, int](42)

	m.Put("foo", 1)
	m.Put("bar", 2)

	m.Iter(func(k string, v int) (stop bool) {
		println("iter", k, v)
		return false // continue
	})

	if x, ok := m.Get("foo"); ok {
		println(x)
	}
	if m.Has("bar") {
		x, _ := m.Get("bar")
		println(x)
	}

	m.Put("foo", -1)
	m.Delete("bar")

	if x, ok := m.Get("foo"); ok {
		println(x)
	}
	if m.Has("bar") {
		x, _ := m.Get("bar")
		println(x)
	}

	m.Clear()

	// Output:
	// iter foo 1
	// iter bar 2
	// 1
	// 2
	// -1
}

Documentation

Index

• type Map
  • func NewMap[K comparable, V any](ac *memorypool.Allocator, sz uint32) (m *Map[K, V])
  • func (m *Map[K, V]) Capacity() int
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Count() int
  • func (m *Map[K, V]) Debug()
  • func (m *Map[K, V]) Delete(key K) (ok bool)
  • func (m *Map[K, V]) Get(key K) (value V, ok bool)
  • func (m *Map[K, V]) Has(key K) (ok bool)
  • func (m *Map[K, V]) Iter(cb func(k K, v V) (stop bool))
  • func (m *Map[K, V]) Put(key K, value V)

Types

type Map

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

Map is an open-addressing hash map based on Abseil's flat_hash_map.

func NewMap

func NewMap[K comparable, V any](ac *memorypool.Allocator, sz uint32) (m *Map[K, V])

NewMap constructs a Map.

func (*Map[K, V]) Capacity

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

Capacity returns the number of additional elements the can be added to the Map before resizing.

func (*Map[K, V]) Clear

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

Clear removes all elements from the Map.

func (*Map[K, V]) Count

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

Count returns the number of elements in the Map.

func (*Map[K, V]) Debug

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

func (*Map[K, V]) Delete

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

Delete attempts to remove |key|, returns true successful.

func (*Map[K, V]) Get

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

Get returns the |value| mapped by |key| if one exists.

func (*Map[K, V]) Has

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

Has returns true if |key| is present in |m|.

func (*Map[K, V]) Iter

func (m *Map[K, V]) Iter(cb func(k K, v V) (stop bool))

Iter iterates the elements of the Map, passing them to the callback. It guarantees that any key in the Map will be visited only once, and for un-mutated Maps, every key will be visited once. If the Map is Mutated during iteration, mutations will be reflected on return from Iter, but the set of keys visited by Iter is non-deterministic.

func (*Map[K, V]) Put

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

Put attempts to insert |key| and |value|