Почему словарь быстрее списка

Словарь в Python работает быстрее списка при поиске элементов, потому что использует хеш-таблицу (O(1) в среднем случае), тогда как список требует последовательного перебора (O(n)). Хеш-функция преобразует ключ в уникальный индекс, что позволяет мгновенно находить значение.

Пример:

# Список - O(n)
my_list = ['a', 'b', 'c']
print('b' in my_list)  # Проверит все элементы

# Словарь - O(1)
my_dict = {'a': 1, 'b': 2, 'c': 3}
print('b' in my_dict)  # Найдёт сразу по хешу

Нюансы:

1. Словари потребляют больше памяти
2. Ключи должны быть хешируемыми (неизменяемыми типами)
3. В худшем случае (коллизии) сложность может деградировать до O(n)