Hash Maps

As Hash Sets are to Sets, so we have Hash Maps for normal Maps. The API is very similar to that of Maps, but the performance characteristics resemble those of hash sets.

For a more in depth look at Hash Maps and other data structures, take a look at our eBooks page!

What are Hash Maps good for?

A Hash Map is useful for most problems involving associated data types, and the API will almost always mimic that of Data.Map. Their strengths though are the same as hash sets. Operations are typically faster than normal maps. While still technically logarithmic, for most practical purposes hash map operations are O(1) time.

What are Hash Maps not as good for?

Hash maps do not maintain any ordering of their keys. So operations like getting the maximum or minimum key will need to be O(n), rather than O(log n) for normal maps.

Hash Map Parameters and Constraints

Like normal maps, Hash Maps have two type parameters: a "key" and a "value", where only the key type is constrained. Like hash sets, the Hashable class and Eq class are required of this key type.

How do I create a Hash Map?

Hash maps have the same 3 primary functions as normal maps.

empty :: HashMap k v
singleton :: k -> v -> HashMap k v
fromList :: [(k, v)] -> HashMap k v

How do I get the size of a Hash Map?

As we expect, there is a size function. But for whatever reason, it takes O(n) time.

size :: HashMap k v -> Int

How do I add elements to a Hash Map?

As with maps, we have a simple insert function. This will overwrite an existing value with the same key.

insert :: k -> v -> HashMap k v -> HashMap k v

How do I access Hash Map elements?

Hash maps have the same two principal functions as maps for accessing elements. A lookup function that provides a Maybe value, and a bang operator that unwraps the value but throws an error if it doesn't exist.

lookup :: k -> HashMap k v -> Maybe v
(!) :: HashMap k v -> k -> v

As with sets and hash sets, the member function can efficiently determine if a key already exists.

member :: k -> HashMap k v -> Bool

A hash map can also provide all its key-element pairs as a list.

toList :: HashMap k v -> [(k, v)]

How do I delete elements from a Hash Map?

As we've seen before, using the delete function can remove a particular key and its associated value from your hash map.

delete :: k -> HashMap k v -> HashMap k v

How do I combine Hash Maps?

Hash maps have the save combination functions as normal maps, except again, there is no operator for set difference.

union :: HashMap k v -> HashMap k v -> HashMap k v
unions :: (Foldable f) => [HashMap k v] -> HashMap k v
unionWith :: (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
intersection :: HashMap k v -> HashMap k v -> HashMap k v
difference :: HashMap k v -> HashMap k v -> HashMap k v

Import Notes

You may or may not wish to include the bang operator as an unqualified import, depending on what other structures you are working with.

import Data.HashMap (HashMap, (!))
import qualified Data.HashMap as HM

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! If you want to keep following the order of the series, you can take a look and learn about Arrays next!