Hash tábla az adatstruktúrában: Python példa

Tartalomjegyzék:

Anonim

Mi az a hashing?

A hash egy rögzített hosszúságú érték, amelyet matematikai képlet segítségével állítanak elő. A hash értékeket az adattömörítésben, a kriptológiában stb. Használják. Az adatok indexelésénél a hash értékeket azért használják, mert rögzített hosszúságúak, függetlenül az előállításukhoz használt értékektől. A hash értékek minimális helyet foglalnak el, más, más hosszúságú értékekhez képest.

A hash függvény matematikai algoritmust alkalmaz a kulcs hash-vá alakítására. Ütközés akkor következik be, amikor egy kivonatolási funkció egynél több kivonathoz ugyanazt a kivonatolási értéket adja.

Ebben az algoritmus oktatóanyagban megtudhatja:

  • Mi az a hashing?
  • Mi az a Hash táblázat?
  • Hash funkciók
  • A jó hash funkció tulajdonságai
  • Ütközés
  • Hash tábla műveletek
  • Hash Table Python példa
  • Hash táblázat kód magyarázat
  • Python szótár példa
  • Komplexitás elemzése
  • Valós alkalmazások
  • A hash táblák előnyei
  • A hash táblák hátrányai

Mi az a Hash táblázat?

A HASH TABLE egy adatstruktúra, amely értékeket tárol pár kulcs és érték segítségével. Minden értékhez hozzárendel egy egyedi kulcsot, amelyet hash függvény segítségével állítanak elő.

A kulcs nevét a hozzá tartozó érték eléréséhez használják. Ezáltal a hash tábla értékeinek keresése nagyon gyors, függetlenül a hash tábla tételeinek számától.

Hash funkciók

Például, ha munkavállalói nyilvántartásokat akarunk tárolni, és minden alkalmazottat egyedileg azonosítunk egy alkalmazott számával.

Használhatjuk kulcsként az alkalmazotti számot, értékként pedig a munkavállalói adatokat rendelhetjük hozzá.

A fenti megközelítéshez további szabad területre lesz szükség (m * n 2 ) nagyságrendű, ahol az m változó a tömb nagysága, az n változó pedig az alkalmazott számjegyeinek száma. Ez a megközelítés tárhely problémát vet fel.

A hash függvény megoldja a fenti problémát azáltal, hogy megkapja a munkavállalói számot, és felhasználja hash egész szám előállításához, rögzített számjegyekhez és a tárhely optimalizálásához. A hash függvény célja egy kulcs létrehozása, amely a tárolni kívánt érték hivatkozására szolgál. A függvény elfogadja a menteni kívánt értéket, majd algoritmus segítségével kiszámítja a kulcs értékét.

Az alábbiakban bemutatunk egy egyszerű hash függvényt

h(k) = k1 % m

ITT,

  • h (k) az a hash függvény, amely elfogadja a k paramétert. A k paraméter az az érték, amelyhez a kulcsot ki akarjuk számítani.
  • k 1 % m a hash függvényünk algoritmusa, ahol k1 a tárolni kívánt érték, m pedig a lista mérete. A kulcs kiszámításához a modulus operátort használjuk.

Példa

Tegyük fel, hogy van egy rögzített 3-as listánk és a következő értékek

[1,2,3]

A fenti képlettel kiszámíthatjuk azokat a pozíciókat, amelyeket az egyes értékeknek el kell foglalniuk.

A következő kép a hash-táblázatunk elérhető indexeit mutatja.

1. lépés)

Számítsa ki azt a pozíciót, amelyet az első ilyen érték foglal el

h (1) = 1% 3

= 1

Az 1. érték elfoglalja az 1. index helyét

2. lépés)

Számítsa ki azt a pozíciót, amelyet a második érték foglal el

h (2) = 2% 3

= 2

A 2. érték elfoglalja a helyet a 2. indexen

3. lépés)

Számítsa ki azt a pozíciót, amelyet a harmadik érték foglal el.

h (3) = 3% 3

= 0

A 3. érték elfoglalja a 0 index helyét

Végeredmény

A kitöltött hash-táblázatunk a következő lesz.

A jó hash funkció tulajdonságai

Egy jó hash függvénynek a következő tulajdonságokkal kell rendelkeznie.

  • A kivonat előállításának képletének az algoritmusban tárolandó adatok értékét kell használnia.
  • A hash függvénynek egyedi hash értékeket kell generálnia még az azonos mennyiségű bemeneti adatokhoz is.
  • A funkciónak minimalizálnia kell az ütközések számát. Ütközések akkor fordulnak elő, ha egynél több értéknél ugyanaz az érték jön létre.
  • Az értékeket következetesen kell elosztani az összes lehetséges hash-on.

Ütközés

Ütközés akkor következik be, amikor az algoritmus ugyanazt a kivonatot generálja egynél több értékhez.

Nézzünk meg egy példát.

Tegyük fel, hogy a következő értéklista van

[3,2,9,11,7]

Tegyük fel, hogy a hash tábla mérete 7, és a képletet (k 1 % m) fogjuk használni, ahol m a hash tábla mérete.

Az alábbi táblázat a létrehozandó kivonatolási értékeket mutatja.

Kulcs Hash algoritmus (k 1 % m) Hash érték
3 3% 7 3
2 3% 7 2
9. 3% 7 2
11. 3% 7 4
7 3% 7 0

Amint a fenti eredményekből kiderül, a 2. és 9. értéknek ugyanaz a kivonatértéke, és nem tárolhatunk egynél több értéket minden egyes pozíciónál.

Az adott probléma megoldható akár láncolással, akár szondázással. A következő szakaszok részletesen tárgyalják a láncolást és a tapintást.

Láncolás

A láncolás olyan technika, amelyet az ütközés problémájának megoldására használnak összekapcsolt listák használatával, amelyek mindegyikének egyedi indexei vannak.

A következő kép azt ábrázolja, hogyan néz ki egy láncolt lista

A 2 és 9 egyaránt ugyanazt az indexet foglalja el, de összekapcsolt listákként tárolják őket. Minden listának egyedi azonosítója van.

A láncolt listák előnyei

A láncolt listák előnyei a következők:

  • A láncolt listák jobban teljesítenek az adatok beszúrásakor, mert a beszúrás sorrendje O (1).
  • Nem szükséges láncolt listát használó hash tábla átméretezése.
  • Könnyen befogadhat számos értéket, amennyiben szabad hely áll rendelkezésre.

Szondázás

Az ütközés megoldására használt másik technika a szondázás. A tapintási módszer alkalmazásakor, ha ütközés történik, egyszerűen továbbléphetünk, és egy üres rést találhatunk az értékünk tárolására.

Az alábbiak a szondázás módszerei:

Módszer Leírás
Lineáris tapintás Ahogy a neve is sugallja, ez a módszer az üres ütközéseket lineárisan keresi az ütközés helyétől kezdve és előre haladva. Ha eléri a lista végét, és nem található üres rés. A szondázás a lista elején kezdődik.
Másodlagos szondázás Ez a módszer másodfokú polinom kifejezéseket használ a következő rendelkezésre álló szabad hely megtalálásához.
Dupla hashelés Ez a technika egy másodlagos hash függvény algoritmust használ a következő szabad rendelkezésre álló rés megtalálásához.

A fenti példánkat használva a hash tábla a szondázás után a következőképpen jelenik meg:

Hash tábla műveletek

Itt vannak a Hash táblák által támogatott műveletek:

  • Beszúrás - ez a művelet egy elem hozzáadására szolgál a hash táblához
  • Keresés - ez a művelet a hash tábla elemeinek keresésére szolgál a kulcs segítségével
  • Törlés - ezzel a művelettel elemeket lehet törölni a kivonat táblából

Adatok beillesztése művelet

A beszúrási művelet értékek tárolására szolgál a hash táblában. Ha egy új értéket tárol a hash tábla, akkor indexszámot kap. Az index számát a hash függvény segítségével számítják ki. A hash függvény feloldja az indexszám kiszámításakor bekövetkező ütközéseket.

Adatkezelés keresése

A keresési műveletet az indexszám segítségével értékek keresésére használják a hash-táblában. A keresési művelet visszaadja a keresési index számához kapcsolódó értéket. Például, ha a 6 értéket a 2 indexben tároljuk, akkor a 2 indexszámú keresési művelet a 6 értéket adja vissza.

Adatok törlése művelet

A törlési művelettel értéket lehet eltávolítani a hash-táblából. A művelet törléséhez az indexszámot kell használni. Miután törölte az értéket, az indexszám szabaddá válik. A beszúrási művelettel más értékek tárolására is használható.

Hash Table implementáció Python példával

Nézzünk meg egy egyszerű példát, amely kiszámítja a kulcs kivonatolási értékét

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Hash táblázat kód magyarázat

ITT,

  1. Meghatározza a hash_key függvényt, amely elfogadja a paraméterkulcsot és az m-et.
  2. Egy egyszerű modulus műveletet használ a kivonatoló érték meghatározásához
  3. Meghatározza az m változót, amely inicializálva van a 7 értékre. Ez a hash-táblázatunk mérete
  4. Kiszámítja és kinyomtatja a 3 hash értéket
  5. Kiszámítja és kinyomtatja a 2 hash értéket
  6. Kiszámítja és kinyomtatja a 9 hash értéket
  7. Kiszámítja és kinyomtatja a 11 hash értékét
  8. Kiszámítja és kinyomtatja a 7 hash értéket

A fenti kód végrehajtása a következő eredményeket eredményezi.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Python szótár példa

A Python tartalmaz egy beépített adattípust, amelyet Szótárnak hívnak. A szótár egy kivonat táblázat példája. Értékeket tárol pár kulcs és érték segítségével. A hash értékek automatikusan generálódnak számunkra, és az esetleges ütközések megoldódnak számunkra a háttérben.

Az alábbi példa bemutatja, hogyan lehet szótár adattípust használni a Python 3-ban

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

ITT,

  1. Meghatározza a szótár változó alkalmazottját. A kulcs nevét John Doe értékének tárolására használják, az életkor 36 éves, a pozíció pedig az Business Manager értéket tárolja.
  2. Megkéri a kulcs nevének értékét és kinyomtatja a terminálban
  3. Frissíti a kulcspozíció értékét a Software Engineer értékre
  4. Kiírja a kulcsok nevének és pozíciójának értékeit
  5. Törli az összes értéket, amelyet a szótár változó alkalmazottunk tárol
  6. Kinyomtatja az alkalmazott értékét

A fenti kód futtatása a következő eredményeket eredményezi.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Komplexitás elemzése

A hash táblák átlagos időbeli összetettsége O (1) a legjobb esetben. A legrosszabb esetben az idő összetettsége O (n). A legrosszabb eset akkor fordul elő, amikor sok érték ugyanazt a kivonatkulcsot generálja, és az ütközést szondázással kell megoldanunk.

Valós alkalmazások

A való világban hash táblákat használnak az adatok tárolására

  • Adatbázisok
  • Asszociatív tömbök
  • Készletek
  • Memória gyorsítótár

A hash táblák előnyei

A hash táblák használatának előnyei / előnyei:

  • A hash táblák nagy teljesítményt nyújtanak az adatok felkutatásakor, a meglévő értékek beillesztésében és törlésében.
  • A hash táblák időbeli összetettsége állandó, függetlenül a táblázat tételeinek számától.
  • Nagy teljesítményt nyújtanak még akkor is, ha nagy adatállományokkal dolgoznak.

A hash táblák hátrányai

Itt vannak a hash táblák használatának hátrányai:

  • Nem használhat null értéket kulcsként.
  • Az ütközések nem kerülhetők el a kulcsok használatával történő létrehozásakor. hash funkciók. Ütközések akkor fordulnak elő, amikor egy már használatban lévő kulcs jön létre.
  • Ha a kivonási funkciónak sok ütközése van, ez a teljesítmény csökkenéséhez vezethet.

Összegzés:

  • A hash táblákat kulcsok és értékek segítségével tárolják az adatok.
  • A hash függvény matematikai algoritmust használ a hash érték kiszámításához.
  • Ütközés akkor következik be, ha ugyanazon kivonatérték több mint egy értéknél jön létre.
  • A lánc összekapcsolt listák létrehozásával oldja meg az ütközést.
  • A szondázás úgy oldja meg az ütközést, hogy üres réseket talál a hash-táblában.
  • Lineáris tapintással keresi a következő szabad rést, hogy tárolja az értéket attól a ponttól kezdődően, ahol az ütközés történt.
  • A másodfokú szondázás polinom kifejezésekkel keresi meg a következő szabad helyet, ha ütközés történik.
  • A dupla hash egy másodlagos hash függvény algoritmust használ a következő szabad hely megtalálásához, ha ütközés történik.
  • A hash táblák jobb teljesítményt nyújtanak más adatszerkezetekhez képest.
  • A hash táblák átlagos időbonyolultsága O (1)
  • A szótár adattípusa a pythonban egy kivonat táblázat példája.
  • A hash táblák támogatják a beszúrási, keresési és törlési műveleteket.
  • A null érték nem használható indexértékként.
  • Az ütközések nem kerülhetők el a hash funkciókban. A jó hash funkció minimalizálja az ütközések számát a teljesítmény javítása érdekében.