Python hash table

Python's dict maps keys to values using a hash-table implementation. A hash helps locate candidate entries; equality determines whether a key matches. A hash is not a unique identifier, and Python's built-in hash() is not a persistent ID generator.

The examples use the standard library and were tested with Python 3.12.14. They focus on behavior you can rely on without reproducing version-specific CPython internals.

Use a dictionary for keyed lookup

stock = {'notebook': 4, 'pen': 10}
stock['notebook'] += 2
stock['eraser'] = 3
print(stock['notebook'])
print(stock.get('marker', 0))
print(list(stock))
del stock['pen']
print(stock)

Expected output:

6
0
['notebook', 'pen', 'eraser']
{'notebook': 6, 'eraser': 3}

Dictionaries preserve insertion order. Updating an existing key does not move it. Direct access to a missing key raises KeyError; get lets the caller choose a default. Pick a default that cannot be confused with a valid business value, or test membership explicitly when the distinction matters.

Equal hashes do not imply equal keys

A collision occurs when different keys produce the same hash. This intentionally poor hash function forces that situation. It is a teaching fixture, not a recommended implementation.

from dataclasses import dataclass

@dataclass(frozen=True)
class DemoKey:
    name: str

    def __hash__(self):
        return 1  # Deliberately force collisions for this demonstration.

first = DemoKey('alpha')
second = DemoKey('beta')
lookup = {first: 'first value', second: 'second value'}
print(hash(first) == hash(second))
print(first == second)
print(len(lookup))
print(lookup[DemoKey('alpha')])
print(lookup[DemoKey('beta')])

Expected output:

True
False
2
first value
second value

The dictionary retains both entries because the keys are unequal. The required direction is: equal hashable objects must have equal hashes. The reverse is false. Different Python numeric types can compare equal; for example, 1, 1.0, and True refer to the same dictionary key slot under equality.

values = {1: 'integer'}
values[1.0] = 'float'
values[True] = 'boolean'
print(len(values))
print(values[1])

Expected output:

1
boolean

Hashability depends on stable contents

A key must have a stable hash for its lifetime and equality behavior consistent with that hash. Strings, integers, and suitable tuples work. A tuple is not automatically hashable: all of its elements must also be hashable. Lists and dictionaries are mutable and cannot serve as ordinary dictionary keys.

coordinates = {(2, 3): 'occupied'}
print(coordinates[(2, 3)])
for candidate in ([2, 3], (2, [3])):
    try:
        hash(candidate)
    except TypeError as exc:
        print(type(exc).__name__)

Expected output:

occupied
TypeError
TypeError

For application-defined keys, a frozen dataclass containing immutable hashable fields often expresses the intent clearly. Do not mutate fields that participate in a key's hash or equality after inserting the object. Merely adding __hash__ does not make a mutable identity design correct.

Do not persist built-in hashes as identifiers

String and bytes hashes are randomized between ordinary interpreter runs. A numeric hash can also collide, and implementation details can vary. Store the original key, a database-assigned identifier, or another identity designed for the application's uniqueness requirements.

If the goal is a reproducible content fingerprint, hash explicitly encoded bytes with a documented algorithm. This is separate from dictionary hashing. SHA-256 is useful for checking content equality with an extremely low accidental collision probability, but no fixed-length digest mathematically guarantees unique inputs.

import hashlib

def fingerprint(text):
    return hashlib.sha256(text.encode('utf-8')).hexdigest()

print(fingerprint('abc'))
print(fingerprint('abc') == fingerprint('abc'))
print(fingerprint('abc') == fingerprint('ABC'))

Expected output:

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
True
False

Encoding and normalization are part of the fingerprint contract. Visually similar Unicode strings can have different byte sequences. A plain digest does not authenticate a sender and is not a password-storage scheme.

Understand performance without inventing internals

Dictionary lookup, insertion, and deletion are usually described as average constant-time operations under appropriate hashing assumptions. That is not a guarantee that every call takes the same time. Hashing long keys costs work, resizing costs work, and excessive collisions can degrade performance. Iteration touches the collection and is not constant time.

Let Python manage a normal dictionary's storage. There is no public dict load-factor setting to tune. A classroom implementation using buckets or linked lists can explain collision handling but should not be presented as the exact layout of today's CPython dictionary. For simple counting, the standard library's Counter is often clearer than a custom hash table.

from collections import Counter

print(dict(Counter(['sql', 'python', 'sql'])))

Expected output:

{'sql': 2, 'python': 1}

For a practical use of hashable inputs, see LRU caching in Python. Primary references: dictionary operations, the hashing contract, and hashlib.