Hash Values
Python's built-in hash() function returns an object's hash value. Hash tables rely on hash values to index elements:
object ──▶ hash(object) ──▶ hash value ──▶ slot index in hash table
For a hash table to work correctly, key objects must satisfy two conditions:
- The hash value must not change during the object's lifetime.
- Objects that compare equal must have the same hash value.
Objects satisfying these conditions are called hashable. Only hashable objects can be used as keys in a hash table. This is why dict, set, and other hash-table-backed containers require hashable keys.
Among Python's built-in types, all immutable objects are hashable; mutable objects like list and dict are not:
>>> hash([])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Unhashable objects cannot be used as dict keys:
>>> {[]: 'list is not hashable'}
TypeError: unhashable type: 'list'
>>> {{}: 'dict is not hashable either'}
TypeError: unhashable type: 'dict'
User-defined objects are hashable by default — their hash value is derived from their memory address, and any two distinct objects are considered unequal:
>>> class A:
... pass
...
>>> a = A()
>>> b = A()
>>> hash(a), hash(b)
(-9223372036573452351, -9223372036573452365)
>>> a == b
False
How Is the Hash Value Computed?
The answer is a hash function. As we know from the object model, object behavior is determined by the type object. Hash value computation is one such behavior — it's stored in the tp_hash function pointer of the type object. The built-in hash() function delegates to tp_hash to compute and return the value.
For str, the hash function is unicode_hash in Objects/unicodeobject.c:
PyTypeObject PyUnicode_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"str", /* tp_name */
sizeof(PyUnicodeObject), /* tp_size */
// ...
(hashfunc) unicode_hash, /* tp_hash */
// ...
};
For user-defined objects, you can override the default hash behavior by implementing __hash__ and __eq__. For example, if a Tag instance is uniquely identified by its value field:
class Tag:
def __init__(self, value, title):
self.value = value
self.title = title
def __hash__(self):
return hash(self.value)
def __eq__(self, other):
return self.value == other.value
Since hash values are used frequently and never change during an object's lifetime, they are cached inside the object to avoid recomputation. For str, the internal hash field stores the cached value.
A good hash function must distribute hash values uniformly across the hash space. The more similar two values are, the more different their hash values should be.
Hash Collisions
Two different objects can have the same hash value. Also, the number of slots in a hash table is far smaller than the full hash value space. This means multiple keys can map to the same slot — a hash collision.
hash(key1) % table_size = 3 ┐
├─▶ both map to slot 3 → collision!
hash(key3) % table_size = 3 ┘
There are two common strategies to resolve hash collisions:
- Separate chaining
- Open addressing
Separate Chaining
Each slot maintains a linked list. All keys that hash to the same slot are stored in the corresponding list:
Hash Index Linked Lists
┌───┐
│ 0 │──▶ NULL
├───┤
│ 1 │──▶ [key2] ──▶ NULL
├───┤
│ 2 │──▶ NULL
├───┤
│ 3 │──▶ [key1] ──▶ [key3] ──▶ NULL ← both hash to slot 3
├───┤
│ 4 │──▶ NULL
└───┘
Open Addressing (Python's Approach)
Python uses open addressing — data is stored directly in the hash slots. If a slot is occupied, try another one.
Insert key3 (hashes to slot 3, already occupied by key1):
┌───┬───────┐
│ 0 │ │
├───┼───────┤
│ 1 │ │
├───┼───────┤
│ 2 │ │
├───┼───────┤
│ 3 │ key1 │ ← slot 3 occupied
├───┼───────┤
│ 4 │ │
├───┼───────┤
│ 5 │ key3 │ ← probe finds slot 5, insert here ✅
└───┴───────┘
The i-th probe tries slot (base + dᵢ) % size. The probing strategy depends on the function dᵢ.
Linear probing — dᵢ = 2 * i:
Probe sequence: slot 3 → 5 → 7 → 9 → ...
Quadratic probing — dᵢ = i²:
Probe sequence: slot 3 → 4 → 7 → 12 → ...
Both methods have a weakness: a fixed probe sequence increases collision probability when multiple keys share the same starting slot.
key, key2, key3 all hash to slot 1:
Fixed probe sequence: 1 → 3 → 7 → 13 → ...
All three follow the SAME path → high collision rate ❌
Python's Perturbation-Based Probing
Python improves on this by incorporating the object's hash value into the probe sequence, making each key's probe path unique:
key (hash=0b...0101): probe path → 1 → 6 → 3 → ...
key2 (hash=0b...1010): probe path → 1 → 4 → 9 → ...
key3 (hash=0b...1111): probe path → 1 → 8 → 2 → ...
The implementation is in lookdict inside Objects/dictobject.c:
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;
top:
dk = mp->ma_keys;
ep0 = DK_ENTRIES(dk);
mask = DK_MASK(dk);
perturb = hash;
i = (size_t)hash & mask;
for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);
// key comparison omitted
// compute next slot
// perturb incorporates the hash value → unique probe sequence per key
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}
Hash Attacks
Before Python 3.3, hash values were computed solely from the object itself — no randomness involved. This meant the same object always produced the same hash value across any two interpreter instances:
# Python 2, process 1 (pid=2878)
>>> hash('fasion')
3629822619130952182
# Python 2, process 2 (pid=2915)
>>> hash('fasion')
3629822619130952182 # identical ← vulnerability
An attacker could craft a large number of keys that all hash to the same value, then POST them as JSON to a Python 2 web server. The server would build a dict from this data — and every single key would collide. Hash table performance degrades from O(1) to O(N), effectively taking the server down. This is a hash flooding attack.
The Fix: Hash Salting (Python 3.3+)
The solution is simple — add a salt:
- When the interpreter starts, generate a random number as the salt.
- The hash function incorporates both the object itself and the random salt.
Since the attacker cannot know the interpreter's internal random salt, they cannot pre-compute colliding keys.
# Python 3.7, process 1
>>> hash('fasion')
7411353060704220518
# Python 3.7, process 2
>>> hash('fasion')
1784735826115825426 # different every time ✅
Python's hash algorithm is implemented in Python/pyhash.c.
The Delete Operation
Now let's look at how dict handles deletion. Consider this scenario:
State after inserting key1, key2, key3:
Hash Index Entry Storage
┌───┬──────┐ ┌───┬──────┐
│ 0 │ │ │ 0 │ key1 │
├───┼──────┤ ├───┼──────┤
│ 1 │ 1 │──▶ 1 │ key2 │
├───┼──────┤ ├───┼──────┤
│ 2 │ │ │ 2 │ │
├───┼──────┤ ├───┼──────┤
│ 3 │ │ │ 3 │ │
├───┼──────┤ └───┴──────┘
│ 4 │ │
├───┼──────┤
│ 5 │ 0 │──▶ key1 (slot 5, entry 0)
├───┼──────┤
│ 6 │ 2 │──▶ key3 (slot 6, entry 2) ← key3 collided at slot 1, moved to slot 6
└───┴──────┘
If we delete key2 by simply marking slot 1 as EMPTY:
┌───┬──────┐
│ 1 │EMPTY │ ← slot 1 cleared
├───┼──────┤
│ 6 │ 2 │ key3 hashes to slot 1, probes... finds EMPTY → thinks key3 doesn't exist ❌
└───┴──────┘
This breaks the probe chain — key3 becomes unreachable!
The Fix: DUMMY Tombstone
Instead of marking the slot as EMPTY, Python marks it as DUMMY — a tombstone that signals "keep probing, don't stop here":
┌───┬──────┐
│ 1 │DUMMY │ ← tombstone, probe chain intact
├───┼──────┤
│ 6 │ 2 │ key3 hashes to slot 1, sees DUMMY → continues probing → finds slot 6 ✅
└───┴──────┘
Slot state constants are defined in Objects/dict-common.h:
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) /* Used internally */
#define DKIX_ERROR (-3)
Reusing Deleted Entry Storage
Python doesn't bother reusing deleted entry storage slots. When a new key is inserted, it simply uses the next available entry:
Insert key4 after deleting key2:
Entry storage:
┌───┬──────┐
│ 0 │ key1 │
├───┼──────┤
│ 1 │ key2 │ ← deleted (wasted, ignored)
├───┼──────┤
│ 2 │ key3 │
├───┼──────┤
│ 3 │ key4 │ ← new entry goes here ✅
└───┴──────┘
Yes, some storage slots may be wasted — but that's acceptable.
Note: The above describes the entries array — the compact storage that
holds actual key-value pairs. There is a separate indices array (the hash
table index) where deleted slots are markedDUMMYand are reused during
insertion, preventing probe chains from growing indefinitely. These are two
distinct structures working together in Python's dict implementation
(introduced in Python 3.6).
Resize and Rebuild
When entry storage is exhausted, Python performs a resize: allocates a brand-new hash table and migrates all live entries into it.
Before resize: After resize:
┌───┬──────┐ ┌───┬──────┐
│ 0 │ key1 │ │ 0 │ key1 │
├───┼──────┤ ──rebuild──▶ ├───┼──────┤
│ 1 │ key2 │(deleted) │ 1 │ key3 │ ← only live entries copied
├───┼──────┤ ├───┼──────┤
│ 2 │ key3 │ │ 2 │ key4 │
├───┼──────┤ ├───┼──────┤
│ 3 │ key4 │ │ │ │ ← fresh empty slots
└───┴──────┘ └───┴──────┘
The new table size is determined by the current number of live elements, so a resize can result in expansion, shrinkage, or no change in capacity. Either way, after the rebuild, fresh entry slots are available again.
Top comments (6)
Why is that? Why does it not reuse them? After all if they are in the chain of elements which have the same hash, it would make sense to not make this chain any longer.
Great question, Petr! This touches on a subtle but important design decision.
The short answer is: reusing a deleted slot is actually unsafe without extra bookkeeping.
Here's why. Python's dict uses open addressing with pseudo-random probing (not simple linear chaining). When you look up a key, Python follows the probe sequence until it either finds the key or hits an empty slot — an empty slot signals "stop searching."
A deleted slot (marked as DUMMY) is different from an empty slot. If Python reused a deleted slot for a new key, it would need to ensure that the new key's probe sequence still terminates correctly for all other existing keys that pass through that slot. That's non-trivial to verify at insertion time.
The DUMMY marker solves this elegantly: it tells the lookup "keep probing, don't stop here," while still allowing insertions to reuse the slot for a new key. So Python does reuse DUMMY slots during insertion — just not by "reclaiming" them as empty. The distinction is:
Lookup: DUMMY → keep probing
Insertion: DUMMY → can write here (reuse ✅)
The probe chain doesn't get longer because of DUMMY slots — they're already part of the probing path. What actually triggers a resize is the load factor, not the number of DUMMY entries.
Hope that clarifies it!
This is at odds with this portion of your article...
Insert key4 after deleting key2:
Entry storage:
┌───┬──────┐
│ 0 │ key1 │
├───┼──────┤
│ 1 │ key2 │ ← deleted (wasted, ignored)
├───┼──────┤
│ 2 │ key3 │
├───┼──────┤
│ 3 │ key4 │ ← new entry goes here ✅
└───┴──────┘
Yes, some storage slots may be wasted — but that's acceptable.
Thanks for the sharp eye, Petr! There's actually no contradiction here — they're describing two different layers of Python's dict implementation:
indices array (the hash table index): deleted slots are marked DUMMY and can be reused during insertion ✅
entries array (compact physical storage): deleted entries are left in place; new entries are always appended to the next available position
The article's "Reusing Deleted Entry Storage" section specifically describes the entries array behavior — which is correct.
My earlier reply was describing the indices layer behavior — also correct, just a different layer.
The key insight: Python's dict uses a compact two-layer design, and "reuse" means something different at each layer. Hope that clears it up! 🙂
Please, don't use AI when replying for me amd read what I said...
You're right to call that out, Petr.
I mixed up two different layers of the dict implementation without making that clear — that's on me.
To be precise:
"No reuse of deleted slots" → refers to the entries array (compact storage of actual key-value pairs). Deleted entries stay in place; new entries are always appended. This is what the article's diagram shows.
"DUMMY slots can be reused" → refers to the indices array (the separate hash table index). Deleted index slots are marked DUMMY and are reused during insertion to keep probe chains from growing unnecessarily.
Two different structures, both correct — I just never established that distinction in the article itself. That's the real gap.
Thanks for pushing on it.