Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.HashMap

Contents

HashMap
Constructors
Metadata
Lookups
Modifications
Conversions
- Safe conversions
- Unsafe conversions

Description

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

Capacity limitation

Access to each key creates a new entry. Note that entries cannot be invalidated due to the internal implementation (called open addressing).

Example

Expand

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

Synopsis

data HashMap s a
new :: (PrimMonad m, Unbox a) => Int -> m (HashMap (PrimState m) a)
build :: (PrimMonad m, Unbox a) => Int -> Vector (Int, a) -> m (HashMap (PrimState m) a)
capacity :: HashMap s a -> Int
size :: PrimMonad m => HashMap (PrimState m) a -> m Int
lookup :: (HasCallStack, Unbox a, PrimMonad m) => HashMap (PrimState m) a -> Int -> m (Maybe a)
member :: (HasCallStack, PrimMonad m) => HashMap (PrimState m) a -> Int -> m Bool
notMember :: (HasCallStack, PrimMonad m) => HashMap (PrimState m) a -> Int -> m Bool
insert :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> Int -> a -> m ()
insertWith :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> a -> a) -> Int -> a -> m ()
exchange :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> Int -> a -> m (Maybe a)
modify :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> a) -> Int -> m ()
modifyM :: (HasCallStack, PrimMonad m, Unbox a) => HashMap (PrimState m) a -> (a -> m a) -> Int -> m ()
clear :: PrimMonad m => HashMap (PrimState m) a -> m ()
keys :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector Int)
elems :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector a)
assocs :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector (Int, a))
unsafeKeys :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector Int)
unsafeElems :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector a)
unsafeAssocs :: (PrimMonad m, Unbox a) => HashMap (PrimState m) a -> m (Vector (Int, a))

HashMap

data HashMap s a Source #

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) Source #

$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) Source #

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

Since: 1.1.0.0

Metadata

capacity :: HashMap s a -> Int Source #

$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 Source #

$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) Source #

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

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

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

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

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

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

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

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

Modifications

Insertions

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

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

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

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

$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}}))$ .

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

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

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

Constraint

The rest capacity must be non-zero. Otherwise it loops forever.

Since: 1.1.0.0

Updates

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

$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 () Source #

$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 () Source #

$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) Source #

$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) Source #

$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)) Source #

$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) Source #

$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) Source #

$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)) Source #

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

Since: 1.1.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result