intmap

package module
v0.0.0-...-9505126 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 3, 2023 License: BSD-2-Clause Imports: 1 Imported by: 1

README

Fast hashmap with integer keys for Golang

GoDoc Go Report Card

intmap

import "github.com/kamstrup/intmap"

Package intmap is a fast hashmap implementation for Golang, specialized for maps with integer type keys. The values can be of any type.

It is a full port of https://github.com/brentp/intintmap to use type parameters (aka generics).

It interleaves keys and values in the same underlying array to improve locality. This is also known as open addressing with linear probing.

It is up to 3X faster than the builtin map:

name                             time/op
Map64Fill-8                       201ms ± 5%
IntIntMapFill-8                   207ms ±31%
StdMapFill-8                      371ms ±11%
Map64Get10PercentHitRate-8        148µs ±40%
IntIntMapGet10PercentHitRate-8    171µs ±50%
StdMapGet10PercentHitRate-8       171µs ±33%
Map64Get100PercentHitRate-8      4.50ms ± 5%
IntIntMapGet100PercentHitRate-8  4.82ms ± 6%
StdMapGet100PercentHitRate-8     15.5ms ±32%

Usage

m := intmap.New[int64,int64](32768)
m.Put(int64(1234), int64(-222))
m.Put(int64(123), int64(33))

v, ok := m.Get(int64(222))
v, ok := m.Get(int64(333))

m.Del(int64(222))
m.Del(int64(333))

fmt.Println(m.Len())

m.ForEach(func(k int64, v int64) {
    fmt.Printf("key: %d, value: %d\n", k, v)
})

m.Clear() // all gone, but buffers kept

Documentation

Overview

Package intmap contains a fast hashmap implementation for maps with keys of any integer type

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type IntKey

type IntKey interface {
	~int | ~uint | ~int64 | ~uint64 | ~int32 | ~uint32 | ~int16 | ~uint16 | ~int8 | ~uint8 | ~uintptr
}

IntKey is a type constraint for values that can be used as keys in Map

type Map

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

Map is a hashmap where the keys are some any integer type.

func New

func New[K IntKey, V any](capacity int) *Map[K, V]

New creates a new map with keys being any integer subtype. The map can store up to the given capacity before reallocation and rehashing occurs.

func (*Map[K, V]) Clear

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

Clear removes all items from the map, but keeps the internal buffers for reuse.

func (*Map[K, V]) Del

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

Del deletes a key and its value, returning true iff the key was found

func (*Map[K, V]) ForEach

func (m *Map[K, V]) ForEach(f func(K, V))

func (*Map[K, V]) Get

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

Get returns the value if the key is found.

func (*Map[K, V]) Len

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

Len returns the number of elements in the map.

func (*Map[K, V]) Put

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

Put adds or updates key with value val.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL