hashtable

Documentation

Index

• type Map
  • func New[K comparable, V any](nodeManager *node.Manager[K, V]) *Map[K, V]
  • func NewWithSize[K comparable, V any](nodeManager *node.Manager[K, V], size int) *Map[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Delete(key K) node.Node[K, V]
  • func (m *Map[K, V]) DeleteNode(n node.Node[K, V]) node.Node[K, V]
  • func (m *Map[K, V]) Get(key K) (got node.Node[K, V], ok bool)
  • func (m *Map[K, V]) Range(f func(node.Node[K, V]) bool)
  • func (m *Map[K, V]) Set(n node.Node[K, V]) node.Node[K, V]
  • func (m *Map[K, V]) SetIfAbsent(n node.Node[K, V]) node.Node[K, V]
  • func (m *Map[K, V]) Size() int

Types

type Map

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

Map is like a Go map[K]V but is safe for concurrent use by multiple goroutines without additional locking or coordination.

A Map must not be copied after first use.

Map uses a modified version of Cache-Line Hash Table (CLHT) data structure: https://github.com/LPD-EPFL/CLHT

CLHT is built around idea to organize the hash table in cache-line-sized buckets, so that on all modern CPUs update operations complete with at most one cache-line transfer. Also, Get operations involve no write to memory, as well as no mutexes or any other sort of locks. Due to this design, in all considered scenarios Map outperforms sync.Map.

func New

func New[K comparable, V any](nodeManager *node.Manager[K, V]) *Map[K, V]

New creates a new Map instance.

func NewWithSize

func NewWithSize[K comparable, V any](nodeManager *node.Manager[K, V], size int) *Map[K, V]

NewWithSize creates a new Map instance with capacity enough to hold size nodes. If size is zero or negative, the value is ignored.

func (*Map[K, V]) Clear

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

Clear deletes all keys and values currently stored in the map.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K) node.Node[K, V]

Delete deletes the value for a key.

Returns the deleted node or nil if the node wasn't deleted.

func (*Map[K, V]) DeleteNode

func (m *Map[K, V]) DeleteNode(n node.Node[K, V]) node.Node[K, V]

DeleteNode evicts the node for a key.

Returns the evicted node or nil if the node wasn't evicted.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (got node.Node[K, V], ok bool)

Get returns the node.Node stored in the map for a key, or nil if no node is present.

The ok result indicates whether node was found in the map.

func (*Map[K, V]) Range

func (m *Map[K, V]) Range(f func(node.Node[K, V]) bool)

Range calls f sequentially for each node present in the map. If f returns false, range stops the iteration.

Range does not necessarily correspond to any consistent snapshot of the Map's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently, Range may reflect any mapping for that key from any point during the Range call.

It is safe to modify the map while iterating it. However, the concurrent modification rule apply, i.e. the changes may be not reflected in the subsequently iterated nodes.

func (*Map[K, V]) Set

func (m *Map[K, V]) Set(n node.Node[K, V]) node.Node[K, V]

Set sets the node.Node for the key.

Returns the evicted node or nil if the node was inserted.

func (*Map[K, V]) SetIfAbsent

func (m *Map[K, V]) SetIfAbsent(n node.Node[K, V]) node.Node[K, V]

SetIfAbsent sets the node.Node if the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current node.

func (*Map[K, V]) Size

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

Size returns current size of the map.