Hash táblázat az adatstruktúrában: Python Példa

Mi az a Hashing?

A hash egy rögzített hosszúságú érték, amelyet egy matematikai képlet segítségével állítanak elő. A hash értékeket adattömörítésben, kriptológiában stb. használják. Az adatindexelésben a hash értékeket használjuk, mert rögzített hosszúságúak, függetlenül a generálásukhoz használt értékektől. Lehetővé teszi, hogy a hash értékek minimális helyet foglaljanak el más, változó hosszúságú értékekkel összehasonlítva.

A hash függvény egy matematikai algoritmust alkalmaz a kulcs hash-lé alakítására. Ütközés akkor következik be, ha egy hash függvény ugyanazt a hash értéket állítja elő több kulcshoz.

Mi az a hash-tábla?

A HASH TÁBLÁZAT egy olyan adatstruktúra, amely kulcs- és értékpár használatával értékeket tárol. Minden értékhez egyedi kulcs van hozzárendelve, amelyet egy hash függvény segítségével állítanak elő.

A kulcs neve a hozzá tartozó érték elérésére szolgál. Ez nagyon felgyorsítja az értékek keresését a hash táblában, függetlenül a hash táblában lévő elemek számától.

Hash funkciók

Például, ha az alkalmazottak nyilvántartásait szeretnénk tárolni, és minden alkalmazott egyedileg azonosítható egy alkalmazotti szám segítségével.

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

A fenti megközelítés további nagyságrendű szabad területet igényel (m * n²) ahol az m változó a mérete sor, az n változó pedig az alkalmazotti szám számjegyeinek száma. Ez a megközelítés tárhelyproblémát vezet be.

A hash függvény megoldja a fenti problémát azáltal, hogy lekéri az alkalmazotti számot, és ennek segítségével generál egy hash egész értéket, rögzített számjegyeket, és optimalizálja a tárhelyet. A hash függvény célja egy kulcs létrehozása, amely a tárolni kívánt értékre hivatkozik. A függvény elfogadja a mentendő értéket, majd egy algoritmus segítségével kiszámítja a kulcs értékét.

A következő egy példa egy egyszerű hash függvényre

h(k) = k1 % m

ITT,

• h(k) az a hash függvény, amely elfogad egy k paramétert. A k paraméter az az érték, amelyhez a kulcsot ki szeretnénk számítani.
• k₁ % 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 listánk, amelynek fix mérete 3 és a következő értékek

[1,2,3]

A fenti képlet segítségével kiszámíthatjuk, hogy az egyes értékeknek milyen pozíciókat kell elfoglalniuk.

A következő kép a hash táblázatunkban elérhető indexeket mutatja.

Step 1) Számítsa ki azt a pozíciót, amelyet az első érték így fog elfoglalni

h(1) = 1 % 3

= 1

Az érték 1 fog elfoglalni a hely tovább index 1

Step 2) Számítsa ki azt a pozíciót, amelyet a második érték fog elfoglalni

h(2) = 2 % 3

= 2

Az érték 2 fog elfoglalni a hely tovább index 2

Step 3) Számítsa ki azt a pozíciót, amelyet a harmadik érték fog elfoglalni.

h(3) = 3 % 3

= 0

Az érték 3 fog elfoglalni a hely tovább index 0

Végeredmény

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

A jó hash függvény tulajdonságai

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

• A hash generálására szolgáló képletnek az algoritmusban tárolandó adatértéket 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 minimálisra kell csökkentenie az ütközések számát. Ütközések akkor fordulnak elő, ha ugyanazt az értéket egynél több értékhez állítják elő.
• Az értékeket következetesen kell elosztani a lehetséges kivonatok között.

ütközés

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

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

Tegyük fel, hogy a következő értéklistával rendelkezünk

[3,2,9,11,7]

Tegyük fel, hogy a hash tábla mérete 7, és a (k₁ % m) ahol m a hash tábla mérete.

A következő táblázat a létrehozandó hash értékeket mutatja be.

Kulcs	Hash algoritmus (k1 % 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 láthatjuk, a 2-es és 9-es érték azonos hash-értékkel rendelkezik, és nem tárolhatunk egynél több értéket minden pozícióban.

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

Láncolás

A láncolás egy olyan technika, amelyet az ütközés problémájának megoldására használnak olyan összekapcsolt listák használatával, amelyek mindegyike egyedi indexekkel rendelkezik.

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

Mind a 2, mind a 9 ugyanazt az indexet foglalja el, de csatolt listákként tárolódnak. 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 jobb teljesítményt nyújtanak adatok beszúrásakor, mivel a beszúrás sorrendje O(1).
• A láncolt listát használó hash táblát nem szükséges átméretezni.
• Könnyedén képes befogadni nagyszámú értéket, amíg van szabad hely.

Szondázás

A másik technika, amelyet az ütközés feloldására használnak, a szondázás. A szondázási módszer használatakor, ha ütközés történik, egyszerűen továbbléphetünk, és találhatunk egy üres helyet az értékünk tárolására.

A szondázási módszerek a következők:

Módszer	Leírás
Lineáris tapintás	Ahogy a név is sugallja, ez a módszer az ütközés helyétől kezdve lineárisan keresi az üres réseket, és halad előre. Ha a lista végére értünk, és nem található üres hely. A szondázás a lista elején kezdődik.
Másodlagos szondázás	Ez a módszer másodfokú polinomiális kifejezéseket használ a következő szabad slot megtalálásához.
Double hashelés	Ez a technika egy másodlagos hash függvény algoritmust használ a következő szabad hely 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 fog megjelenni:

Hash tábla műveletek

Itt van a OperaA hash táblák által támogatott lehetőségek:

• beszúrás - ezt Operation egy elem hozzáadására szolgál a hash táblához
• Kutató - ezt Operation segítségével kereshet elemeket a hash táblában a kulcs segítségével
• törlése - ezt Operation elemekkel törölhető a hash táblából

Adatbeviteli művelet

A beszúrási művelet az értékek tárolására szolgál a hash táblában. Ha új értéket tárol a hash táblában, akkor indexszámot kap. Az indexszám kiszámítása a hash függvény segítségével történik. A hash függvény felold minden ütközést, amely az indexszám kiszámításakor fordul elő.

Adatművelet keresése

A keresési művelet a hash táblában lévő értékek megkeresésére szolgál az indexszám segítségével. A keresési művelet azt az értéket adja vissza, amely a keresési indexszámhoz van kapcsolva. Például, ha a 6-os értéket a 2-es indexen tároljuk, a 2-es indexszámú keresési művelet a 6-os értéket adja vissza.

Adatok törlése művelet

A törlési művelet egy érték eltávolítására szolgál egy hash táblából. Törölni a Operaaz indexszám használatával történik. Az érték törlése után az indexszám szabaddá válik. Más értékek tárolására használható a beszúrási művelet segítségével.

Hash tábla megvalósítása Python Példa

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

def hash_key( key, m):
    return key % m


m = 7

print(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ábla kód magyarázata

ITT,

1. Hash_key függvényt határoz meg, amely elfogadja a kulcs és m paramétereket.
2. Egy egyszerű modulus műveletet használ a hash érték meghatározásához
3. Meghatároz egy m változót, amely 7-es értékre inicializálódik. Ez a hash táblánk mérete
4. Kiszámolja és kiírja a 3-as hash értékét
5. Kiszámolja és kiírja a 2-as hash értékét
6. Kiszámolja és kiírja a 9-as hash értékét
7. Kiszámolja és kiírja a 11-as hash értékét
8. Kiszámolja és kiírja a 7-as hash értékét

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

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

Python Példa szótárhoz

Python egy szótár nevű beépített adattípussal érkezik. A szótár egy példa a hash-táblázatra. Az értékeket kulcs- és értékpár segítségével tárolja. A hash értékek automatikusan generálódnak számunkra, és az esetleges ütközéseket a rendszer a háttérben oldja meg helyettünk.

A következő példa bemutatja, hogyan használhat szótári adattípust Python 3

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. Egy szótári változót határoz meg. A kulcsnév a John Doe érték tárolására szolgál, az életkor 36 évet, a pozíció pedig a Business Manager értéket tárolja.
2. Lekéri a kulcsnév értékét, és kiírja a terminálba
3. Frissíti a kulcspozíció értékét a Szoftvermérnök értékre
4. Kinyomtatja a billentyűk nevének és pozíciójának értékeit
5. Törli az alkalmazott szótárváltozóban tárolt összes értéket
6. Kiírja az alkalmazott értékét

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

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őbonyolultsága O (1) a legjobb forgatókönyv szerint. A legrosszabb eset bonyolultsága O(n). A legrosszabb forgatókönyv akkor fordul elő, ha sok érték generálja ugyanazt a hash kulcsot, és az ütközést vizsgálással kell megoldanunk.

Valós alkalmazások

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

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

A hash táblák előnyei

Íme a hash táblák használatának előnyei/előnyei:

• A hash-táblázatok nagy teljesítményt nyújtanak az adatok keresésekor, a meglévő értékek beszúrásakor és törlésekor.
• A hash táblák időbonyolultsága állandó, függetlenül a táblázat elemeinek számától.
• Nagyon jól teljesítenek még akkor is, ha nagy adatkészletekkel dolgoznak.

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

Íme 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 kulcsok generálásakor. hash függvények. Ütközés akkor következik be, amikor egy már használatban lévő kulcs generálódik.
• Ha a kivonatoló függvénynek sok ütközése van, ez a teljesítmény csökkenéséhez vezethet.

Összegzésként

• A hash táblák az adatok tárolására szolgálnak kulcs- és értékpár használatával.
• A hash függvény egy matematikai algoritmust használ a hash érték kiszámításához.
• Ütközés akkor következik be, ha egynél több értékhez ugyanaz a hash érték jön létre.
• A láncolás az ütközést az összekapcsolt listák létrehozásával oldja meg.
• A szondázás úgy oldja meg az ütközést, hogy üres réseket talál a hash táblában.
• A lineáris tapintás megkeresi a következő szabad slotot, hogy eltárolja az értéket attól a réstől kezdve, ahol az ütközés történt.
• A másodfokú szondázás polinomiális kifejezéseket használ a következő szabad rés megtalálásához, ha ütközés történik.
• Double A hash egy másodlagos hash függvény algoritmust használ, hogy ütközés esetén megtalálja a következő szabad slotot.
• A hash táblák jobb teljesítményt nyújtanak más adatstruktúrákhoz képest.
• A hash táblák átlagos időbonyolultsága O (1)
• A python szótáradattípusa egy példa a hash-táblázatra.
• A hash táblák támogatják a beszúrási, keresési és törlési műveleteket.
• Null érték nem használható indexértékként.
• Az ütközések nem kerülhetők el a hash függvényekben. A jó hash függvény minimalizálja az ütközések számát a teljesítmény javítása érdekében.