Arrays and searching 0/120

Lesson 1 of 9

Hashmaps

Store information by key and use a map to avoid repeated searches.

4,405 words · 20 min read

Part 1 of 10 What exactly is a hashmap?

What exactly is a hashmap?

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.

Why is that useful? Once the counts are stored, we can ask for any word’s count without scanning the document again: the hashmap returns the count saved under that key, or reports that the word has no entry.

Python calls it a dictionary, and C++ provides unordered_map; other languages say Map or HashMap. The syntax differs, but each stores and retrieves information by key.

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.

Operations on keys and values

Start with apple → 3 and pear → 1; each row is an independent operation.
OperationExampleResult
Look up a keyRead apple3
Test membershipDoes plum exist?No
Insert a new keyStore plum → 2Three entries
Update an existing keyStore apple → 4Two entries; apple now has value 4
Remove a keyRemove appleOne entry; only pear → 1 remains

Each key has one entry. Storing "apple" → 4 replaces the earlier count of 3. Different keys can have equal values: "apple" → 3 and "pear" → 3 are separate entries. A membership test looks only at keys, never at values.

What about a count of zero? Removing apple makes its key absent. Setting its value to zero instead leaves the entry "apple" → 0, and a membership test still finds it. An algorithm may need to tell those two situations apart.

Arrays and maps

Do we need a hashmap when we already have arrays? An array gives constant-time access when we know an element’s position: it goes straight to nums[i], while a hashmap first hashes the key and then locates its entry. An array also keeps its slots next to one another in memory, which makes scanning fast, and a hash table needs extra space for its keys and for unused slots.

So the choice depends on the range of possible keys. To count integers from 0 to 100, an array of 101 counts works well. With a few distinct numbers up to 10910^9, though, an array with a slot for every possible key would waste almost all of its space. A map stores entries only for the keys we actually use, and its keys can be words as well as numbers.

Three ways to find information by key
StructureKeysCost to find a keyIteration order
Array: Python list, C++ vectorPositions 0 to n − 1O(1)By position
Hash map: Python dict, C++ unordered_mapAny hashable valueO(1) expected, O(n) worstPython: insertion order; C++: unspecified
Tree map: C++ mapAny comparable valueO(log n)Sorted by key

When is a set enough?

Sometimes we need no value at all. A set stores only distinct keys, so it can answer whether a word appeared. A map also stores information about each word, so it can answer how many times that word appeared.

Difficulty tier:Very Easy

You get an array of integers nums. Return true if some value appears at least twice, and false if every value is distinct.

Constraints

  • 1≤n≤1051 \le n \le 10^5, where nn is the length of nums
  • −109≤nums[i]≤109-10^9 \le \text{nums}[i] \le 10^9

Sample 1 · Input

nums = [1,2,3,1]

Output

true

Sample 2 · Input

nums = [1,2,3,4]

Output

false

Sample 3 · Input

nums = [1,1,1,3,3,4,3,2,4,2]

Output

true

In the first sample, 1 appears at positions 0 and 3. Only the presence of each value matters here, so a set is enough. We scan the array and ask whether the current value is already in the set. If it is, an earlier position held the same value and we can stop. If not, we add it and move on:

Sign up to run
def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False


print(contains_duplicate([1, 2, 3, 1]))
print(contains_duplicate([1, 2, 3, 4]))

Prints True, then False.

Comparing every value with every later value also answers the question, but at the limit n=105n = 10^5 that takes

n(n−1)2=105×99,9992=4,999,950,000 comparisons\frac{n(n-1)}{2} = \frac{10^5 \times 99{,}999}{2} = 4{,}999{,}950{,}000 \text{ comparisons}

The set does one membership test and at most one insertion per number, 2×1052 \times 10^5 operations at most, and the next part explains why each takes expected constant time.