Why is key-based search in a dictionary performed quickly?

Searching by keys in a dictionary (dict in Python) is fast due to the use of a hash table. Keys are hashed, and the hash result is used to compute the index in the array. This allows access to values in almost constant time, on average O(1).

Main principles:

1. Hashing: The key is transformed into an integer (hash) using a hash function. This function should be deterministic (the same key always produces the same hash) and evenly distribute hashes for different keys.
2. Indexing: The hash is used to calculate the index in the base array, which stores key-value pairs or references to them.
3. Collisions: Situations may occur where different keys have the same hash (collision). Python uses various strategies to resolve collisions, such as open addressing (searching for the next free cell). When collisions occur, search time may increase, but on average it remains close to O(1).
4. Resizing: When the hash table fills up, Python automatically increases its size and rehashes all existing elements. This maintains a low collision probability and ensures high performance.

# Example of hashing
# The key 'a' is hashed
# The key 'b' is hashed

d = {'a': 1, 'b': 2}

# Example of accessing by key
value = d['a'] # Fast lookup

Thus, the high search speed is due to the fact that finding the required element does not require traversing all dictionary elements, but is done directly by the computed index.