Если с объяснением того, что такое дикт и как его юзать у нас проблем не возникает, то вот ответить как они устроены в Python, а при правильном ответе получить следующий: “А как решаются коллизии?”, то уже ответить проблематичнее.
Отвечаю сразу на первый вопрос - в Python’e ассоциативный массив реализован с помощью хеш-таблицы (для заметки, в C++ красно-чёрные деревья).
В основе всего лежит хеш-функция. И вот многие говорят, что хорошая хеш-функция эта то, что дает более рандомный ответ, но разрабы путона так не считают и их хеша схожи, даже для разных строк. Этим свойством они пользуются для оптимизации, но об этом ниже.
Уж не будем про то, что такое хеш, просто строка байт, полученная от какого-то алгоса, которому скормили какие-то входные данные. Для одинаковых данных будет один и тот же хеш.
В общем есть пару статей на эту тему, но там всё устарело, ибо с Python3.6 были некоторые оптимайзы по памяти. То, как представлен словарь. Подходы, алги и т.д. не меняли. На данный момент PyDictObject представляет из себя структуру из:
ma_used - кол-во айтемов в словаре, ma_version_tag - просто глобальное уникальное значение, которое меняется при каждом изменении словаря.
Дальше объяснить будет чуть сложнее, ибо сейчас вкину то, о чем расскажу ниже.
ma_keys - PyDictKeysObject который там в конце концов сводится к PyDictKeyEntry (пропущен жирный пласт с количеством юзабельных и использованных entries и т.д., сорри), а он, в свою очередь, состоит из:
С этой структурой всё понято, дык вот фича в том, что ma_keys конкретно для ключей и значений используется только тогда, когда таблица не является разорванной/разделенной (splitted короче). Когда же таблица “combined”, то ключи используются из me_keys, а значения из me_value!
Задетектить сплитед она или комбаин легко. Если me_value is Null - combined
Имеем хоть какое-то представление теперь о словарях в реализации CPython, идем дальше к самому вкусному.
В каждом слоте хеш-таблицы может храниться только один объект (хеш, ключ, значение).
Конечно же имеются коллизии (когда у двух разных объектов одинаковый хеш) и это нормально, такое надо уметь решать.
Есть несколько алгоритмов разрешать их, но в нашем случае - это открытая адресация. Есть ещё алгоритм через цеопчки (храним лист), но он проигрывает по памяти из-за хранение указателей на элементы в списке, но у него конечно есть плюсы. Речь не о чем, “Python” сделал свой выбор.
Алгоритм открытой адресации очень прост. Мы берем хеш нашего ключа и делаем MOD <размер хеш-таблицы>. Таким образом получаем индекс для вставки нашего элемента. Что же происходит, когда ячейка уже занята? Просто берем и смотрим в следующую, да-да, тупо выходит следующее:
hash(k) % TABLE_SIZE + i, где i, какой-нибудь счетчик, пока не дойдем до свободной ячейки!
Когда нам необходимо найти что-то, то делаем тоже самое, только попав на какую-то ячейку проверяем её по хешу и ключу, если мы попали не туда - делаем +1 и смотрим дальше.
Хотим удалить что-то? Затираем элемент, но ставим маркер на эту ячейку, если за ней есть другие элементы, если нет - просто удаляем.
И вот как раз когда мы удаляем(затираем), появляются несколько последовательность, между которыми может стоять маркер. Это и есть splitted хэш-таблица!
Маркер нужен для того, чтобы не прекратить наш линейный поиск ячейки с нужным нам значением тогда, когда мы дойдем до пустой ячейки (ибо дальше есть другие).
Понятное дело, что чем больше вот таких пустых мест, тем дольше мы будем всё искать и искать, куда же мы там сохранили. Для этого есть пересоздание словаря. Чет тип фрагментации что ль. Есть критическое значение маркеров, при котором создается новый словарь из старых значением, но без “пробелов” между ячейками.
Entry в словаре (слот) может быть в одном из 4 состояний: unused, active, dummy и pending. Подробнее о каждом сможете почитать сами, снизу линк.
НА САМОМ ДЕЛЕ НЕ ВСË ТАК ПРОСТО
Я рассказал про банальную открытую адресацию, но в Python’e используют как раз то, что я упомянул выше - схожесть хешей. В связи с этим поиск нужной ячейки получается совсем не просто +1, а есть определенный шаг, с которым мы ходим. Есть linear probing (наш +1 каждый раз), а есть double probing. Фича второго в том, что мы двигаемся не на +1, а на хэш, но уже второй функции от того же k.
Я бы не сказал, что в Python’e используется двойное хеширование, у них своё. Шаг вычисляется так:
j = (5 * j) + 1 + perturb;
Всё это дико интересно конечно, но в то, как это работает я особо не вникал, хотя они всё подробно расписали в доке к методу (линк снизу).
Кста, есть фактик. Каждый словарь инициализируется с 8 слотами, что позволяет сохранять 5 элементов. Сделано это для того, что в большинстве мест, в самом CPython очень часто используются словари всего для 2-3 элементов и чтобы не использовать больше памяти, чем надо, поступили вот так. И да, насколько помню, у нас что в листах, что тут, всегда выделено больше памяти и больше доступно ячеек, чем есть на самом деле. То, что у вас len([1,2,3]) выдает 3, не значит, что там на самом деле столько ячеек. Связано это с тем, что выделять по 1 ячейке при каждом append’e слишком дорого по времени, поэтому выделяют всегда с запасом для следующих вставок.
Чтобы избежать замедления поиска в хеш-таблице она ресайзиться при заполнении на две трети.
Собсна у меня всё, было интересно посмотреть на исходники CPython’a. Будет что рассказать на собесах, надеюсь и Вам тоже. Я кста не перечитываю что написал, да-да.
Забылся. В коде вместо % (mod) стоит & (вот про MOD из доки):
size_t i = hash & mask;
i = mask & (i*5 + perturb + 1);
Фишка в том, что mask - размер таблицы минус 1, но размер таблицы всегда степень двойки.
Обещанные ссылки:
31.12.2023 — Итоги Года
Итоги Года 202331.12.2022 — Итоги Года
Итоги Года 202231.12.2021 — Итоги Года
Итоги Года 202131.12.2020 — Итоги Года
Итоги Года 2020