Kód nélküli útmutató a hash és hash asztalokhoz

Ha korábban programozott, akkor biztosan találkozott hash és hash táblákkal. Sok fejlesztő használt hash táblákat ilyen vagy olyan formában, és a kezdő fejlesztőknek meg kell tanulniuk ezt az alapvető adatstruktúrát. Csak egy probléma van:

Minden oktatóanyag, amellyel találkozik, biztosan megvitatja a hash és a hash táblákat JavaScriptben, Pythonban vagy más programozási nyelven.

Ez azt jelenti, hogy talán megért egy kicsit a hash működésével és a hash tábla használatával [beillesztendő nyelv itt], de hiányozhat a működésének elve.

Nem lenne jó, ha egy adott nyelv ismerete nélkül megismerhetnénk a hash-t? Ha tudja, hogyan működik a hash, és mi a hash tábla, akkor a nyelvnek nem szabad számítania.

Ez a kód nélküli megközelítés, és ebben a bejegyzésben mindent megtanítok a hash és a hash táblákra, függetlenül attól, hogy melyik programozási nyelvet használja jelenleg. Akár junior, akár idősebb fejlesztő vagy, mindenki megtanul valamit ebből a bejegyzésből.

Tehát mi a hash funkció?

Mielőtt belekezdenénk az összes divatos dologba, hadd mondjam el, mi a hash. Könnyítsük meg, hogy képzeljük el, hogy van egy fekete dobozunk:

Ez a fekete doboz különleges. Funkciódoboznak hívják. Funkciódoboznak fogjuk nevezni, mert ez a mező a bemenet független változóját hozzárendeli a kimenet függő változójához (matyásnak tűnik, de viseljen).

A funkciódobozunk így működik: ha betűt teszünk a dobozba, akkor számot kapunk. Mivel a dobozunk egy függvénydoboz, a doboz minden bemenetéhez csak egy kimenet lehet.

Funkciómezőnk egy betűt vesz AJ-től a bemeneten, és a megfelelő számot 0-tól 9-ig adja ki a kimeneten. Tehát ha C-t adunk meg, akkor 2-et kapunk a kimeneten.

Ez képezi az alapjait annak, hogy mi a hash függvény. A hash funkció azonban egy lépéssel tovább lép. A bemenet adatait leképezzük a kimenet valamely numerikus értékére, általában hexadecimális szekvenciára.

Tehát lényegében minden kivonatolás az, hogy egy függvény segítségével adatokat reprezentál egy reprezentatív numerikus vagy alfanumerikus értékre. A hash függvény esetében a bemenet méretétől függetlenül a kimenet mindig ugyanaz marad.

Mi a helyzet a hash asztalokkal?

Tehát ezen a ponton felmerülhet a kérdés, hogy mi az a hash asztal. A hash-táblák a kivonatot használják az adatstruktúra kialakításához.

A hashtáblák asszociatív módszerrel tárolják az adatokat az úgynevezett kulcsérték-keresőrendszer használatával. Ez csak annyit jelent, hogy a kivonat táblában a kulcsok egyedi értékekhez vannak hozzárendelve.

Ez az adatszervezési rendszer nagyon gyors módszert eredményez az adatok hatékony megtalálásához. Ennek oka, hogy mivel minden kulcs egyedi értékhez van hozzárendelve - ha megismerünk egy kulcsot, akkor azonnal megtalálhatjuk a hozzá tartozó értéket.

A hashtáblák rendkívül gyorsak, időbeli összetettségük O (1) nagyságrendű.

Zavaros? Vessen egy pillantást erre a diagramra, ahol több funkciódobozunk készít kivonatolási értékeket.

Ebben a forgatókönyvben a bemenet minden karakterén (mindegyik kulcs) hash függvény van alkalmazva, és a funkció mezőben található hash függvény generálja a kivonatolási értéket. Ezt a kapott értéket ezután hozzárendeli egy indexhez az alapul szolgáló összekapcsolt listában vagy tömbben, amelyet a hash tábla megvalósításához használnak.

A kapott szerkezet így fog kinézni:

Hash ütközések

Itt az alkalom arra, hogy beszéljünk az ütközésről a hash függvényekben és a hash táblákban.

A matematika egyik funkciója ideális abban az esetben, ha a bemenetben lévő elem pontosan a kimenet egy eleméhez van hozzárendelve.

Hash függvényben azonban nem mindig ilyen. Előfordul, hogy a bemenet különböző hash értékei ugyanazt a hash értéket eredményezik a kimenetben. Amikor ez megtörténik, akkor kap egy úgynevezett hash ütközést.

A hash ütközések a legtöbb használati esetben nem túl gyakoriak, mivel a bemenet kicsi változása drámai módon eltérő kimenetet eredményezhet. De minél több adatot kell bevinnie a hash függvénybe, annál valószínűbb az ütközés.

A korábban megadott hash tábla példában feltételeztük, hogy egy tömböt használtak a hash tábla megvalósításához. Bár ez egyszerű hash táblákra jó, a gyakorlatban ezek nem túl jóak az ütközések kezelésére.

Mint ilyen, a láncolás néven ismert módszert alkalmazzák. A láncolás során, ha a hash tábla ugyanazon hash értéket adja vissza több elem esetében, akkor egyszerűen "láncoljuk" az elemeket ugyanazokkal a hash értékekkel együtt a hash tábla ugyanazon indexén.  

Így ahelyett, hogy indexként tömbként valósítanánk meg, a kivonatoló táblázatot egy összekapcsolt lista segítségével valósítjuk meg, ahol minden elem lista, nem pedig csak egyetlen érték van hozzárendelve.

De ahogy a lánc hossza növekszik, a hash-tábla időbeli bonyolultsága romolhat. Nyílt címzés néven ismert módszert is alkalmaznak. Ebben alternatív helyek találhatók a hash táblázatot megvalósító mögöttes adatstruktúrában. Csak ne feledje, hogy ez a módszer csökkenti a hash tábla hatékonyságát, és rosszabb az idő bonyolultsága.

A hashás ugyanaz, mint a titkosítás vagy a kódolás?

Sokan hajlamosak a hasítást a titkosítással vagy a kódolással társítani. Tehát a hash titkosítás? Ugyanaz, mint a kódolás?

A titkosításban zavarjuk az adatokat, hogy csak azok férhessenek hozzá, akik rendelkeznek az adatok visszafejtéséhez szükséges kulccsal. Ha egy titkosító titkosítást használunk, akkor nemcsak titkosítjuk az adatokat, hanem valamikor meg akarjuk dekódolni az adatokat is. Titkosításban vissza akarjuk állítani az eredeti adatokat.

A hashing viszont adatokat vesz fel és kimenetet állít elő az adatok integritásának megerősítése céljából. A hamisítás során nem áll szándékunkban helyreállítani az eredeti adatokat.

A kódolás abban különbözik a titkosítástól és a kivonatolástól, hogy a kódolás célja nem az adatok elfedése bármilyen biztonsági célból, hanem csupán az adatok konvertálása olyan formátumba, amelyet egy másik rendszer használhat.

Mit tehetek hash-zással?

A hash-eket és a hash-táblákat számos felhasználási lehetőséggel lehet használni! Ezek tartalmazzák:

  1. Cryptosystems
  2. Ciklikus redundancia-ellenőrzések
  3. Kereső motorok
  4. Adatbázisok
  5. Összeállítók

Vagy bármely olyan rendszer, amelynek összetett keresési folyamata van.

Csomagolás

Ebben a bejegyzésben áttekintettük a hashelés alapjait, mindezt egyetlen kódsor megírása nélkül! Ez könnyű volt, igaz? A kód nélküli megközelítés sokkal könnyebb módja ezeknek az alapvető témáknak a megismerésében.

Megtudtuk, hogy a hash függvényekkel objektumok alakíthatók át rögzített hosszúságú alfanumerikus kimenetté. Megtudtuk azt is, hogy a hash táblák kulcsérték-kereső rendszerek, és bár jól működnek, nem tökéletesek, és néha ütközésekben szenvednek.

A bejegyzés végére ismernie kell a különbséget a hash, a titkosítás és a kódolás között, és meg kell tudnia, hogy hol használhatók a hashek.

Tetszett a kód nélküli megközelítés? Szeretne továbbmenni?

Tudjon meg többet a hash táblákról és más adatstruktúrákról és algoritmusokról a "Kód nélküli adatszerkezetek és algoritmusok" című könyvben. Kiterjesztést kap arról, amit ez a bejegyzés tartalmazott, és még sok más témáról tudhat meg mindent, egyetlen kódsor megírása nélkül!

Kód nélküli adatszerkezetek és algoritmusok - Ismerje meg a DSA-t egyetlen kódsor megírása nélkül | Armstrong Subero | Apress Ez a könyv új, teljesen kód nélküli nézőpontot kínál az algoritmusok és adatstruktúrák számára. Tudjon meg többet az adatszerkezeti algoritmusokról (DSA) anélkül, hogy bármikor meg kellene nyitnia a kódszerkesztőt, fordítót kellene használnia, vagy meg kellene néznie az integrált fejlesztői környezetet (IDE). Bejelentkezés fiókKönyvespolc Bejelentkezés Apress Access