Ebben az oktatóanyagban megtudhatja, mi az a hashing.
A hashing egy tetszőleges adatok nagy halmazának táblázatos indexekbe történő leképezésének technikája hash függvény segítségével. Ez egy módszer nagy adatkészletek szótárainak ábrázolására.
Lehetővé teszi a keresés, a frissítés és a visszakeresés műveletét állandó idő alatt, azaz O(1)
.
Miért van szükség hasításra?
Nagy mennyiségű adat tárolása után különféle műveleteket kell végrehajtanunk ezeken az adatokon. A keresések elkerülhetetlenek az adatkészletek számára. A lineáris keresés és a bináris keresés időbeli bonyolultsággal O(n)
és / vagy kereséssel végez keresést O(log n)
. Az adatkészlet méretének növekedésével ezek a bonyolultságok is jelentősen megnőnek, ami nem elfogadható.
Olyan technikára van szükségünk, amely nem függ az adatok méretétől. A hashelés lehetővé teszi, hogy a keresések állandó időben történjenek, azaz O(1)
.
Hash funkció
Hash függvényt használnak az adatkészlet minden elemének a táblázat indexeihez való hozzárendeléséhez.
A hash-tábláról, az ütközés-elhárítási technikákról és a hash-funkciókról további információt a Hash Table oldalon talál.