Надградете своите умения на Python: Разглеждане на речника

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

Ако мирише на Python dict, чувства се като a dictи изглежда като такъв ... е, трябва да е a dict. Абсолютно! О, и setсъщо ...

А?

Речниците и наборите в Python се реализират с помощта на хеш таблица. В началото може да звучи обезсърчително, но докато разследваме допълнително, всичко трябва да е ясно.

Обективен

В тази статия ще открием как a dictсе прилага в 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. Изчислете 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