streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban figyelembe vesszük a különböző adatstruktúrákban használt hash technikákat, amelyek állandó időtartamú hozzáférést biztosítanak elemeikhez.

Részletesebben tárgyaljuk az ún hajtogatási technika és rövid bemutatást ad a középső négyzet és az ütés technikáiról.

2. Áttekintés

Amikor az adatstruktúrákat választjuk az objektumok tárolásához, az egyik szempont az, hogy gyorsan hozzáférnünk kell-e hozzájuk.

A Java segédprogramcsomag meglehetősen sok adatstruktúrát kínál számunkra az objektumaink tárolásához. Az adatstruktúrákról további információt a Java Gyűjtemények összeállítási oldalunkon talál, amelyek többjükön útmutatókat tartalmaznak.

Mint tudjuk, ezen adatstruktúrák némelyike ​​lehetővé teszi számunkra az elemek állandó időben történő lekérését, függetlenül az általuk tartalmazott elemek számától.

Valószínűleg a legegyszerűbb a tömb. Valójában a tömb elemeihez indexük alapján férünk hozzá. A hozzáférési idő természetesen nem a tömb méretétől függ. Valójában a színfalak mögött sok adatstruktúra erősen használja a tömböket.

A probléma az, hogy a tömbindexeknek numerikusaknak kell lenniük, míg ezeket az adatszerkezeteket gyakran inkább objektumokkal kezeljük.

Ennek a problémának a megoldása érdekében sok adatstruktúra numerikus értéket próbál meg rendelni, amely tömbindexként szolgálhat az objektumok számára. Ezt az értéket hívjuk a-nak hash érték vagy egyszerűen a hash.

3. Hash

A hashelés egy objektum átalakítása numerikus értékké. Az ezeket az átalakításokat végrehajtó függvényeket hívjuk hash funkciók.

Az egyszerűség kedvéért vegyük figyelembe a hash függvényeket, amelyek a húrokat tömbindexekké, azaz egész tartományokká alakítják át a tartományból [0, N] véges N.

Természetesen, a hash függvényt sokféle húrra alkalmazzák. Ezért „globális” tulajdonságai fontossá válnak.

Sajnos nem lehetséges, hogy a hash függvény mindig különböző karakterláncokat alakít át különböző számokká.

Elég könnyen meggyőzhetjük magunkat arról, hogy a húrok száma sokkal nagyobb, mint az egész számok bármely tartományban [0, N]. Ezért elkerülhetetlen, hogy létezzen egy pár nem egyenlő karakterlánc, amelynek hash függvénye egyenlő értékeket eredményez. Ezt a jelenséget ún ütközés.

Nem fogunk belemerülni a kivonatoló funkciók mögötti mérnöki részletekbe, de nyilvánvaló, hogy egy jó hash függvénynek megpróbálnia egységesen feltérképezni azokat a karakterláncokat, amelyeken számokba van meghatározva.

Egy másik nyilvánvaló követelmény, hogy a jó hash funkciónak gyorsnak kell lennie. Ha túl sok időbe telik a kivonatolási érték kiszámítása, akkor nem tudjuk gyorsan elérni az elemeket.

Ebben az oktatóanyagban a következők egyikét vesszük figyelembe technikák, amelyek megpróbálják egységessé tenni a térképezést miközben gyorsan fenntartja.

4. Összecsukható technika

Célunk olyan funkció megtalálása, amely a húrokat tömbindexekké alakítja. Csak az ötlet szemléltetésére tegyük fel, hogy azt akarjuk, hogy ez a tömb képes legyen 105 elemre, és használjuk a stringet Java nyelv mint például.

4.1. Leírás

Kezdjük azzal, hogy a karakterlánc karaktereit számokká konvertáljuk. Az ASCII jó jelölt erre a műveletre:

Most az imént kapott számokat bizonyos méretű csoportokba rendezzük. Általában a csoport méretét a tömbünk mérete alapján választjuk meg, amely 105. Mivel azok a számok, amelyekbe a karaktereket átalakítottuk, két-három számjegyet tartalmaznak, az általánosság elvesztése nélkül, beállíthatjuk a csoport méretét kettő:

A következő lépés az egyes csoportok számainak összefűzése, mintha húrok lennének, és megtalálja az összegüket:

Most meg kell tennünk az utolsó lépést. Ellenőrizzük, hogy a szám 348933 a 105-ös tömbünk indexeként szolgálhat. Természetesen meghaladja a megengedett legnagyobb értéket 99999. Ezt a problémát könnyen leküzdhetjük a modulo operátor alkalmazásával, hogy megtaláljuk a végeredményt:

348933 % 10000 = 48933

4.2. Záró megjegyzések

Látjuk, hogy az algoritmus nem tartalmaz időigényes műveleteket, ezért meglehetősen gyors. Az input karakterlánc minden karaktere hozzájárul a végeredményhez. Ez a tény határozottan segít az ütközések csökkentésében, de nem azok teljes elkerülésében.

Például, ha ki akartuk hagyni a hajtogatást, és a modulo operátort közvetlenül az ASCII-transzformált bemeneti karakterláncra alkalmaztuk (figyelmen kívül hagyva a túlcsordulási problémát)

749711897321089711010311797103101 % 100000 = 3101

akkor egy ilyen hash függvény ugyanazt az értéket állítja elő minden olyan karaktersorozat esetében, amelynek ugyanaz az utolsó két karaktere van, mint a bemeneti karakterláncunknak: ageokor, large, stb.

Az algoritmus leírásából könnyen beláthatjuk, hogy nem mentes az ütközésektől. Például az algoritmus ugyanazt a kivonatolási értéket állítja elő Java nyelv és vaJa nyelv húrok.

5. Egyéb technikák

A hajtogatási technika meglehetősen gyakori, de nem az egyetlen. Néha a binning vagy négyzet közepe technikák is hasznosak lehetnek.

Az ő ötletüket úgy szemléltetjük, hogy nem karakterláncokat, hanem számokat használunk (tegyük fel, hogy a húrokat már valahogyan átalakítottuk számokká). Nem tárgyaljuk előnyeiket és gyengeségeiket, de véleményt alkothat az algoritmusok megtekintése után.

5.1. Binning technika

Tegyük fel, hogy 100 egész számunk van, és azt akarjuk, hogy a hash függvényünk 10 elem tömbjébe térképezze fel őket. Ezután egyszerűen elrendezhetjük ezt a 100 egész számot tíz csoportba oly módon, hogy az első tíz egész szám az első kukába, a második tíz egész a második kukába kerül stb.:

5.2. Középtéri technika

Ezt az algoritmust John von Neumann javasolta, és ez lehetővé teszi számunkra, hogy egy adott számból kiindulva ál-véletlenszerű számokat állítsunk elő.

Szemléltessük egy konkrét példán. Tegyük fel, hogy van egy négyjegyű számunk 1111. Az algoritmus szerint négyzetbe helyezzük, így megszerezzük 1234321‬. Most négy számjegyet vonunk ki a közepéből, például 2343. Az algoritmus lehetővé teszi számunkra, hogy megismételjük ezt a folyamatot, amíg meg nem elégedünk az eredménnyel.

6. Következtetés

Ebben az oktatóanyagban több kivonási technikát vettünk figyelembe. Részletesen ismertettük a hajtogatási technikát, és gyors leírást adtunk arról, hogy miként érhető el a binning és a közepes négyzet.

Mint mindig, a megfelelő kódrészleteket is megtalálhatjuk a GitHub-tárunkban.