Python, в середині dict'a

Наступним, за що я взявся в пітончику розбирита аби понять проблеми перфоменсу був славнозвісний dict, гроза всіх мап та хеш-таблиць ! 

Оп оп оп!

В пітончику дікт - це проста хеш-мапа , зі своїми власними приколи , але все ж таки хеш-мапа. Тому якщо ви знаєте , що це таке то можете далі не читати. А якщо ні - то продовжуйте.

Дікт - це сам по собі асоціація масивів  ключ/значення ( пара ключ/значення представлення масивом ). І дуже багато речей, алгоритмічно начебто схожи на динамічний список в тому ж самому пітончику. Але є декілька своїх власних унікальних речей. Деякі з них я спробую тут і описати (=.
Як і все білдинівське , пітонівський дікт реалізований на сішці.
Наприклад пара ключ-значення предстають для нас в такому вигляді:

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

Тобто по своїй сішній суті це окремий тип даних, який мість в собі обєк ключа, обєкт значення і розмір хеша утвореного з ключа. З таких ось записів і складається сам дікт.
Сам жеш  дікт на сішечці виглядає десь так.

typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;
    Py_ssize_t ma_used;
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};


Тобто це вже на порядок складніше за ліст  ( структуру якого я досліджував ось тут ), але і на багато цікавіше , бо структура складніша. Давайте глянемо, що там в середині є такого:

• ma_fill - це кількість акитивних комірок ( вільних і зайнятих ) плюс кількість видалених комірок
• ma_used - кількість використаних комірок
• ma_table - наш масив значень
• ma_mask - розмір масиву мінус 1, для вираховування значення індексу комірки ( слота )
• ma_smalltable - початковий масив довжиною 8! аве!!

Стає вже трошки зрозуміліше? Дікт так само як ліст, містить в собі всю інформацію про себе - розмір, кількість зайнятиз комірок, кільких видалених комірок і  масив обєктів які містять ключ/значення. Це все допомагає дікт більшість речей виконувати з мінімальною вартітю для нашого пітончика ( доступ по ключу до обєкта, добавлення елемента, взанвання кількості ключів дікта, видалення елемента тощо)ПОтже коли ми це все уявили треба подивитися як він насправді працює. І тут треба розглянути два пункти:

• Ініціалізація словника
• Під час будь-якого створеня словника ( чи то d = dict() , чи d = {}, чи d = {1:'one'} ) спершу викликається сішна функція PyDict_New(),  в результаті отримуємо будемо  створену структуру, що описана вище і з готовими комірками під 8 елементів (=

returns new dictionary object
function PyDict_New:
    allocate new dictionary object
    clear dictionary's table
    set dictionary's number of used slots + dummy slots (ma_fill) to 0
    set dictionary's number of active slots (ma_used) to 0
    set dictionary's mask (ma_value) to dictionary size - 1 = 7
    set dictionary's lookup function to lookdict_string
    return allocated dictionary object

• відразу встановлюється значення використаних слотів
• відразу встановлюється значення вільних слотів
• ініціалізується lookdict_string функція
• та встановлюється маска для нашого дікта

Я думаю тут все ясно, що відбулося і розказувати не має сенсу (^_^)

• Під час добавлення елементу до такого дікта ця вся структура починає працювати власне як хеш-мапа  і розкривати всю її суть.
• Добавлення елементу до словника виконуєтсья за допомогою такої структури

arguments: dictionary, key, value
returns: 0 if OK or -1
function PyDict_SetItem:
    if key's hash cached:
        use hash
    else:
        calculate hash
    call insertdict with dictionary object, key, hash and value
    if key/value pair added successfully and capacity over 2/3:
        call dictresize to resize dictionary's table

• Під час добавлення пари ключ/значення викликаєтсья ще одна допоміжна функція PyDict_SetItem(). Ця функція перевіря, чи ключ ок для дікта і вираховує хеш для нього, а потім за допомогою insertdict() добавляє нашу пару та нові слоти  ( якщо заповненість 2/3 від загальної кількості слотів  - не питайте чому саме така кількість, навіть не знаю)
• Для пошуку правильної комірки в дікті ( тобто тої куди має бути записаний ключ, або де він вже є ) - викликається lookdict_string() - вона по готовому хешу вираховує комірку для нашого ключа.
• Під час добавлення ключа може бути ще один цікавий випадок - "колізія імен", співпадіння хешів для двох різних ключів. Таке відбуваєтсья досить рідко - але можливе. Отже якщо наша функція lookdict_string() знаходить комірку для  нашого ключа , але вона зайнята - то просто дивиться чи наступна комірка є вільною , і так поки вона не знайде вільну комірку.

Начебто все просто правда? тіко троха багато коду схожого на сішний (=.