AtCoder.Extra.HashMap

A dense, fast Int hash map with a fixed-sized capacity of \(n\). Most operations are performed in \(O(1)\) time, but in average.

NOTE: The entries (key - value pairs) cannot be invalidated due to the internal implementation (called open addressing).

Example

Create a HashMap with capacity \(10\):

>>> import AtCoder.Extra.HashMap qualified as HM
>>> hm <- HM.new @_ @Int 10

insert, lookup and other functions are available in \(O(1)\) averaged time:

>>> HM.insert hm 0 100
>>> HM.insert hm 10 101
>>> HM.size hm
2

>>> HM.lookup hm 0
Just 100

>>> HM.lookup hm 10
Just 101

Since: 1.1.0.0

HashMap

data HashMap s a

A dense, fast Int hash map with a fixed-sized capacity of \(n\).

Since: 1.1.0.0

Constructors

new :: (PrimMonad m, Unbox a) => Int -> m (HashMap (PrimState m) a)

\(O(n)\) Creates a HashMap of capacity \(n\).

Since: 1.1.0.0

build :: (PrimMonad m, Unbox a) => Int -> Vector (Int, a) -> m (HashMap (PrimState m) a)

\(O(n)\) Creates a HashMap of capacity \(n\) with initial entries.

Since: 1.1.0.0

Metadata

capacity :: HashMap s a -> Int

\(O(1)\) Returns the maximum number of elements the hash map can store.

Since: 1.1.0.0

size :: PrimMonad m => HashMap (PrimState m) a -> m Int

\(O(1)\) Returns the number of elements in the hash map.

Since: 1.1.0.0

Lookups

lookup :: (HasCallStack, Unbox a, PrimMonad m) => HashMap (PrimState m) a -> Int -> m (Maybe a)

\(O(1)\) Return the value to which the specified key is mapped, or Nothing if this map contains no mapping for the key.

Since: 1.1.0.0

member :: (HasCallStack, PrimMonad m) => HashMap (PrimState m) a -> Int -> m Bool

\(O(1)\) Checks whether the hash map contains the element.

Since: 1.1.0.0

notMember :: (HasCallStack, PrimMonad m) => HashMap (PrimState m) a -> Int -> m Bool

\(O(1)\) Checks whether the hash map does not contain the element.

Since: 1.1.0.0

Modifications

Insertions

insert :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> Int -> a -> m ()

\(O(1)\) Inserts a \((k, v)\) pair.

Since: 1.1.0.0

insertWith :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> a -> a) -> Int -> a -> m ()

\(O(1)\) Inserts a \((k, v)\) pair. If the key exists, the function will insert the pair \((k, f(v_{\mathrm{new}}, v_{\mathrm{old}}))\).

Since: 1.1.0.0

exchange :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> Int -> a -> m (Maybe a)

\(O(1)\) Inserts a \((k, v)\) pair and returns the old value, or Nothing if no such entry exists.

Since: 1.1.0.0

Updates

modify :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> a) -> Int -> m ()

\(O(1)\) Modifies the element at the given key. Does nothing if no such entry exists.

Since: 1.1.0.0

modifyM :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> m a) -> Int -> m ()

\(O(1)\) Modifies the element at the given key. Does nothing if no such entry exists.

Since: 1.1.0.0

Reset

clear :: PrimMonad m => HashMap (PrimState m) a -> m ()

\(O(n)\) Clears all the elements.

Since: 1.1.0.0

Conversions

Safe conversions

keys :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector Int)

\(O(n)\) Enumerates the keys in the hash map.

Since: 1.1.0.0

elems :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector a)

\(O(n)\) Enumerates the elements (values) in the hash map.

Since: 1.1.0.0

assocs :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector (Int, a))

\(O(n)\) Enumerates the key-value pairs in the hash map.

Since: 1.1.0.0

Unsafe conversions

unsafeKeys :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector Int)

\(O(n)\) Enumerates the keys in the hash map.

Since: 1.1.0.0

unsafeElems :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector a)

\(O(n)\) Enumerates the elements (values) in the hash map.

Since: 1.1.0.0

unsafeAssocs :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector (Int, a))

\(O(n)\) Enumerates the key-value pairs in the hash map.

Since: 1.1.0.0