Оновіть свої навички Python: вивчення словника

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

Якщо він пахне Python dict, відчуває себе як dictі виглядає як ... ну, це повинен бути a dict. Абсолютно! О, і setтеж ...

А?

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

Об’єктивна

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

  1. Розуміння того, що таке хеш-таблиці та як ними користуватися
  2. Пориньте у вихідний код Python, щоб краще зрозуміти, як реалізуються словники
  3. Вивчення відмінностей між словником та іншими структурами даних, такими як списки та набори

Що таке хеш-таблиця?

Хеш-таблиця - це структура, призначена для зберігання списку пар ключ-значення, без шкоди для швидкості та ефективності маніпулювання та пошуку структури.

Ефективність хеш-таблиці походить від хеш-функції - функції, яка обчислює індекс пари ключ-значення - Це означає, що ми можемо швидко вставляти, шукати та видаляти елементи, оскільки ми знаємо їх індекс у масиві пам'яті.

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

Давайте переконаємось, що перед тим, як рухатись далі, ми обгорнули концепцію хеш-таблиць. Ми почнемо з того dict, що створимо скелети для нашого дуже (дуже) простого настрою, що складається лише із методів вставки та пошуку, використовуючи деякі методи дундера Python. Нам потрібно буде ініціалізувати хеш-таблицю зі списком певного розміру та ввімкнути підписку (знак []) для неї:

Тепер наш список хеш-таблиць повинен містити певні структури, кожна з яких містить ключ, значення та хеш:

Основний приклад

Невелика компанія з 10 співробітниками хоче вести записи, що містять дані про працівників, які залишаються хворими. Ми можемо використовувати наступну хеш-функцію, щоб усе могло поміститися в масив пам'яті:

length of the employee's name % TABLE_SIZE

Давайте визначимо нашу хеш-функцію в класі Entry:

Тепер ми можемо ініціалізувати масив із 10 елементів у нашій таблиці:

Чекай! Давайте все обдумаємо. Швидше за все, ми вирішимо деякі хеш-колізії. Якщо у нас лише 10 елементів, нам буде набагато складніше знайти відкритий простір після зіткнення. Давайте вирішимо, що наша таблиця матиме подвійний розмір - 20 елементів! Обіцяю, це стане в нагоді в майбутньому.

Щоб швидко вставити кожного працівника, ми будемо слідувати логіці:

array[length of the employee's name % 20] = employee_remaining_sick_days

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

Для пошуку ми в основному робимо те ж саме:

array[length of the employee's first name % 20] 

Ми ще не закінчили!

Обробка зіткнень Python

Python використовує метод, що називається Open Addressing, для обробки колізій. Він також змінює розмір хеш-таблиць, коли він досягає певного розміру, але ми не будемо обговорювати цей аспект. Відкрите визначення адресації з Вікіпедії:

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

Давайте розглянемо процес отримання значення за keyдопомогою перегляду вихідного коду Python (написаного на C):

  1. Обчислити хеш key
  2. Calculate the index of the item by hash & mask where mask = HASH_TABLE_SIZE-1 (in simple terms - take N last bits from the hash bits):
i = (size_t)hash & mask;

3. If empty, return DKIX_EMPTY which translates eventually to a KeyError:

if (ix == DKIX_EMPTY) { *value_addr = NULL; return ix;}

4. If not empty, compare keys & hashes and set value_addr address to the actual value address if equal:

if (ep->me_key == key) { *value_addr = ep->me_value; return ix;}

and:

if (dk == mp->ma_keys && ep->me_key == startkey) { if (cmp > 0) { *value_addr = ep->me_value; return ix; }}

5. If not equal, use different bits of the hash (algorithm explained here) and go to step 3 again:

perturb >>= PERTURB_SHIFT;i = (i*5 + perturb + 1) & mask;

Here’s a diagram to illustrate the whole process:

The insertion process is pretty similar — if the found slot is empty, the entry is being inserted, if it’s not empty then we compare the key and the hash — if equal, we replace the value, and if not we continue our quest of finding a new spot with the perturb algorithm.

Borrowing ideas from Python

Ми можемо запозичити ідею Python про порівняння обох ключів і хешів кожного запису з нашим об'єктом введення (замінюючи попередній метод):

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

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

So what we’re going to do is to move forward until we find an open space. If you recall, we implemented our table with double the size (20 elements and not 10) — This is where it comes handy. When we move forward, our search of an open space will be much quicker because there’s more room!

But we have a problem. What if someone evil tries to insert the 11th element? We need to raise an error (we won’t be dealing with table resizing in this article). We can keep a counter of filled entries in our table:

Now let’s implement the same in our searching method:

The full code can be found here.

Now the company can safely store sick days for each employee:

Python Set

Going back to the beginning of the article, set and dict in Python are implemented very similarly, with set using only key and hash inside each record, as can be seen in the source code:

typedef struct { PyObject *key; Py_hash_t hash; /* Cached hash code of the key */} setentry;

As opposed to dict, that holds a value:

typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */} PyDictKeyEntry;

Performance and Order

Time comparison

I think it’s now clear that a dict is much much faster than a list (and takes way more memory space), in terms of searching, inserting (at a specific place) and deleting. Let's validate that assumption with some code (I am running the code on a 2017 MacBook Pro):

And the following is the test code (once for the dict and once for the list, replacing d):

The results are, well, pretty much what we expected..

dict: 0.015382766723632812 seconds

list:55.5544171333313 seconds

Order depends on insertion order

The order of the dict depends on the history of insertion. If we insert an entry with a specific hash, and afterwards an entry with the same hash, the second entry is going to end up in a different place then if we were to insert it first.

Before you go…

Thanks for reading! You can follow me on Medium for more of these articles, or on GitHub for discovering some cool repos :)

If you enjoyed this article, please hold down the clap button ? to help others find it. The longer you hold it, the more claps you give!

And do not hesitate to share your thoughts in the comments below, or correct me if I got something wrong.

Additional resources

  1. Hash Crash: The Basics of Hash Tables
  2. The Mighty Dictionary
  3. Introduction to Algorithms