Hashing and Frequency Counting

How hashing works

print(hash("abc"))
print(hash(42))
print(hash((1, 2)))
# print(hash([1, 2]))         # TypeError: unhashable type: 'list'

key ──► hash function ──► a number ──► a slot in a table
                                            │
                                            └──► the value

Looking up: hash the key, go straight to the slot. One step, whatever the size.

• Equal objects must produce equal hashes. That is why mutable objects are unhashable: changing one would move it.
• Two different keys may hash to the same slot - a collision - which Python resolves internally.
• Lookup is O(1) on average and O(n) in a pathological worst case that you will not meet in practice.

The core pattern

def has_duplicates_slow(items):
    """O(n^2) - scanning the list for each item."""
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False


def has_duplicates(items):
    """O(n) - a set remembers everything already seen."""
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False


def has_duplicates_shortest(items):
    return len(set(items)) != len(items)


data = list(range(10_000)) + [500]
print(has_duplicates(data), has_duplicates_shortest(data))

The whole technique is: trade memory for time. Store what you have seen, and every later question about it becomes a single lookup.

Two sum

def two_sum_slow(numbers, target):
    """O(n^2)."""
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return i, j
    return None


def two_sum(numbers, target):
    """O(n). For each value, look for the complement we have already passed."""
    seen = {}
    for index, value in enumerate(numbers):
        complement = target - value
        if complement in seen:
            return seen[complement], index
        seen[value] = index
    return None


print(two_sum([2, 7, 11, 15], 9))       # (0, 1)
print(two_sum([3, 2, 4], 6))            # (1, 2)
print(two_sum([1, 2], 100))             # None

The insight is worth stating plainly: instead of searching forward for a partner, record everything behind you so the partner can find you.

Counting

from collections import Counter

text = "the quick brown fox jumps over the lazy dog the end"
words = text.split()

counts = Counter(words)
print(counts.most_common(3))
print(counts["the"])                     # 3
print(counts["missing"])                 # 0, never a KeyError
print(sum(counts.values()))              # the total
print(len(counts))                       # distinct words


# By hand, when you would rather not import
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

from collections import Counter


def is_anagram(first, second):
    """O(n). Sorting would be O(n log n)."""
    normalise = lambda s: Counter(c for c in s.lower() if c.isalnum())
    return normalise(first) == normalise(second)


print(is_anagram("Listen", "Silent"))          # True
print(is_anagram("Dormitory", "Dirty Room"))   # True
print(is_anagram("hello", "world"))            # False


def group_anagrams(words):
    """Group words that are anagrams of each other."""
    groups = {}
    for word in words:
        key = tuple(sorted(word.lower()))      # a hashable signature
        groups.setdefault(key, []).append(word)
    return list(groups.values())


print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

from collections import Counter


def first_non_repeating(text):
    """The first character appearing exactly once. O(n)."""
    counts = Counter(text)
    for character in text:                      # dicts keep insertion order
        if counts[character] == 1:
            return character
    return None


print(first_non_repeating("swiss"))            # w
print(first_non_repeating("aabb"))             # None


def most_frequent(items, n=1):
    return Counter(items).most_common(n)


print(most_frequent([1, 3, 3, 2, 3, 1], 2))    # [(3, 3), (1, 2)]

Grouping

from collections import defaultdict

records = [
    {"name": "Meera", "dept": "eng", "salary": 90},
    {"name": "Arun", "dept": "design", "salary": 75},
    {"name": "Sara", "dept": "eng", "salary": 82},
    {"name": "Ravi", "dept": "design", "salary": 88},
]

by_dept = defaultdict(list)
for record in records:
    by_dept[record["dept"]].append(record["name"])
print(dict(by_dept))

totals = defaultdict(int)
counts = defaultdict(int)
for record in records:
    totals[record["dept"]] += record["salary"]
    counts[record["dept"]] += 1

for dept in sorted(totals):
    print(f"{dept:<10}{totals[dept]:>6}  average {totals[dept] / counts[dept]:.1f}")

from collections import defaultdict


def build_index(documents):
    """Map each word to the documents containing it."""
    index = defaultdict(set)
    for doc_id, text in documents.items():
        for word in text.lower().split():
            index[word.strip(".,!?")].add(doc_id)
    return index


documents = {
    1: "python is readable",
    2: "python is widely used",
    3: "readable code matters",
}

index = build_index(documents)
print(index["python"])                                   # {1, 2}
print(index["python"] & index["readable"])               # {1} - both words
print(index["python"] | index["matters"])                # {1, 2, 3} - either

An inverted index is how search works. Building it costs one pass; querying it costs a set operation, whatever the size of the corpus.

Caching and memoisation

from functools import cache


@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)


print(fib(100))
print(fib.cache_info())


# By hand, so the mechanism is visible
def fib_manual(n, memo=None):
    memo = {} if memo is None else memo
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_manual(n - 1, memo) + fib_manual(n - 2, memo)
    return memo[n]


print(fib_manual(100))

Sets for relationships

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a & b)          # {3, 4}     in both
print(a | b)          # everything
print(a - b)          # {1, 2}     only in a
print(a ^ b)          # {1, 2, 5, 6}  in exactly one


def find_missing(complete, present):
    """What is expected but absent."""
    return sorted(set(complete) - set(present))


print(find_missing(range(1, 11), [1, 2, 4, 5, 7, 8, 10]))     # [3, 6, 9]


def intersection_of_all(lists):
    return set.intersection(*(set(items) for items in lists))


print(intersection_of_all([[1, 2, 3], [2, 3, 4], [3, 2, 9]]))     # {2, 3}

Deduplicating

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

print(list(set(items)))                    # fast, order lost
print(list(dict.fromkeys(items)))          # fast, first occurrence order kept


def unique_by(records, key):
    """Keep the first record for each key value."""
    seen = set()
    result = []
    for record in records:
        value = record[key]
        if value not in seen:
            seen.add(value)
            result.append(record)
    return result


records = [
    {"id": 1, "email": "a@x.com"},
    {"id": 2, "email": "b@x.com"},
    {"id": 3, "email": "a@x.com"},
]
print(unique_by(records, "email"))

Worked problems

The longest run without repeats

def longest_unique_substring(text):
    """O(n) with a dictionary of last seen positions."""
    last_seen = {}
    start = best = best_start = 0

    for index, character in enumerate(text):
        if character in last_seen and last_seen[character] >= start:
            start = last_seen[character] + 1
        last_seen[character] = index
        if index - start + 1 > best:
            best = index - start + 1
            best_start = start

    return text[best_start:best_start + best]


print(longest_unique_substring("abcabcbb"))      # abc
print(longest_unique_substring("pwwkew"))        # wke
print(longest_unique_substring("bbbbb"))         # b

Subarray summing to a target

def subarray_with_sum(numbers, target):
    """O(n) using running totals stored in a dictionary."""
    seen = {0: -1}                       # a running total of 0 before we start
    running = 0

    for index, value in enumerate(numbers):
        running += value
        if running - target in seen:
            return seen[running - target] + 1, index
        seen.setdefault(running, index)

    return None


print(subarray_with_sum([1, 4, 20, 3, 10, 5], 33))     # (2, 4)
print(subarray_with_sum([1, 2, 3], 100))                # None

Same idea as two sum: record every running total, so the question "was there an earlier point with total x?" becomes a lookup.

Checking for a valid arrangement

from collections import Counter


def can_rearrange_to_palindrome(text):
    """At most one character may appear an odd number of times."""
    counts = Counter(c for c in text.lower() if c.isalnum())
    odd = sum(1 for count in counts.values() if count % 2)
    return odd <= 1


for text in ["civic", "ivicc", "hello", "aabbccd"]:
    print(f"{text:<10}{can_rearrange_to_palindrome(text)}")

The majority element

from collections import Counter


def majority(items):
    """A value appearing more than half the time, or None."""
    if not items:
        return None
    value, count = Counter(items).most_common(1)[0]
    return value if count > len(items) // 2 else None


print(majority([3, 3, 4, 2, 3, 3, 3]))     # 3
print(majority([1, 2, 3]))                  # None


def majority_no_memory(items):
    """Boyer-Moore voting: O(n) time, O(1) space."""
    candidate, count = None, 0
    for item in items:
        if count == 0:
            candidate = item
        count += 1 if item == candidate else -1
    return candidate if items.count(candidate) > len(items) // 2 else None


print(majority_no_memory([3, 3, 4, 2, 3, 3, 3]))

When hashing does not help

Common mistakes

• Using a list where a set was needed, turning O(n) into O(n²).
• Trying to use a list or dict as a key; convert to a tuple or a frozenset.
• Building the set inside the loop that searches it.
• Assuming a set preserves order.
• Using Counter and expecting a KeyError for an absent key; it returns 0.
• Caching a function whose result depends on outside state.

Best practices

• Whenever you write a nested loop over one collection, ask whether a set or dict removes the inner one.
• Use Counter for counting and defaultdict for grouping.
• Build lookups once, outside the loop.
• Use dict.fromkeys when deduplication must preserve order.
• Store a hashable signature - a sorted tuple, a frozenset - when the item itself cannot be a key.

Practice

1. Find the first repeated element in a list in one pass.
2. Group a list of words by their sorted letters and report the largest group.
3. Find two numbers summing to a target, then extend it to three numbers.
4. Build an inverted index over five documents and answer a two word query.
5. Find the longest substring with at most two distinct characters.

Conclusion

A hash table converts "search for it" into "look it up". Whenever you find yourself scanning a collection inside a loop over the same collection, the answer is almost always a set or a dictionary and one extra pass.