Коллекции

Типы данных Python

Неизменяемые (немутабельные, immutable) типы данных: числа (int, float), строки (str), булевые (bool), кортежи (tuple) и frozenset. Также - None, complex, bytes.
Изменяемые (мутабельные, muttable) типы данных. К изменяемым относятся списки (list), множества (set) и словари (dict). Также байтовый массив bytearray.

Изменяемые типы данных могут быть изменены после их создания, а неизменяемые — нет.

None - экземпляр типа объекта NoneType, который используется для обозначения отсутствия значения

bool - булевы значения (True, False)

int - целые чисел, как положительныхе, так и отрицательные

float - числа, которые могут иметь десятичную часть (с плавающей точкой)

complex - комплексные числа

str - текстовая информация (строка, последовательность символов)

tuple - неизменяемые упорядоченные коллекции элементов (кортежи)

bytes - байтовые последовательности, которые используются для работы с бинарными файлами

frozenset - неизменяемый тип данных, представляющий неупорядоченную коллекцию уникальных элементов

list - изменяемые упорядоченные коллекции элементов (списки)

dict - ассоциативный массив, пары «ключ-значение», где каждый ключ является уникальным

set - неупорядоченная коллекция уникальных элементов (поддерживает операции над множествами - объединения, вхождения, исключения)

bytearray - массив заданных байтов

Отличие списка от кортежа

Список и кортеж в Python различаются главным образом изменяемостью: список является изменяемым (может быть изменен после создания), тогда как кортеж является неизменяемым (не может быть изменен после создания). Это означает, что элементы списка можно добавлять, удалять или изменять, а элементы кортежа после создания остаются неизменными.

Под список выделяется определенное место в памяти, когда оно заканчивается (после добавления новых элементов) выделяется новое место памяти большего размера, в которое переносится весь список, для кортежа выделяется фиксированное место в памяти и никогда не меняется, так как кортеж неизменяем(поэтому работа с ним быстрее)

Семантическое различие

Список обычно содержит однородные данные (элементы одного типа и назначения).
Кортеж часто содержит разнородные данные, где позиция элемента имеет смысловое значение.

Аннотации типов

Кортежи можно аннотировать как записи с фиксированной структурой, где указывается тип для каждой позиции. Это полезно для представления структур данных с определенной схемой, например, информация о человеке (имя, возраст, активен) или координаты точки (x, y). tuple[int, str, bool] - кортеж из 3 элементов типов int, str, bool.

Области применения

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

Что может быть ключом в словаре?

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

Соответственно, ключом в словаре может быть любой хэшируемый тип данных.

Механизм работы:

Вычисляется хеш ключа
По хешу определяется "корзина" (bucket)
В корзине ищется ключ (уже с использованием eq)

Если хеш объекта меняется после помещения в словарь, он окажется в неправильной корзине и станет недоступен.

Хешируемость — это протокол, состоящий из двух методов:

__hash__— возвращает хеш-значение объекта
__eq__ — определяет равенство объектов

Любой объект по умолчанию хешируем (благодаря реализации в object). В базовом классе object уже реализованы оба метода:

__hash__— основан на идентификаторе объекта (id)
__eq__— сравнивает идентификаторы объектов (is)

Это означает, что любой созданный нами класс по умолчанию хешируем.

Объект становится нехешируемым, если:

Явно установить hash = None
Переопределить eq, но не переопределить hash

Кортеж (tuple) не может быть ключом в словаре, в том случае если в нем изменяемые типы данных.

Как dict и set реализованы внутри?

Dict и Set реализованы в виде хэш-таблицы.

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

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

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

Статья на хабре: Python. Внутреннее устройство множеств set и словарей dict.

Коллизия

Kоллизия - случай, когда хеш функция возвращает идентичный хеш для различных объектов.

Способов бороться с хеш-коллизиями концептуально два.

Метод цепочки

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

Пример

Это как если положить все книги с одинаковым номером на одну полку. Тогда при поиске книги придется найти нужную полку, взять первую книгу и прочитать название. Если не та — проверить следующую, и так далее. В худшем случае все `n` книг попадут на одну полку и сложность получится O(n).

Недостатки: при большом числе коллизий производительность может снижаться до линейного поиска внутри списка.

Открытая адресация

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

Пример

Говоря языком библиотекаря, в этом случае библиотека получается большая, но полупустая. Потому что если полка, на которую вы хотели положить книгу, оказалась занята, вы выбираете другую свободную полку и кладете книгу туда. А потом по такому же алгоритму вычисляете, где находится нужная книга.

Недостатки: открытая адресация может вызвать проблемы с заполнением таблицы, так как более высокая степень заполненности снижает производительность из-за длинных цепочек поиска.

Наиболее распространённые методы поиска - Линейное пробирование (Linear Probing): Если ячейка занята, проверяются следующие ячейки последовательно (например, i+1, i+2, i+3, ...), пока не найдётся свободная. - Квадратичное пробирование (Quadratic Probing): Если ячейка занята, следующая проверяемая ячейка находится по формуле i + 1^2, i + 2^2, i + 3^2, .... Это помогает снизить проблему кластеризации, характерную для линейного пробирования. - Двойное хеширование (Double Hashing): Если ячейка занята, используется вторая хеш-функция для определения шага поиска свободной ячейки. Например, если первая хеш-функция дала результат h1, а вторая хеш-функция даёт h2, ячейки проверяются по формуле i + h2, i + 2*h2, ....

Сcылка на статью habr - метод открытой адресации. (https://habr.com/ru/post/247843/).

Где поиск выполняется быстрее: в списках или словарях?

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

Из этого видно, что поиск в словарях работает быстрее. Это особенно заметно при большом количестве значений. Но есть обратная сторона: словари не всегда удобно использовать для хранения большого количества данных из-за требования уникальных ключей.