Opening

Have you ever encountered this frustration - you used Python dictionaries as a "secret weapon" to optimize query performance, but the program unexpectedly slowed down? As a Python developer, I've deeply experienced this kind of frustration. Today, let's explore the challenging problem of "hash collisions" behind dictionaries and see how to cleverly handle it in practice.

Essence

To discuss hash collisions, we first need to talk about how Python dictionaries work. A dictionary is essentially a hash table that uses a hash function to convert keys into array indices. It's like a huge storage locker where each compartment has its own number (index). When we store data, we calculate a number based on the key and then put the data in the corresponding compartment.

However, this process often encounters an awkward problem - different keys might correspond to the same compartment, which is called a "hash collision." It's like two people trying to put their things in the same storage compartment, and we need to find a way to resolve this conflict.

I encountered a typical case in actual development. Once we needed to process a large amount of user data, using user IDs as dictionary keys. We thought dictionary lookups should be fast, but the system became unusually slow. After analysis, we found that the user ID generation rules led to many IDs having similar hash values, causing severe hash collisions.

Impact

So how much impact do hash collisions actually have? Let's do an experiment:

import time
import random
import string

def generate_similar_strings(prefix, count):
    """Generate strings with the same prefix"""
    return [prefix + ''.join(random.choices(string.ascii_lowercase, k=5)) 
            for _ in range(count)]

def generate_random_strings(length, count):
    """Generate completely random strings"""
    return [''.join(random.choices(string.ascii_lowercase, k=length)) 
            for _ in range(count)]

def performance_test(keys):
    """Test dictionary operation performance"""
    d = {}

    # Test insertion performance
    start_time = time.time()
    for i, key in enumerate(keys):
        d[key] = i
    insert_time = time.time() - start_time

    # Test lookup performance
    start_time = time.time()
    for key in keys:
        _ = d[key]
    lookup_time = time.time() - start_time

    return insert_time, lookup_time


n = 100000


similar_keys = generate_similar_strings("user_", n)
similar_insert_time, similar_lookup_time = performance_test(similar_keys)


random_keys = generate_random_strings(10, n)
random_insert_time, random_lookup_time = performance_test(random_keys)