A hash table is a data structure that uses a hash function to turn a key into a location to search for its stored entry. It makes lookups such as “find the position for this instrument ID” fast without scanning every position. A map built on a hash table stores key–value pairs; a set uses hashing for membership without an associated value.
The hash narrows the search. Key equality decides which entry matches. Two distinct keys can lead to the same location, so a correct table must resolve collisions rather than overwrite an unrelated record.
A collision does not merge two instruments
Consider fictional instrument IDs
ALFA and BETA, with positions of 120 and −40 shares. For illustration only, choose four buckets numbered 0–3 and a deliberately weak rule: add the key's ASCII character codes, then take the remainder after division by four.ALFA: , so bucket .BETA: , so bucket .
These are unequal keys with the same destination: a collision. They are not duplicate keys. In a chaining design, bucket 0 holds both entries. To look up
BETA, search that bucket, reject ALFA after comparing keys, and return the value attached to BETA.
Two distinct keys survive one collision. This illustrative chaining table uses ASCII-sum modulo 4; it does not depict Python's actual hash function or dictionary layout. Positions are fictional shares.
Another design, open addressing, keeps entries within the table and follows a probe sequence when the first candidate location is occupied. Both designs need a way to distinguish colliding keys. The number of entries divided by the number of buckets or slots is the load factor; allowing the table to become too crowded makes searches longer.
Using Python's dictionary
CPython implements
dict using a resizable hash table. Use the built-in dictionary for application code; the toy rule below only reproduces the collision arithmetic.def toy_bucket(key: str) -> int:
"""Map ASCII-only teaching keys to four buckets."""
return sum(key.encode("ascii")) % 4
print(toy_bucket("ALFA"), toy_bucket("BETA"))
# 0 0
positions = {"ALFA": 120, "BETA": -40}
print(len(positions), positions["BETA"])
# 2 -40
positions["ALFA"] = 125
print(len(positions), positions["ALFA"])
# 2 125
print(list(positions))
# ['ALFA', 'BETA']The first print demonstrates a collision under the toy hash, not a claim that these strings collide under Python's
hash(). The dictionary keeps two keys. Assigning to ALFA again replaces that key's value; it does not add a third key. positions["GAMMA"] would raise KeyError because the key is absent.Python dictionaries preserve insertion order, a language guarantee since Python 3.7. That order is neither sorted-key order nor bucket order. Updating
ALFA leaves its position in the iteration order unchanged. The dictionary documentation specifies these behaviours.What “constant time” assumes
Lookup and membership are commonly described as average or expected in Big O notation, with the number of stored entries. That description assumes well-distributed hashes, controlled table occupancy, and bounded-cost hashing and key comparisons. With severe collisions, a lookup can require work. These are growth rates, not promises of a fixed latency.
Key size matters too: computing a string hash can require reading its characters, and comparing long keys can be expensive. A cached hash may save repeated hashing work. An insertion can also trigger an resize even when insertion is constant time on average and amortized across many operations. The CPython complexity reference states the assumptions behind its bounds. A position cache with long composite identifiers or custom equality methods needs those costs considered separately.
Hashable is the key requirement
A Python key must be hashable: its hash stays stable over its lifetime, and keys that compare equal must have equal hashes. Equal hashes alone do not imply equal keys. This contract lets the table find an entry again and resolve collisions correctly.
Immutability is useful here, but it is not the complete test. Strings work as keys; lists do not. A tuple works only if all its elements are hashable, so a tuple containing a list is still unsuitable. Some mutable user-defined objects retain identity-based equality and hashing by default; changing fields used by custom equality or hashing while an object is a key can break lookup. See Python's hashable definition and hash contract.
By default, Python salts string and byte hashes per process. They remain stable within that process but may differ across runs. Do not save
hash(instrument_id) as a permanent instrument identifier or assume separate workers will assign the same hash-based shard. Store the actual identifier and use an explicitly specified stable scheme when persistent partitioning is required.For the underlying mechanisms and expected-cost analysis, Hash Tables: Chaining, Open Addressing, and Universal Hashing develops collision resolution and load factor. The public page is a preview; the full lesson requires membership.
Sources
- Python 3.14 glossary: hashable.
- Python 3.14 design FAQ: CPython dictionary implementation.
- Python 3.14 built-in types: dictionaries.
- Python 3.14 time complexity: dictionary operations and amortized costs.
- Python 3.14 data model:
__hash__, equality and hash randomization.
Documentation checked against Python 3.14.10; example executed with Python 3.14.4.