Хеш-множество: как за миг понять, что элемент уже встречался

Очень частый вопрос в программах звучит так: «этот элемент мы уже встречали?» — и множество отвечает почти мгновенно.

Хеш-множество — это хеш-таблица, которая хранит только ключи без значений. Её работа — мгновенно говорить «да, есть» или «нет, нету».

Что такое множество

Множество (set) — это набор, где, во-первых, каждый элемент встречается ровно один раз (дубликаты невозможны по определению), и во-вторых, главная операция — проверка «есть ли здесь такой элемент?». Порядок элементов при этом не важен. Ровно как математическое множество из школы.

В большинстве языков множество построено на знакомой нам хеш-таблице, только хранит оно одни ключи. Поэтому проверка наличия, добавление и удаление работают за O(1) — то самое «мгновенно независимо от размера». Спрашиваете «есть ли элемент Х?» — структура считает его хеш, прыгает в нужную ячейку и сразу отвечает.

Три задачи, где множество незаменимо

Убрать дубликаты

Самое частое применение — почистить данные от повторов. Кладёшь всё подряд в множество, а оно само выбрасывает повторяющееся, потому что дважды один элемент в нём не уживается:

visits = ["Аня", "Ваня", "Аня", "Петя", "Ваня", "Аня"]
unique = set(visits)
print("Уникальных посетителей:", len(unique))   # 3
print(unique)

Проверить, было ли уже

Голосовал ли пользователь? Видели ли мы этот email? Вместо перебора всего списка держим множество уже встреченного и спрашиваем за один шаг:

voted = set()

def try_vote(user):
    if user in voted:               # проверка за O(1)
        return "Уже голосовал!"
    voted.add(user)
    return "Голос принят"

print(try_vote("u42"))   # Голос принят
print(try_vote("u42"))   # Уже голосовал!

Найти пересечение и разность

Множества умеют то, чего нет у списков: быстро отвечать на «что есть в обоих?» и «что есть здесь, но не там?». Это пересечение и разность — и они однострочные:

friends_a = {"Маша", "Дима", "Лена", "Олег"}
friends_b = {"Лена", "Олег", "Катя"}

print("Общие друзья:", friends_a & friends_b)   # пересечение
print("Только у A:", friends_a - friends_b)      # разность

Чем множество отличается от списка

За что приходится платить

У множества есть ограничения. В него можно класть только хешируемые элементы — то есть такие, для которых можно посчитать хеш и которые не меняются (числа, строки, кортежи; а вот список внутрь множества не положить). И оно не хранит порядок: если вам важна последовательность, множество не подойдёт. Памяти оно тоже тратит чуть больше, чем простой список, ради своей скорости.

Когда тянуться за множеством

Правило простое. Как только в коде назревает вопрос «а это мы уже видели?» или «нет ли тут повторов?» — это сигнал взять множество вместо списка. Замена часто превращает медленный код, который перебирает данные снова и снова, в быстрый, отвечающий за один шаг. Маленькая структура, а экономит огромное количество времени.