Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 225 ยท Hashing

Hash Functions

Learn what makes a good hash function, build integer and string hashes, and understand Python's hash(), hashability, __hash__ and __eq__, and why lists can't be dict keys.

A hash table is only as good as its hash function: the rule that turns a key (a number, a string, a tuple, your own object) into a bucket number. A good function spreads keys evenly, so collisions stay rare and lookups stay O(1). A bad one piles keys into a few buckets and quietly turns your fast table into a slow list.

This lesson covers what a hash function must do, how to build simple ones for integers and strings, and then the part that matters most day to day in Python: what hash() really does, why some objects can be dictionary keys and others cannot, and how to make your own classes safe to use as keys.

What a hash function must do

A hash function h(key) maps a key to an integer. For use in a hash table it needs these properties:

  1. Deterministic. The same key must give the same hash every time (within a run of the program). Otherwise you could never find what you stored.
  2. Equal keys, equal hashes. If a == b then h(a) == h(b). The reverse is not required: different keys may share a hash (that is a collision).
  3. Uniform. Hash values should be spread evenly over the possible range, so buckets fill evenly.
  4. Fast. Hashing happens on every lookup, so it should cost about as much as reading the key.
  5. Sensitive to small changes (the "avalanche" idea). Keys that look alike, like "user1" and "user2", should not land in neighboring or identical buckets.
TEXT
key  --hash function-->  big integer  --% m-->  bucket index   (made-up numbers)
"cat"                     1_947_261_118          5
"act"                     1_947_258_870          2

The two steps are separate: the function produces a large integer, and the table reduces it to a bucket with % m (or a bit mask when m is a power of two). Keep that split in mind, because "hashing" in Python usually refers to the first step only.

Hashing integers

Integers are easy: the identity hash h(k) = k is already deterministic and, for typical keys, spread well enough. Trouble starts when the reduction step hurts the spread. If every key is a multiple of 10 and m = 10, every key lands in bucket 0.

Two classic fixes:

  • Division method: k % m with m a prime that is not close to a power of two.
  • Multiplication method: multiply by a constant, keep the fractional part, and scale to m. The constant 0.6180339887... (the golden ratio minus 1) works well because it scrambles patterns.
Python Division versus multiplication method

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With m = 10 every key divisible by 10 falls in bucket 0, so the table degenerates into one long chain (1 bucket used for 8 keys). The multiplication method puts the same 8 keys in 8 different buckets. Using a prime m (for example 11) would also fix this example, which is why textbooks recommend prime sizes with the division method.

Hashing strings

A string is a sequence of characters, so the hash must depend on every character and its position. Adding up the character codes ignores order, so "listen" and "silent" would collide. The standard solution is a polynomial hash: treat the string like a number written in some base B.

TEXT
h("abc") = ord('a')ยทBยฒ + ord('b')ยทB + ord('c')     (then reduce modulo something)

You compute it with Horner's rule, one multiply and add per character:

TEXT
h = 0
for ch in s:
    h = h * B + ord(ch)

This is the same idea that powers Rabin-Karp string search. Common bases are small primes such as 31 or 33 (the famous "djb2" hash starts at 5381 and uses 33).

Python Bad sum hash versus polynomial hash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All the words above are anagram groups, which is the worst case for the sum hash: words in the same group get the same sum, so they always collide. With 20 words and 16 buckets, the sum hash uses only 2 buckets with a longest chain of 11, while the polynomial hash uses 7 buckets with a longest chain of 4.

Note: Python integers never overflow, so polynomial_hash grows without bound for long strings. Real implementations in C or Java keep the value in a fixed number of bits (it "wraps around"), or reduce % p with a large prime p as you do in Rabin-Karp.

Hashing tuples and combining values

To hash a pair (x, y) you combine the hashes of the parts, and again order must matter: (1, 2) and (2, 1) are different keys. The usual recipe is the same polynomial idea, applied to the component hashes:

TEXT
h((x, y)) = h(x) * 31 + h(y)

Python's built-in tuple hash does a stronger version of this, so you rarely write it by hand. What you do need to know is the rule behind it: a container is hashable only if everything inside it is hashable.

Python's hash() and hashability

hash(obj) calls the object's __hash__ method and returns an integer. Dictionaries and sets call it for you on every key or element.

Python What hash() does for built-in types

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three things stand out:

  • Small integers hash to themselves, except -1, which becomes -2 (CPython uses -1 internally to signal an error).
  • 1, 1.0 and True are equal, so they must hash equal, and a dict treats them as the same key.
  • Lists, dicts and sets are unhashable. They can change after being used as a key, which would change their hash and strand them in the wrong bucket. Immutable types (int, float, str, bytes, bool, frozenset, and tuples of those) are hashable. When you need a "list key", use a tuple, or a frozenset for an unordered group.

Watch out: do not print or store hash("some string") and expect the same number tomorrow. Python randomizes string and bytes hashes every time the interpreter starts (a defense against attackers who craft colliding keys). Within one run the hash is stable, which is all a dict needs, but across runs it changes. This is also why iterating a set of strings can give a different order from run to run. If you need a number that stays the same forever (file checksums, sharding across servers), use hashlib or your own function instead.

Making your own classes hashable

By default, a class instance hashes by identity: two separate objects are never equal, even with identical contents. To use your own objects as dictionary keys by value, define __eq__ and __hash__ together and follow the contract:

If a == b, then hash(a) == hash(b).

The easy way to keep that promise is to build the hash from exactly the same fields that __eq__ compares, and to hash them as one tuple.

Python A hashable Point class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without __hash__, defining only __eq__ makes Python set __hash__ to None, so the class becomes unhashable. That is deliberate: it stops you from creating objects that are equal but hash differently.

The mutable key trap

If a key's fields change after it was inserted, its hash changes, but the entry still sits in the bucket for the old hash. The key is then lost: in returns False even though the object is visibly in the dictionary.

Python Mutating a key breaks the dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rule: keys must be immutable, or at least never modified while they are in a table. That is the real reason Python forbids list keys.

Hashing for stability: hashlib

When you need a hash that is identical on every machine and run (fingerprints, consistent bucketing, Bloom filters), use a cryptographic hash from hashlib. It is slower than hash(), but the output is fixed.

Python Stable hashes with hashlib

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cryptographic hashes are designed so that you cannot easily find two inputs with the same output, and tiny input changes flip about half the output bits (strong avalanche). You do not need that strength for a normal dictionary, and hash() is far faster, but you do need the stability whenever hashes leave the process.

Common mistakes

  • Forgetting that __eq__ and __hash__ travel together. Overriding one without the other causes unhashable classes or, worse, inconsistent behavior.
  • Using mutable fields in __hash__ and then changing them while the object is a key.
  • Relying on hash() of a string across runs (printing it, saving it, using it to decide which server owns a key).
  • Assuming equal hash means equal key. Hash equality is a necessary condition only; the table still compares keys with ==.
  • Hashing only part of what __eq__ compares is fine (just more collisions); hashing more than __eq__ compares breaks the contract.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement about hash functions must always be true?

    Equal keys must hash equal, or a lookup would go to a different bucket than the insert. Different keys sharing a hash is allowed (a collision).
  2. 2. Why is summing character codes a poor string hash?

    The sum is the same for any rearrangement of the same letters, so every anagram of a word lands in the same bucket. A polynomial hash makes the position matter.
  3. 3. Why can't a list be used as a dictionary key in Python?

    A key's hash must stay the same while it is stored. A list can change, so Python makes it unhashable. Use a tuple instead.
  4. 4. What does len({1, 1.0, True}) print?

    1, 1.0 and True are equal and hash equal, so the set keeps just one of them.
  5. 5. When is it appropriate to use hashlib instead of hash()?

    hash() of strings is randomized per run. hashlib gives fixed, reproducible output, which you need for saved fingerprints, sharding or Bloom filters.

Summary

  • A hash function maps a key to a big integer; the table reduces it to a bucket with % m. It must be deterministic, give equal hashes for equal keys, spread keys evenly, and be fast.
  • Integers: division by a prime, or the multiplication method, avoids patterns. Strings: use a polynomial hash with Horner's rule so order matters.
  • Python's hash() powers dicts and sets. Immutable built-ins are hashable; lists, dicts and sets are not. 1, 1.0 and True collapse into one key.
  • Custom classes need __eq__ and __hash__ built from the same immutable fields; @dataclass(frozen=True) does it for you.
  • String hashes are randomized per run, so never persist or print them; use hashlib for stable hashes.

Next: Dictionaries and Sets in Practice