Data structures and algorithms 0/7

DSA, Arrays and searching

What is a hash map?

Also called hashmap, dictionary, unordered_map

199 words · 1 min read

A hashmap stores pairs of keys and values. A key identifies an entry, and its value is the information stored there. For example, "apple" → 3 can record that the word apple appears three times in a document: apple is the key, and 3 is its value.

A map is the set of operations on keys and values. A hash table is one way to implement those operations; other implementations use trees, which keep the keys sorted. This lesson builds the hash-table implementation.

How does hashing work?

So how does a hash map find a key without searching every stored entry? It uses a hash function hh that computes an integer from the key, and then reduces that integer to one of the mm buckets of an internal array:

bucket(k)=h(k) mod m\text{bucket}(k) = h(k) \bmod m

Let’s use a small table. It has m=8m = 8 buckets, numbered 0 through 7, and an integer key is its own hash, so key kk goes into bucket k % 8. Key 12 goes to bucket 4, and key 7 to bucket 7. The stored value plays no part in choosing the bucket.

Any integer can be a key, but the table has only 8 buckets, so different keys must sometimes share one.
Hashmaps Store information by key and use a map to avoid repeated searches. Read the full lesson