10 (1)

10 (1). Hasítás. Keresés, a befogadás és a kirekesztés elemekkel. Véletlenszerű funkció (hash), és annak tulajdonságait.

Korábban tekinthető a gyűjtemény alapján a keresési fák teszi, hogy építsenek egy absztrakt adattípus „táblázat”. De ezek a gyűjtemények logaritmikus időigényes művelet, attól függően, hogy az elemek száma a táblázatban. Vannak alkalmazások, amelyek megkövetelik a gyors és garantált idejű teljesítmény, függetlenül az adatok mennyisége a táblázatban. Ebben az esetben a különleges szervezet az asztal állandó üzemeltetését - hash tábla.

Hash tábla igényel memória O (# 9474; m # 9474;), ahol m - a sok szerepel a táblázatban a rekordok. Keresés időt a hash tábla még mindig O (1).

A hash-táblázat index h adott elem (k), ahol k - gomb h (k) elem - a hash függvény (vagy véletlenszerűvé funkció). A szám h (k) nevezik a hash értékét k kulcs. A folyamat, amely a kulcseleme a hash index - a táblázat az úgynevezett hasítás.

Hash függvény (randomizálva funkció) és tulajdonságai

1. Egy jó hash függvény kell biztosítsa tördelő, azaz bármely kulcsa minden m hash értékeket kell egyformán valószínű.

2. randomizing funkciót nem tart fenn kapcsolatot a kulcsainak értékei. Ez a követelmény kizárja (vagy legalábbis csökkenti) a függőség a „minőség” randomizációját kulcs használt értékeket.

4. Hash - funkciót kell determinisztikus abban az értelemben, hogy ismételt hívások azonos kulcsot, vissza kellett térnie az azonos hash értékét.

Vezetői intézkedés randomize funkció ábrán látható.

· Szétadagolás Módszer maradékot (moduláris hashing) ad egy egyszerű és hatékony hash függvény. K kulcsot van rendelve egy fennmaradó osztódó k m. A hash függvény van kiszámítva, mint egyenlet h (k) = k mod m.

Például, ha m = 13, k = 100, akkor h (k) = 9.

· Módszer szorzás (szorzó) kiszámít egy hash - funkciót, amelyet a képlet

ahol A- egy állandó kielégítő 0

Az erény a szorzás a módszer lényege, hogy a minőség a hash függvény függ kevés a választott m. De általában az m választani a kettő hatványa, mint a legtöbb számítógépen szorzás ereje két gyorsan végrehajtják, mint a váltás a szót. szorzás módszer működik bármely választott konstans A. de néhány értékeit lehet jobb, mint mások. A legjobb ár-érték egy Fibonacci-szám. A = 0,6180339887

Mi azt az eljárást illusztrálja egy konkrét példát. Tegyük fel, a hash mérete - táblázat m = 10000. Amikor behelyezzük a kulcsot fog hash 123456 - azaz:

függvény hash (kulcs string [4].): integer;

f: = ORD (kulcs [1]) - ORD (gomb [2]) + ORD ([3] gomb) - ORD (kulcs [4]);

F: = (F * 10000) div (255 * 4);

Módszerek konfliktusmegoldás

Az eljárást eltávolítására az asztalról csökken megtalálása az elem és annak eltávolítását a túlfolyó lánc.

3.2 ábra. Változatos módszerek konfliktusok megoldásában

3.3 ábra. Ütközés Felbontás hozzátéve elemeket láncok

Lineáris vizsgálat csökken szekvenciális scan a táblázat elemei fix pitch

ahol i - a próbálkozások száma a konfliktus megoldására. Lépésben egyenlő egy szekvenciális keresést az összes elem után a jelenlegi.

Négyzetes tesztje különbözik a lineáris a lépést iterációjával nem lineárisan függ a próbálkozások számát, hogy megtalálja egy szabad elemet

Engedélyezése és keresés

Bemutatjuk algoritmusok behelyezése és visszakeresés módszer lineáris tesztelés.

· A = h (kulcs) + i * C

· Ha t (a) = szabadon, t (a) = gombot. levelet elem, az elzáró elem adunk

· I = i + 1, ugorjon a 2. lépésre

· A = h (kulcs) + i * C

· Ha t (a) = gombot. A stop elem megtalálható

· Ha t (a) = szabadon, az ütközőelem nem található

· I = i + 1, ugorjon a 2. lépésre

Kiválasztása lépésben q. Amikor megpróbálja felvenni egy elemet egy elfoglalt sejt elkezd szekvenciális leolvasó sejt, és így tovább, amíg nem találunk egy szabad cella. Ebben, és írjon elem. Lényegében szekvenciális keresés - egy speciális esete a lineáris, ahol q = 1.

Lépés q nem fix, hanem változó négyzetesen: q = 1,4,9,16. Ennek megfelelően, amikor megpróbál hozzáadni egy elemet egy elfoglalt sejt elkezd szekvenciális leolvasó sejt, és így tovább, amíg nem találunk egy szabad cella. dupla hash

Ez azt mutatja, a hash tábla mérete 13 sejtek, amely felhasználja a kiegészítő funkciók:

Azt akarjuk, hogy helyezze be a kulcsot 14. Kezdetben i = 0. Aztán. De index 1 sejt elfoglalt, ezért egyre i 1 és újraszámolja a hash értéket. Mi is teszik, amíg el nem érünk egy üres cellába. Amikor i = 2, megkapjuk. A sejt a 9-es szám ingyenes, akkor írj a legfontosabb.

(2. lépés). Az eltávolítási eljárás számít ez nem olyan egyszerű, mivel ebben az esetben nem lesz fordított behelyezés eljárást.

Az a tény, hogy az elemek a táblázatban két államban: a szabad és foglalt. Ha töröl egy elemet azáltal, hogy a szabad eltávolítása után a keresési algoritmus nem fog megfelelően működni. Tegyük fel, hogy a legfontosabb eleme eltávolítjuk a táblázatban kulcsok szinonimái. Abban az esetben, cserélhető elem eredményeként ütközés felbontású elemek kerültek más billentyűkkel, a lista ezen elemek eltávolítása után mindig ad egy negatív eredmény, hiszen a keresési algoritmus megáll az első elem található abban a helyzetben szabadon.

Ahhoz, hogy javítson ezen a helyzeten a különböző módokon.

· A legegyszerűbb ezek közül keresni az elem nem felel meg az első helyet, és a végén az asztalra. Azonban egy ilyen módosítás az algoritmus semmissé tenné az egész nyereség gyorsulás az adatokhoz való hozzáférést, ami úgy érhető el tördeljük.

· Van olyan megközelítés, amely mentes ezeket a hátrányokat. Ennek lényege abban a tényben rejlik, hogy a hozzáadott feltétele eltávolított elemek a hash tábla. Ez az állapot a keresési folyamat értelmezni a foglalkoztatás, valamint ingyenes belépést a tanfolyamot.

Fogalmazza keresés behelyezése és eltávolítása algoritmusok hash tábla, amelynek három állam elemekkel.

2. a = h (kulcs) + i * C

3. Ha t (a) = szabad vagy t (A) = hagyni, t (a) = gombot. levelet elem, az elzáró elem adunk

4. i = i + 1, ugorjon a 2. lépésre

· A = h (kulcs) + i * C

· Ha t (a) = gombot. akkor T (A) = hagyni. az ütközőelem eltávolítjuk

· Ha t (a) = szabadon, az ütközőelem nem található

· I = i + 1, ugorjon a 2. lépésre

· A = h (kulcs) + i * C

· Ha t (a) = gombot. A stop elem megtalálható

· Ha t (a) = szabadon, az ütközőelem nem található

· I = i + 1, ugorjon a 2. lépésre

A keresési algoritmust a hash tábla, amelynek három állam, nem különbözik a keresési algoritmus kivételével törléseket. A különbség az, hogy meg kell ünnepelni a szabad és a törölt elemeket a szervezet maga a táblázat. Ez úgy valósítható meg, amely fenntartja a két érték a kulcs mezőbe. Egy másik kiviteli alak tartalmazhat a bevezetése egy további mezőt, ahol a rögzített elem állapotban. A hossza ezen a területen lehet, hogy csak két bit, ami elegendő ahhoz, hogy rögzítse a három államban.