Frissítse Python készségeit: A szótár vizsgálata

a hash tábla (hash map) egy olyan adatstruktúra, amely egy asszociatív tömb absztrakt adattípust valósít meg, egy struktúra, amely a kulcsokat képes leképezni az értékekre.

Ha Python szagú dict, úgy érzi magát, mint egy dict, és úgy néz ki ... nos, akkor biztosan a dict. Teljesen! Ja, és egy set...

Mi?

A Python szótárai és halmazai hash-tábla segítségével valósulnak meg. Elsőre ijesztőnek tűnhet, de mivel tovább vizsgálódunk, minden világosnak kell lennie.

Célkitűzés

Ebben a cikkben felfedezzük, hogyan dictvalósul meg az a Python-ban, és meg fogjuk építeni a saját (egyszerű) megvalósítását. A cikk három részre oszlik, és az első kettőben egyedi szótárunk épül fel:

  1. A hash táblák megértése és használata
  2. Bemerülni a Python forráskódjába, hogy jobban megértsük a szótárak megvalósítását
  3. A szótár és más adatstruktúrák, például listák és halmazok közötti különbségek feltárása

Mi az a hash asztal?

A hash tábla egy olyan szerkezet, amelyet úgy terveztek, hogy tárolja a kulcs-érték párok listáját, anélkül, hogy kompromisszumot kötne a szerkezet manipulálásának és keresésének sebességével és hatékonyságával kapcsolatban.

A hash tábla hatékonysága a hash függvényből származik - egy olyan funkcióból, amely kiszámítja a kulcs-érték pár indexét - Ez azt jelenti, hogy gyorsan beilleszthetünk, kereshetünk és eltávolíthatunk elemeket, mivel ismerjük azok indexét a memória tömbben.

A bonyolultság akkor kezdődik, amikor két kulcsunk azonos értéket kap. Ezt a forgatókönyvet hash ütközésnek hívják . Az ütközés kezelésének sokféle módja van, de csak a Python útjára térünk ki. Nem megyünk túl mélyre a hash-táblázat magyarázatával annak érdekében, hogy ez a cikk kezdőbarát és Python-központú legyen.

Győződjünk meg róla, hogy a továbbjutás előtt körbefontuk-e a hash-táblák fogalmát. Kezdjük azzal, hogy létrehozzuk a csontvázakat a nagyon (nagyon) egyszerű dict, csak beillesztési és keresési módszerekből álló szokásunkhoz , a Python néhány dunder módszerével. Inicializálnunk kell a hash táblázatot egy adott méretű listával, és engedélyeznünk kell hozzá az előfizetés ([] előjel):

A hash tábla listánknak konkrét struktúrákat kell tartalmaznia, amelyek mindegyike tartalmaz kulcsot, értéket és hash-t:

Alap példa

Egy 10 alkalmazottal rendelkező kisvállalkozás nyilvántartást szeretne vezetni az alkalmazottaik hátralévő betegnapjairól. A következő hash funkciót használhatjuk, így minden elfér a memória tömbben:

length of the employee's name % TABLE_SIZE

Határozzuk meg hash függvényünket az Entry osztályban:

Most inicializálhatunk egy 10 elemű tömböt a táblázatunkban:

Várjon! Gondoljuk át. Valószínűleg megoldunk néhány hash ütközést. Ha csak 10 elemünk van, akkor ütközés után sokkal nehezebb lesz nyitott teret találnunk. Döntsük el, hogy asztalunk dupla méretű lesz - 20 elem! Ez a jövőben hasznos lesz, ígérem.

Minden alkalmazott gyors beillesztéséhez a logikát fogjuk követni:

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

Tehát a beillesztési módszerünk a következőképpen fog kinézni (még nincs hash ütközés kezelése):

A kereséshez alapvetően ugyanezt tesszük:

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

Még nem fejeztük be!

Python ütközés kezelése

A Python az Open Addressing nevű módszert használja az ütközések kezelésére. Átméretezi a hash táblákat is, amikor elér egy bizonyos méretet, de ezt a szempontot nem tárgyaljuk. Nyissa meg a címzés definícióját a Wikipédiából:

Egy másik, nyílt címzésnek nevezett stratégiában az összes bejegyzésrekordot magában a tároló tömbben tárolja. Amikor új bejegyzést kell beilleszteni, a vödröket megvizsgálják, kezdve a hash-to slot-tól és folytatva bizonyos szonda-sorrendben , amíg egy üres foglalatot nem találnak. Bejegyzés keresésekor a vödröket ugyanabban a sorrendben vizsgálják, amíg vagy a célrekord, vagy egy nem használt tömbhely nem található, ami azt jelzi, hogy nincs ilyen kulcs a táblázatban.

Vizsgáljuk meg az érték lekérésének folyamatát keya Python forráskód (C-ben írva) segítségével:

  1. Számítsa ki a kivonatát key
  2. Számolja indexki az elemet azzal, hogy hash & maskhova mask = HASH_TABLE_SIZE-1(egyszerű szóval - vegyen N utolsó bitet a hash bitekből):
i = (size_t)hash & mask;

3. Ha üres, térjen vissza, DKIX_EMPTYami végül a következőre változik KeyError:

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

4. Ha nem üres, hasonlítsa össze a kulcsokat és kivonatokat, és állítsa be a value_addrcímet a tényleges értékre, ha megegyezik:

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

és:

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

5. Ha nem egyenlő, használja a hash különböző bitjeit (az algoritmust itt elmagyarázzuk), és folytassa ismét a 3. lépéssel:

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

Itt van egy ábra, amely szemlélteti az egész folyamatot:

A beszúrási folyamat meglehetősen hasonló - ha a megtalált nyílás üres, a bejegyzést beillesztjük, ha nem üres, akkor összehasonlítjuk a kulcsot és a kivonatot - ha egyenlő, akkor kicseréljük az értéket, és ha nem, akkor folytatjuk a keresést új hely az perturbalgoritmussal.

Ötletek kölcsönzése a Python-tól

Kölcsönvehetjük a Python ötletét, miszerint az egyes bejegyzésekhez tartozó kulcsokat és hasheket össze kell hasonlítani a bejegyzésobjektumunkkal (az előző módszer helyett):

A hash-táblázatunk továbbra sem rendelkezik ütközéskezeléssel - valósítsuk meg! Amint azt korábban láthattuk, a Python a bejegyzések összehasonlításával, majd a bitek maszkjának megváltoztatásával teszi, de a lineáris próbának nevezett módszerrel fogjuk megtenni (ami a nyitott címzés egyik formája, amelyet fentebb kifejtettünk):

Amikor a hash függvény ütközést okoz azáltal, hogy egy új kulcsot hozzárendel a hash tábla cellájához, amelyet már elfoglalt egy másik kulcs, a lineáris szondázás a táblázatban keresi a legközelebbi szabad helyet, és beilleszti az új kulcsot.

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