Реалізація словника в Python 2.7

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

На написання цієї статті мене наштовхнув запитання Stack Overflow.
У статті розглядається реалізація CPython версії 2.7. Всі приклади були підготовлені в 32-бітної версії Python на 64-бітної ОС, для іншої версії значення будуть відрізнятися.

Словник в Python

Словник в Python є асоціативним масивом, тобто зберігає дані у вигляді пар (ключ, значення). Словник — измененяемый тип даних. Це означає, що в нього можна додавати елементи, змінювати та видаляти з словника. Він також надає операцію пошуку і повернення елемента з ключем.

Ініціалізація і додавання елементів:

>>> d = {} # те ж саме, що d = dict()
>>> d['a'] = 123
>>> d['b'] = 345
>>> d['c'] = 678
>>> d
{'a': 123, 'c': 678, 'b': 345}

Отримання елемента:

>>> d['b']
345

Видалення елемента:

>>> del d['c']
>>> d
{'a': 123, 'b': 345}

Ключі словника можуть бути значення тільки hashable типів, тобто типів, у яких може бути отриманий хеш (для цього у них повинен бути метод __hash__()). Тому значення таких типів, як список (list), набір (set) і власне сам словник (dict), не можуть бути ключами словника:

>>> d[list()] = 1
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
TypeError: unhashable type: 'list'
>>> d[set()] = 2
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
TypeError: unhashable type: 'set'
>>> d[dict()] = 3
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
TypeError: unhashable type: 'dict'


Реалізація

Словник в Python реалізований у вигляді хеш-таблиці. Як відомо, реалізація хеш-таблиці повинна враховувати можливість появи колізій — ситуацій, коли різні ключі мають однакове значення хеш. Повинен бути спосіб вставки і вилучення елементів з урахуванням колізій. Існує кілька способів вирішення колізій, наприклад метод ланцюжків і метод відкритої адресації. В Python використовується метод відкритої адресації. Розробники обрали метод відкритої адресації методом ланцюжків з огляду на те, що він дозволяє значно заощадити пам'ять на зберіганні покажчиків, які використовуються в хеш-таблиці з ланцюжками.

У розглянутій реалізації кожна запис (PyDictEntry) в хеш-таблиці словника складається з трьох елементів — хеш, ключ і значення.

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

Структура PyDictObject виглядає наступним чином:

#define PyDict_MINSIZE 8
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];
};

При створенні нового об'єкта словника його розмір дорівнює 8. Це значення визначається константою PyDict_MINSIZE. Для зберігання хеш-таблиці в PyDictObject були введені змінні ma_smalltable і ma_table. Змінна ma_smalltable з предвыделенной пам'яттю розміром PyDict_MINSIZE (тобто 8) дозволяє невеликим словників (до 8 об'єктів PyDictEntry) зберігатися без додаткового виділення пам'яті. Експерименти, проведені розробниками, показали, що цього розміру достатньо для більшості словників: невеликих словників примірників і зазвичай невеликих словників, створених для передачі іменованих аргументів (kwargs). Змінна ma_table відповідає ma_smalltable для маленьких таблиць (тобто для таблиць з 8 клітинок). Для таблиць більшого розміру пам'ять ma_table виділяється окремо. Змінна ma_table не може бути дорівнює NULL.

Якщо комусь раптом захочеться змінити значення PyDict_MINSIZE, це можна зробити в исходниках, а потім перезібрати Python. Значення рекомендується робити рівним ступеня двійки, але не менше чотирьох.

Комірка хеш-таблиці може мати три стани

1) Невикористана (me_key == me_value == NULL)
Цей стан означає, що осередок не містить і ще ніколи не містила пару (ключ, значення).
Після вставки ключа «невикористана» осередок переходить в стан «активна».
Це стан — єдиний випадок, коли me_key = NULL і є початковим станом для всіх клітинок у таблиці.
2) Активна (me_key != NULL me_key != dummy і me_value != NULL)
Означає, що комірка містить активну пару (ключ, значення).
Після видалення ключа осередок зі стану «активна» переходить в стан «порожня» (тобто me_key = dummy, а
dummy = PyString_FromString("<dummy key>")).
Це єдине стан, коли me_value != NULL.
3) Порожня (me_key == dummy і me_value == NULL)
Це стан говорить про те, що осередок раніше містила активну пару (ключ, значення), але вона була видалена, і нова активна пара ще не записана у клітинку.
Так само як і при стані «невикористана», після вставки ключа осередок зі стану «порожня» переходить в стан «активна».
«Порожня клітинка не може повернутися в стан «невикористана», тобто повернути me_key = NULL, так як в даному випадку послідовність проб у разі колізії не буде мати можливість дізнатися, чи осередку «активні».

Змінні-члени структури

ma_fill — число ненульових ключів (me_key != NULL), тобто сума «активних» і «порожніх» осередків.
ma_used — число ненульових і не «порожніх» ключів (me_key != NULL, me_key != dummy), тобто кількість «активних» елементів.
ma_mask — маска, рівна PyDict_MINSIZE — 1.
ma_lookup — функція пошуку. За замовчуванням при створенні нового словника використовується lookdict_string. Так зроблено тому, що розробники порахували, що більшість словників містять тільки рядкові ключі.

Основні тонкощі

Ефективність хеш-таблиці залежить від наявності «хороших» хеш-функцій. «Хороша» хеш-функція повинна обчислюватися швидко і з мінімальною кількістю колізій. Але, на жаль, найбільш часто використовуються і важливі хеш-функції (для строкового і цілого типів) повертають достатньо регулярні значення, що призводить до колізій. Візьмемо приклад:

>>> map(hash, [0, 1, 2, 3, 4])
[0, 1, 2, 3, 4]
>>> map(hash, ['abca', 'abcb', 'abcc', 'abcd', 'abce'])
[1540938117, 1540938118, 1540938119, 1540938112, 1540938113]

Для цілих чисел хэшами є їх значення, тому що йдуть підряд числа будуть мати йдуть підряд хеши, а для рядків підряд йдуть рядки мають практично йдуть підряд хеші. Це не обов'язково погано, навпаки, в таблиці розміром 2**i взяття i молодших біт хеша як початкового індексу таблиці виконується дуже швидко, і для словників, проіндексованих послідовністю цілих чисел, колізій не буде взагалі:



Те ж саме буде майже повністю дотримуватися, якщо ключі словника — це «йдуть підряд» рядка (як у прикладі вище). В загальних випадках це дає більш ніж випадкове поведінку, що вимагається.



Взяття тільки i молодших біт хеша в якості індексу також вразливе до колізій: наприклад, візьмемо список [i << 16 for i in range(20000)] в якості набору ключів. Оскільки цілі є їх власними хэшами і це вписується в словник розміру 2**15 (так як 20000 < 32768), останні 15 біт від кожного хеша всі будуть рівні 0.

>>> map(lambda x: '{0:016b}'.format(x), [i << 16 for i in xrange(20000)])
['0000000000000000', '10000000000000000', '100000000000000000', '110000000000000000', '1000000000000000000', '1010000000000000000', '1100000000000000000', '1110000000000000000', ...]

Вийде, що всі ключі, які будуть мати один і той же індекс. Тобто для всіх ключів (крім першого) відбудуться колізії.
Приклади спеціально підібраних «поганих» випадків не повинні впливати на звичайні випадки, так що просто залишимо взяття останніх i біт. Все інше віддається на відкуп методом вирішення колізій.

Метод вирішення колізій

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

Зазвичай комірка знаходиться з першої спроби (і це дійсно так, адже коефіцієнт заповнення хеш-таблиці тримається нижче 2/3), що дозволяє не витрачати час на пробірування і робить розрахунок початкового індексу дуже швидким. Але давайте розглянемо, що станеться, якщо відбудеться колізія.

Перша частина методу вирішення колізій полягає в розрахунку індексів таблиці для пробирования з допомогою формули:

j = ((5 * j) + 1) % 2**i
Для будь-якого початкового j в межах [0..(2*i — 1)] виклик даної формули 2**i раз поверне кожне число в межах [0..(2*i — 1)] рівно один раз. Наприклад:
>>> j = 0
>>> i = 3
>>> for _ in xrange(0, 2**i):
... print j,
... j = ((5 * j) + 1) % 2**i
...
0 1 6 7 4 5 2 3

Ви скажете, що це нічим не краще використання лінійного пробирования з постійним кроком, адже в даному випадку клітинки в хеш-таблиці також переглядаються у певному порядку, але це не єдина відмінність. В загальних випадках, коли хеш значення ключів йдуть підряд, даний метод краще лінійного пробирования. З прикладу вище можна простежити, що для таблиці розміром 8 (2**3) порядок індексів буде наступним:

0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 -> ... (потім йдуть повторення)

Якщо станеться колізія для проби з індексом, рівним 5, то наступний індекс проби буде 2, а не 6, як у випадку лінійного пробирования з кроком +1, тому для ключа, який додається в майбутньому, індекс проби якого буде дорівнює 6, колізії не відбудеться. Лінійне пробірування в даному випадку (при послідовних значень ключів) було б поганим варіантом, так як відбувалося б багато колізій. Імовірність же того, що значення хеш ключів будуть йти у порядку 5 * j + 1, набагато менше.

Друга частина методу вирішення колізій полягає у використанні не тільки молодших i біт хеша, але й інших біт теж. Це реалізовано з використанням змінної perturb наступним чином:

j = (5 * j) + 1 + perturb
perturb >>= PERTURB_SHIFT
потім j % 2**i використовується як наступний індекс проби
де:
perturb = hash(key)
PERTURB_SHIFT = 5

Після цього послідовність проб буде залежати від кожного біта хеша. Псевдовипадкове зміна дуже ефективно, тому що швидко збільшує відмінності в бітах. Так як змінна perturb — беззнаковая, то, якщо пробірування виконується досить часто, мінлива perturb в кінцевому підсумку стає і залишається рівною нулю. В цей момент (який досягається дуже рідко) результат j знову стає дорівнює 5 * j + 1. Далі пошук відбувається точно так само, як у першій частині методу, і вільна клітинка в кінцевому рахунку буде знайдено, оскільки, як було сказано раніше, кожне число в діапазоні [0..(2*i — 1)] буде повернуто рівно один раз, і ми впевнені, що завжди є принаймні одна «невикористана» осередок.

Вибір «хорошого» значення для PERTURB_SHIFT — це питання балансування. Якщо зробити його малим, то старші біти хеша будуть впливати на послідовність проб по итерациям. Якщо ж зробити його великим, то дійсно «поганих» випадках старші біти хеша будуть впливати тільки на попередніх ітераціях. В результаті експериментів, які провів один з розробників Python — Тім Пітерс, значення PERTURB_SHIFT було обрано рівним 5, так як це значення виявилося «кращим». Тобто показало мінімальна загальна кількість колізій як для нормальних, так і для спеціально підібраних «поганих» випадків, хоча значення 4 і 6 не мали значно гірші.

Історична довідка: Один із розробників Python, Реймер Берендс, пропонував ідею використання підходу розрахунку індексів таблиці, заснованого на многочлени, який потім був поліпшений Крістіаном Тисмером. Цей підхід також показав відмінні результати по виникненню колізій, але вимагав більше операцій, а також додаткової змінної для зберігання многочлена таблиці в структурі PyDictObject. В експериментах Тіма Пітерса поточний, використовуваний в Python метод виявився швидше, показуючи в рівній мірі хороші результати по виникненню колізій, але вимагав менше коду і використовував менше пам'яті.

Ініціалізація словника

Коли ви створюєте словник, викликається функція PyDict_New. У цій функції послідовно виконуються наступні операції: відбувається виділення пам'яті для нового об'єкта словника PyDictObject. Змінна ma_smalltable очищається. Змінні ma_used і ma_fill прирівнюються 0, ma_table стає рівною ma_smalltable. Значення ma_mask прирівнюється PyDict_MINSIZE — 1. Функція для пошуку ma_lookup робиться рівною lookdict_string. Повертається створений об'єкт словника.

Додавання елемента

При додаванні елемента в словник або зміни значення елемента в словнику викликається функція PyDict_SetItem. У цій функції береться хеш-значення і викликається функція insertdict, а також функція dictresize, якщо таблиця заповнюється на 2/3 від поточного розміру.

У свою чергу в функції insertdict відбувається виклик lookdict_string (або lookdict, якщо у словнику є не рядковий ключ), в якій відбувається пошук вільної клітинки в хеш-таблиці для вставки. Ця ж функція використовується для знаходження ключа при витяганні.

Початковий індекс проби в цій функції розраховується як хеш ключа, поділений по модулю на розмір таблиці таким чином, відбувається взяття молодших біт хеша). Тобто:

>>> PyDict_MINSIZE = 8
>>> key = 123
>>> hash(key) % PyDict_MINSIZE
>>> 3

В Python це реалізовано з використанням логічної операції «І» та маски. Маска дорівнює наступного значення: mask = PyDict_MINSIZE — 1.

>>> PyDict_MINSIZE = 8
>>> mask = PyDict_MINSIZE - 1
>>> key = 123
>>> hash(key) & mask
>>> 3

Так виходять молодші біти хеш:
2**i = PyDict_MINSIZE, звідси i = 3, тобто достатньо трьох молодших біт.
hash(123) = 123 = 11110112
mask = PyDict_MINSIZE- 1 = 8 — 1 = 7 = 1112
index = hash(123) & mask = 11110112 & 1112 = 0112 = 3

Після того^ як індекс розрахований, виконується перевірка клітинки по індексу, і якщо вона «невикористана», то до неї додається запис (хеш, ключ, значення). Але якщо ця клітинка зайнята, з-за того, що інша запис має той же хеш (тобто сталася колізія), виконується порівняння хеша і ключ вставляється запису і запису в комірці. Якщо хеш і ключ для записів збігаються, то вважається, що запис вже існує в словнику, і виконується її оновлення.

Це пояснює хитрий момент, пов'язаний з додаванням рівних за значенням, але різних за типом ключів (наприклад, float, int і complex):

>>> 7.0 == 7 == (7+0j)
True
>>> d = {}
>>> d[7.0]='float'
>>> d
{7.0: 'float'}
>>> d[7]='int'
>>> d
{7.0: 'int'}
>>> d[7+0j]='complex'
>>> d
{7.0: 'complex'}
>>> type(d.keys()[0])
<type 'float'>

Тобто той тип, який був доданий до словника першим, і буде типом ключа, незважаючи на оновлення. Це пояснюється тим, що реалізація хеша для float значень повертає хеш від int, якщо дробова частина дорівнює 0.0. Приклад розрахунку хеша для float, переписаний на Python:

def float_hash(float_value):
...
fractpart, intpart = math.modf(float_value)
if fractpart == 0.0:
return int_hash(int(float_value)) # використовувати хеш int 
...

А хеш від complex повертає хеш від float. В даному випадку повертається хеш тільки дійсної частини, так як уявна частина дорівнює нулю:

def complex_hash(complex_value):
hashreal = float_hash(complex_value.real)
if hashreal == -1:
return -1
hashimag = float_hash(complex_value.imag)
if hashimag == -1:
return -1
res = hashreal + 1000003 * hashimag
res = handle_overflow(res)
if res == -1:
res = -2
return res

Приклад:

>>> hash(7)
7
>>> hash(7.0)
7
>>> hash(7+0j)
7

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

Зауваження з приводу додавання елементів: Python забороняє додавання елементів до словника під час ітерації, тому при спробі додати новий елемент станеться помилка:

>>> d = {'a': 1}
>>> for i in d:
... d['new item'] = 123
...
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
RuntimeError: dictionary changed size during iteration

Повернемося до процедури додавання елемента в словник. Після успішного додавання або оновлення запису в хеш-таблиці відбувається порівняння наступного запису-кандидата на вставку. Якщо хеш або ключ у записів не збігаються, починається пробірування. Відбувається пошук «невикористаної» клітинки для вставки. У даній реалізації Python використовується випадкове (а якщо змінна perturb дорівнює нулю — квадратичне) пробірування. Як було описано вище, при випадковому пробировании індекс наступної комірки вибирається псевдовипадковим чином. Запис додається в першу знайдену «невикористану» клітинку. Тобто два ключа a і b, у яких hash(a) == hash(b), a != b можуть легко існувати в одному словнику. У разі якщо комірка з початкового індексу проби «порожня», відбудеться пробірування. І якщо перша знайдена клітинка «нульова», «порожня клітинка буде використана заново. Це дозволяє перезаписати видалені клітинки, зберігаючи ще невикористані.

Виходить, що індекси додаються до словника елементів залежать від вже знаходяться в ньому елементів, і порядок ключів для двох словників, що складаються з одного і того ж набору пар (ключ, значення), може бути різним і визначається черговістю додавання елементів:

>>> d1 = {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}
>>> d2 = {'three': 3, 'two': 2, 'five': 5, 'four': 4, 'one': 1}
>>> d1 == d2
True
>>> d1.keys()
['four', 'three', 'five', 'two', 'one']
>>> d2.keys()
['four', 'one', 'five', 'three', 'two']

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

Розглянемо приклад:

>>> d = {}
>>> d['habr'] = 1



Сталася вставка з індексом 5. Змінні ma_fill і ma_used стали дорівнювати 1.

>>> d['python'] = 2



Сталася вставка з індексом 0. Змінні ma_fill і ma_used стали дорівнювати 2.

>>> d['dict'] = 3



Сталася вставка з індексом 4. Змінні ma_fill і ma_used стали дорівнювати 3.
>>> d['article'] = 4



Сталася вставка з індексом 1. Змінні ma_fill і ma_used стали дорівнювати 4.

>>> d['!!!'] = 5



Сталося наступне:
hash('!!!') = -1297030748
i = -1297030748 & 7 = 4
Але як видно з таблиці, індекс 4 вже зайнятий записом з ключем 'dict'. Тобто сталася колізія. Починається пробірування:
perturb = -1297030748
i = (i * 5) + 1 + perturb
i= (4 * 5) + 1 + (-1297030748) = -1297030727
index = -1297030727 & 7 = 1
Новий індекс проби дорівнює 1, але цей індекс теж зайнятий записом з ключем 'article'). Сталася ще одна колізія, продовжуємо пробірування:
perturb = perturb >> PERTURB_SHIFT
perturb = -1297030748 >> 5 = -40532211
i = (i * 5) + 1 + perturb
i= (-1297030727 * 5) + 1 + (-40532211) = -6525685845
index = -6525685845 & 7 = 3
Новий індекс проби дорівнює 3, і, так як він не зайнятий, відбувається вставка запису з ключем '!!!' в комірку з третім індексом. У даному випадку запис була додана після двох проб з-за сталися колізій. Змінні ma_fill і ma_used стали дорівнюють 5.

>>> d
{'python': 2, 'article': 4, '!!!': 5, 'dict': 3, 'habr': 1}

Пробуємо додати шостий елемент в словник.

>>> d[';)'] = 6



Після додавання шостого елемента таблиця буде заповнена на 2/3, а відповідно, відбудеться зміна її розміру. Після того як зміниться розмір (в даному випадку збільшиться в 4 рази), відбудеться повна перебудова хеш-таблиці з урахуванням нового розміру — всі «активні» клітинки будуть перерозподілені, а «порожні» і «невикористані» клітинки будуть проігноровані.

Розмір хеш-таблиці тепер дорівнює 32, а змінні ma_fill і ma_used стали дорівнювати 6. Як видно, порядок елементів повністю змінився:

>>> d
{'!!!': 5, 'python': 2, 'habr': 1, 'dict': 3, 'article': 4, ';)': 6}


Пошук елемента

Пошук запису в хеш-таблиці словника відбувається аналогічно, починаючи з клітинки i, де i залежить від хеш ключа. Якщо хеш і ключ не збігаються з хэшом і ключем знайденої запису (тобто була колізія і треба знайти відповідну запис) — починається пробірування, яке триває, поки не буде знайдена запис, для якої хеш і ключ збігаються. Якщо ж всі осередки були переглянуті, але запис не знайдено, повертається помилка.

>>> d = {'a': 123, 'b': 345, 'c': 678}
>>> d['x']
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
KeyError: 'x'


Коефіцієнт заповнення хеш-таблиці

Розмір таблиці змінюється, коли вона заповнюється на 2/3. Тобто для початкового розміру хеш-таблиці словника, рівного 8, зміна відбудеться після того, як буде доданий 6 елемент.

>>> 8 * 2.0 / 3
5.333333333333333

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

Значення 2/3 від розміру було обрано як оптимальний, для того щоб пробірування не займало забагато часу, тобто вставка нового запису відбувалася швидко. Збільшення цього значення призводить до того, що словник щільніше заповнюється записами, що в свою чергу збільшує кількість колізій. Зменшення ж збільшує розрідженість записів на шкоду збільшення займаних ними кеш-ліній процесора і на шкоду збільшення загального об'єму пам'яті. Перевірка заповнення таблиці відбувається в дуже чутливому до часу ділянці коду. Спроби зробити перевірку більш складною (наприклад, змінюючи коефіцієнт заповнення для різних розмірів хеш-таблиці) зменшували продуктивність.

Перевірити, що розмір словника дійсно змінюється, можна так:

>>> d = dict.fromkeys(range(5))
>>> d.__sizeof__()
248
>>> d = dict.fromkeys(range(6))
>>> d.__sizeof__()
1016

У прикладі повертається розмір об'єкта PyDictObject для 64-бітної версії ОС.
Початковий розмір таблиці дорівнює 8. Таким чином, коли число заповнених клітинок буде дорівнює 6 (тобто більше 2/3 від розміру), розмір таблиці збільшиться до 32. Потім, коли число буде дорівнює 22, збільшиться до 128. При 86 збільшиться до 512, при 342 — до 2048 і так далі.

Коефіцієнт збільшення розміру таблиці

Коефіцієнт збільшення розміру таблиці при досягненні максимального рівня заповнення дорівнює 4, якщо розмір таблиці менше 50000 елементів, і 2 — для таблиць більшого розміру. Такий підхід може бути корисний програм з обмеженнями по пам'яті.

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

Зазвичай додавання елемента до словника може збільшити його розмір в 4 або 2 рази в залежності від поточного розміру словника, але також можливо, що розмір словника зменшиться. Така ситуація може виникнути, якщо ma_fill (кількість ненульових ключів, сума «активних» і «порожніх» клітинок) набагато більше ma_used (кількість «активних» елементів), тобто багато ключів було видалене.

Видалення елемента

Видалення елемента зі словника викликається функція PyDict_DelItem.
Видалення зі словника відбувається по ключу, хоча в дійсності звільнення пам'яті не відбувається. У цій функції обчислюється хеш-значення ключа, а потім відбувається пошук запису в хеш-таблиці з використанням все тієї ж функції lookdict_string або lookdict. У разі якщо запис з таким ключем і хешем знайдена, ключ запису виставляється в стан «порожній» (тобто me_key = dummy), а значення запису NULL (me_value = NULL). Після цього змінна ma_used зменшиться на одиницю, а ma_fill залишиться без зміни. Якщо ж запис не знайдено, повертається помилка.

>>> del d['!!!']



Після видалення мінлива ma_used стала дорівнює 4, а ma_fill залишилася рівною 5, так як клітинка не була вилучена, а лише була позначена як «порожня» і продовжує займати клітинку в хеш-таблиці.

Рандомізація хешей

При запуску python можна скористатися ключем-R, щоб використовувати псевдовипадкову «сіль». У цьому випадку хеш значення таких типів, як рядки, buffer, bytes, і об'єкти datetime (date, time і datetime) будуть непередбачуваними між викликами інтерпретатора. Даний спосіб запропонований в якості захисту від DoS атак.

Посилання

github.com/python/cpython/краплі/2.7/Objects/dictobject.c
github.com/python/cpython/краплі/2.7/Include/dictobject.h
github.com/python/cpython/краплі/2.7/Objects/dictnotes.txt
www.shutupandship.com/2012/02/how-hash-collisions-are-resolved-in.html
www.laurentluce.com/posts/python-dictionary-implementation/
rhodesmill.org/brandon/slides/2010-03-pycon/
www.slideshare.net/MinskPythonMeetup/ss-26224561 — Dictionary у Python. За мотивами Objects/dictnotes.txt — SlideShare (Cyril notorca Lashkevich)
www.youtube.com/watch?v=JhixzgVpmdM — Відео доповіді «Dictionary у Python. За мотивами Objects/dictnotes.txt»

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.