Где поиск по элементу быстрее - в словаре или множестве в Python?

Поиск в словаре vs множество

Оба контейнера обеспечивают O(1) амортизированную сложность поиска в среднем случае, но есть важные различия в практическом применении.

Теория

Словарь и множество используют хеш-таблицы под капотом. Это означает:

• Словарь (dict): хеширует ключи для быстрого доступа к значениям → O(1) для key in dict и dict[key]
• Множество (set): хеширует элементы напрямую → O(1) для element in set

Оба имеют одинаковую асимптотическую сложность!

Практическое сравнение

import timeit

# Подготовка данных
test_dict = {i: i for i in range(1_000_000)}
test_set = set(range(1_000_000))
test_key = 999_999

# Тест производительности
dict_time = timeit.timeit(
    lambda: test_key in test_dict,
    number=10_000_000
)

set_time = timeit.timeit(
    lambda: test_key in test_set,
    number=10_000_000
)

print(f"Словарь: {dict_time:.4f}с")
print(f"Множество: {set_time:.4f}с")

Результаты на практике

Множество немного быстрее (~15-20% в типичных случаях) по следующим причинам:

1. Меньше памяти на элемент: множество хранит только хеш и сам элемент, словарь дополнительно хранит значение
2. Меньше операций: при поиске в set нужно только хешировать элемент
3. Лучше кеширование: меньший footprint означает лучше попадание в CPU cache

Реальный пример

# Если нужна только проверка наличия
fruits_set = {"apple", "banana", "orange"}
if "apple" in fruits_set:  # ← быстрее
    print("Found!")

# Если нужно значение, то словарь уместен
fruits_dict = {
    "apple": {"price": 100, "origin": "Poland"},
    "banana": {"price": 50, "origin": "Ecuador"}
}
if "apple" in fruits_dict:
    info = fruits_dict["apple"]

Итоговые рекомендации

• Используй set для проверки принадлежности элемента
• Используй dict когда нужно ассоциировать ключи со значениями
• Обе структуры имеют O(1) в среднем, но set немного быстрее
• Разница заметна только с миллионами элементов