Why is key-based lookup in a dictionary fast?

Lookup by keys in a Python dictionary (or dict) is fast due to its implementation based on a hash table.

When adding a key-value pair:

1. A hash (integer value) is computed from the key using the built-in hash() function.
2. The hash is used to determine the index (bucket) in the array where the pair will be stored.
3. If there are already elements in the bucket (collision), a special algorithm is used to find a free slot or resolve the conflict (for example, open addressing or linked lists, although CPython uses an optimized form of open addressing).

When searching for a value by key:

1. The hash is also computed from the given key.
2. The hash points to a potential bucket in the array.
3. The system checks the elements in this bucket. Since hashes can collide for different keys, the key itself is additionally compared (using __eq__).

On average, this process takes O(1) (constant time), regardless of the number of elements in the dictionary. In the worst case (many collisions and poor hash distribution), the time can approach O(n) (linear time), but in practice, this is rare due to good hash function implementation and collision resolution mechanisms.

Compared to lists (where searching for an element by value takes O(n) on average), and ordered data structures like search trees (O(log n)), dictionaries provide significantly faster key-based access.

# Example of hash calculation
key = "example_key"
hashed_key = hash(key)
print(f"Hash of key '{key}': {hashed_key}")

# Dictionary
my_dict = {"a": 1, "b": 2, "c": 3}

# Fast access by key
value = my_dict["b"] # O(1) on average
print(f"Value for key 'b': {value}")