What happens if two elements have the same hash?

This is called a hash collision. When using hash tables (for example, dictionaries in Python), if two keys have the same hash, they cannot be placed directly into the same "bucket". Instead, a collision resolution strategy is used.

One common strategy is chaining. In this case, each bucket contains not just one element, but a list or another data structure (such as a linked list) containing all elements with matching hashes that point to this bucket.

When searching for an element, the hash of the key is computed to determine the bucket, and then a sequential search is performed within that bucket until an element with a matching key is found.

Another strategy is open addressing. In this case, when a collision occurs, the algorithm searches for the next free bucket according to a certain rule (such as linear or quadratic probing) to place the element. Searching also involves probing until an element with a matching key or an empty bucket is found.

Python dictionaries use a combination of these approaches, optimized for performance.

# Example of a hash collision in a dictionary
class CollidingKey:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        # Simulate the same hash for different objects
        return 42

    def __eq__(self, other):
        if isinstance(other, CollidingKey):
            return self.value == other.value
        return False

key1 = CollidingKey("A")
key2 = CollidingKey("B")

# Although hashes are equal, __eq__ defines them as different keys
print(f"Hash of key1: {hash(key1)}")
print(f"Hash of key2: {hash(key2)}")
print(f"key1 == key2: {key1 == key2}")

my_dict = {key1: 10, key2: 20}

# When accessing by key, despite the same hash, Python
# uses the __eq__ method to resolve the collision
print(f"Value for key1: {my_dict[key1]}")
print(f"Value for key2: {my_dict[key2]}")

# When adding a new element with the same hash but a different value,
# it will be placed in the same "bucket" but considered a separate element
key3 = CollidingKey("A") # Equal to key1 by value
my_dict[key3] = 30

# Now key1 and key3 point to the same place in the dictionary due to __eq__
print(f"Value for key1 after adding key3: {my_dict[key1]}")

Hash collisions are a normal phenomenon in hash tables. A good hash function minimizes their probability. However, with a large number of collisions, the performance of insert, delete, and search operations in a hash table can deteriorate, approaching O(n) in the worst case.