Как множества и словари реализованы внутри?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

Множества и словари в Python — это структуры данных, которые обеспечивают быстрый доступ к элементам благодаря использованию хеш-таблиц. Хеш-таблица — это структура данных, которая использует хеш-функцию для вычисления индекса, по которому элемент будет храниться в массиве. Это позволяет быстро находить элемент по ключу.

Хеш-таблицы

Хеш-таблица состоит из массива, где каждый элемент называется "бакетом". Когда вы добавляете элемент в множество или словарь, Python использует хеш-функцию для вычисления хеш-значения ключа. Это значение затем преобразуется в индекс массива, где будет храниться элемент.

Пример работы хеш-таблицы

# Создаем словарь
my_dict = {}
​
# Добавляем элемент
my_dict['key'] = 'value'

• my_dict = {}: Создается пустой словарь. Внутри Python выделяет массив для хранения элементов.
• my_dict['key'] = 'value':
  • Хеш-функция вычисляет хеш-значение для строки 'key'.
  • Хеш-значение преобразуется в индекс массива.
  • В массиве по этому индексу сохраняется пара ключ-значение ('key', 'value').

Коллизии

Коллизия возникает, когда два разных ключа имеют одинаковое хеш-значение. Python решает коллизии с помощью метода открытой адресации или цепочек. В случае открытой адресации, если бакет занят, Python ищет следующий свободный бакет. В случае цепочек, каждый бакет хранит список всех элементов, которые имеют одинаковый хеш.

Множества

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

Пример работы множества

# Создаем множество
my_set = set()
​
# Добавляем элемент
my_set.add('element')

• my_set = set(): Создается пустое множество.
• my_set.add('element'):
  • Хеш-функция вычисляет хеш-значение для строки 'element'.
  • Хеш-значение преобразуется в индекс массива.
  • В массиве по этому индексу сохраняется элемент 'element'.

Применение

Множества и словари широко используются в Python для задач, требующих быстрого доступа к данным. Словари часто применяются для хранения пар ключ-значение, например, для конфигураций или кэширования. Множества используются для операций с уникальными элементами, таких как удаление дубликатов или проверка принадлежности.