Улучшите свои навыки Python: изучение словаря

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

Если он пахнет Python dict, ощущается как a dictи выглядит как Python ... ну, это должно быть dict. Абсолютно! О, и setтоже ...

А?

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

Задача

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

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

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

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

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

Сложность начинается, когда два наших ключа имеют одно и то же значение. Этот сценарий называется хеш-коллизией . Есть много разных способов обработки коллизий, но мы рассмотрим только путь Python. Мы не будем слишком углубляться в объяснение нашей хеш-таблицы, чтобы эта статья была удобной для начинающих и ориентированной на Python.

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

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

Базовый пример

Небольшая компания с 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. Вычислите значение indexэлемента по hash & maskгде mask = HASH_TABLE_SIZE-1(проще говоря - возьмите N последних бит из хеш-битов):
i = (size_t)hash & mask;

3. Если пусто, верните, DKIX_EMPTYчто в конечном итоге преобразуется в KeyError:

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

4. Если не пусто, сравните ключи и хэши и установите value_addrадрес на адрес фактического значения, если он равен:

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

а также:

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

5. Если не равны, используйте разные биты хэша (алгоритм описан здесь) и снова перейдите к шагу 3:

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

Вот диаграмма, иллюстрирующая весь процесс:

Процесс вставки очень похож - если найденный слот пуст, запись вставляется, если он не пустой, мы сравниваем ключ и хеш - если они равны, мы заменяем значение, а если нет, мы продолжаем поиск новый ролик с perturbалгоритмом.

Заимствование идей из 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