Sets, dictionaries, and anti-hash tests¶

~25 min · prerequisite: Sorting and tuples

What you will be able to do¶

Use a set to store unique values, and a dictionary to count or look up values by key.
Choose keys that are hashable, and use collections.Counter for frequency counts.
Spread out crafted integer keys with a mixing step, which protects a hash-based solution against an anti-hash test.

The idea¶

A set holds unique values and answers "is this value present?" quickly, whatever its size. A dictionary, written dict, maps each key to a value, and it also finds keys quickly. Both are built on a hash table. Python computes a hash, an integer, for each key and uses it to choose where to look. A key must be hashable, meaning its hash never changes while it is stored. Numbers, strings, and tuples of those are hashable. Lists and sets are not, because you can change them.

A dictionary keeps its keys in insertion order, a guarantee since Python 3.7. A set makes no promise about order. Counter from the collections module is a dictionary for counting, and its most_common(k) method returns the k most frequent items.

Hashing has a weak point. In CPython, the usual implementation, a small non-negative integer hashes to itself. The table uses the low bits of the hash to choose a starting place. If many keys share those low bits, for example every key is a multiple of 2**20, they all start in the same place, and lookups may have to probe through occupied places. Some contest tests are built this way on purpose. This is an anti-hash test.

A common shortcut is to XOR every key with one random number chosen at startup. It does not help here, because XOR keeps the pattern of the low bits. A better defence is a mixing function, a chain of multiplications and shifts that makes every output bit depend on every input bit. The Try it section uses a finalizer from the SplitMix64 generator. It costs some time per key, so use it only when tests may be built against hash tables.

Worked example¶

from collections import Counter

words = ["red", "blue", "red", "green", "red", "blue"]
seen = set()
unique = []
for w in words:
    if w not in seen:
        seen.add(w)
        unique.append(w)

print(unique)
print(Counter(words).most_common(2))

The output is:

['red', 'blue', 'green']
[('red', 3), ('blue', 2)]

Line by line, this is what Python does:

seen is a set, and unique is a list that keeps first occurrences in order.
w not in seen is a fast membership test. When the word is new, it is added to both the set and the list.
Counter(words) counts every word in one step, and most_common(2) returns the two highest counts.

Try it¶

The block applies the mixing step to keys that share their low bits.

import random

MASK = (1 << 64) - 1
SEED = random.getrandbits(64)

def mix(x):
    z = (x + SEED) & MASK
    z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & MASK
    return z ^ (z >> 31)

keys = [k << 20 for k in range(1 << 12)]
low = (1 << 20) - 1
assert len({x & low for x in keys}) == 1
assert len({mix(x) & low for x in keys}) > 4000
assert len({mix(x) for x in range(100000)}) == 100000

Common mistakes¶

Using a list as a key. Running hash([1, 2]) gives:
```
TypeError: unhashable type: 'list'
```
A dictionary fails the same way when a list is its key. Use a tuple such as (1, 2).
Reading a missing key. With counts = {}, the line counts["a"] += 1 gives:
```
KeyError: 'a'
```
Write counts[w] = counts.get(w, 0) + 1, or use a Counter.
Using get without a default. The method d.get(k) returns None when the key is missing. Running d.get("k") + 1 gives:
```
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'
```
Write d.get("k", 0) instead.

Practice¶

Write the function named in each problem. The samples are checks.

First occurrences (easy). Write dedupe(values). Remove repeats, keeping first positions. Sample: dedupe([3, 1, 3, 2, 1]) returns [3, 1, 2].
Top letter (easy). Write top_letter(text). Return the most frequent letter. On a tie, return the one that appears first. Samples: top_letter("banana") returns "a", and top_letter("abcabc") returns "a".
Two-sum check (medium). Write has_pair(values, target). Return "YES" if two different positions hold values that add up to target, else "NO". Samples: has_pair([2, 7, 11, 15], 9) returns "YES", has_pair([2, 7, 11, 15], 100) returns "NO", and has_pair([4, 4], 8) returns "YES".
Unique names (medium). Write register(names). A new name is issued unchanged. A repeated name is issued as name + str(k) for the smallest k >= 1 that has not been issued. Return the issued names. Sample: register(["bob", "bob", "bob1", "bob"]) returns ["bob", "bob1", "bob11", "bob2"].
Subarrays with a given sum (stretch). Write count_sum_k(values, k). Count the non-empty contiguous parts whose sum is k. Samples: count_sum_k([1, 1, 1], 2) returns 2, and count_sum_k([1, 2, 3], 3) returns 2.

Solution

```python def dedupe(values): return list(dict.fromkeys(values))

assert dedupe([3, 1, 3, 2, 1]) == [3, 1, 2] ```

```python def top_letter(text): counts = {} for ch in text: counts[ch] = counts.get(ch, 0) + 1 return max(counts, key=counts.get)

assert top_letter("banana") == "a" assert top_letter("abcabc") == "a" ```

The dictionary keeps letters in first-appearance order, and max returns the first largest item.

```python def has_pair(values, target): seen = set() for x in values: if target - x in seen: return "YES" seen.add(x) return "NO"

assert has_pair([2, 7, 11, 15], 9) == "YES" assert has_pair([2, 7, 11, 15], 100) == "NO" assert has_pair([4, 4], 8) == "YES" ```

```python def register(names): issued = set() out = [] for name in names: chosen = name k = 1 while chosen in issued: chosen = name + str(k) k += 1 issued.add(chosen) out.append(chosen) return out

assert register(["bob", "bob", "bob1", "bob"]) == ["bob", "bob1", "bob11", "bob2"] ```

```python def count_sum_k(values, k): counts = {0: 1} running = 0 total = 0 for x in values: running += x total += counts.get(running - k, 0) counts[running] = counts.get(running, 0) + 1 return total

assert count_sum_k([1, 1, 1], 2) == 2 assert count_sum_k([1, 2, 3], 3) == 2 ```

A part has sum k when an earlier prefix sum equals the current prefix sum minus k, so the dictionary counts earlier prefix sums.

Recap¶

A set stores unique values and answers membership quickly. A dictionary maps keys to values. Keys must be hashable, so use tuples rather than lists.
Use counts.get(k, 0) or Counter to count without a KeyError.
Crafted integer keys can share low hash bits. A mixing function spreads them out, and a plain XOR does not.