**Как устроены словари в Python?** **Часть 1**

Один из самых популярных вопросов на собесах. Так много статей в интернете, так мало правильных ответов&#33;
Сегодня будем разбирать.

**Базовое устройство**

Если вы не смотрели [классический доклад Реймонда Хеттингера](https://www.youtube.com/watch?v=p33CVV29OG8) про устройство словарей в Python3.6+, то нужно срочно посмотреть. Там он рассказывает про устройство хеш-таблицы, проблему хеш конфликтов, сохранение порядка вставки и даже про кеш линии процессора.

Давайте попробуем для начала понять, что за хеш-таблица, и [где она](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/cpython/dictobject.h#L8-L33).


typedef struct {
    PyObject ob_base;
    Py_ssize_t ma_used;  // number of keys
    uint64_t _ma_watcher_tag;  // dict watchers
    PyDictKeysObject *ma_keys;
    PyDictValues *ma_values;
} PyDictObject;


Пока вроде бы все ожидаемо: структура словаря хранит в себе базовый класс, количество ключей, "watchers" (обсудим позже), ключи, значения.

Как выглядят сами [ключи](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/internal/pycore_dict.h#L205-L250)?


struct _dictkeysobject {
    Py_ssize_t dk_refcnt; // own refcount
    uint8_t dk_log2_size; // key size
    uint8_t dk_kind; 

#ifdef Py_GIL_DISABLED
    PyMutex dk_mutex;  // protect shared keys
#endif

    uint32_t dk_version; // version number
    Py_ssize_t dk_usable; //  number of usable entries in dk_entries
    Py_ssize_t dk_nentries; // number of used entries
    char dk_indices[]; // actual hashtable
};


А вот теперь посмотрим на возможные инварианты словарей:
- `ma_keys->dk_kind` может быть одним из трех значений: `general` (как мы все привыкли), `unicode` (оптимизация для словарей только с `str` ключами), `split` (оптимизация для `instance.__dict__`)
- [Если](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/cpython/dictobject.h#L27-L31) `ma_keys->dk_kind &#33;= DICT_KEYS_SPLIT`, то `ma_values == NULL`
- Если `ma_keys->dk_kind == DICT_KEYS_SPLIT`, то `ma_values &#33;= NULL`

Ну и сами split [значения](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/internal/pycore_dict.h#L267-L279):


struct _dictvalues {
    uint8_t capacity;
    uint8_t size;
    uint8_t embedded;
    uint8_t valid;
    PyObject *values[1];
};


**Важные оптимизации**

- Ключи могут быть оптимизированы под `str` (`DICT_KEYS_UNICODE`), тогда происходит важное: мы начинаем использовать [PyDictUnicodeEntry](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Objects/dictobject.c#L847-L851) вместо PyDictEntry, у первого нет хранения `hash`. Что делает его меньше в размере:


sys.getsizeof({'a': 1}) # 184
sys.getsizeof({1: 1}) # 224


- Словарь может быть "разделен" с `DICT_KEYS_SPLIT`, тогда ключи и значения хранятся отдельно. Зачем? Обычно все объекты одного класса имеют одинаковый набор ключей `CACHED_KEYS(Py_TYPE(obj))`. Что позволяет нам [переиспользовать](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/internal/pycore_dict.h#L252-L261) один "shared" объект ключей для всех инстансов. Данная оптимизация использует `str` ключи внутри в том числе

-  Еще одна оптимизация рядом для `instance.__dict__` (работает по-умолчанию, для всех типов с `Py_TPFLAGS_INLINE_VALUES` и `Py_TPFLAGS_MANAGED_DICT`): `ma_values->embedded`. Такие "словари" хранятся прямо в памяти самого объекта (не более 16 объектов): `PyObject header | object fields | PyDictValues header | values[0..capacity-1]`

На чем я вчера и [погорел](https://github.com/python/cpython/issues/161767), когда [дизайнил свою C-API функцию](https://docs.python.org/3.16/c-api/dict.html#c.PyDict_AsFrozenDictAndClear) `PyDict_AsFrozenDictAndClear`.

Такие словари можно "материализовать" в обычные: `instance.__dict__` как раз вызовет такую машинерию при обращении. Словарь и `instance.__dict__` - отличаются примерно всем внутри до материализации.

**Важные детали реализации**

- У ключей есть [свой refcount](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Objects/dictobject.c#L480-L523). Потому что ключи могут переиспользоваться в разных словарях, но они не `PyObject *`. В CPython есть много отдельных refcount штук. Если интересно, могу подробнее рассказать.
- А [Py_EMPTY_KEYS](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Objects/dictobject.c#L645-L660) вообще бесмертный объект
- [DictWatcher](https://docs.python.org/3.16/c-api/dict.html#c.PyDict_AddWatcher)'ы и `_ma_watcher_tag` нужны, чтобы управлять Tier 1 speciailizing оптимизациями. Изменился объект или тип? Watcher скинет статистику для данного объекта в интерпретаторе. Аналогично и `dk_version` - для использования в качестве ключа для кеша в JIT
- [PyFrozenDict](https://github.com/python/cpython/blob/4497fe9889105b1abc6d633971e84ee9f78bd3b8/Include/internal/pycore_dict.h#L457-L461) устроен точно так же, только сразу хранит в себе `ma_hash`, для быстрого хеширования

Что мы не успели обсудить в 1 части? Саму хештаблицу, логику увеличения памяти под ключи, поиск по хешу и логику сравнения значений с одинаковым хешом, какие бывают слоты, локи для FT.

**Обсуждение**: Узнали ли вы что-то новое о словарях? Были ли у вас такие вопросы на собесе?