Hasított tömbfa - Hashed array tree
Az informatikában a hash tömbfa ( HAT ) egy dinamikus tömb adatstruktúra, amelyet Edward Sitarski adott ki 1996-ban, és külön memória töredékeket (vagy "leveleket") tárol az adatok tárolására, ellentétben az egyszerű dinamikus tömbökkel, amelyek fenntartják adataikat egy összefüggő memóriaterületen. Elsődleges célja az elemek másolásának csökkentése az automatikus tömb átméretezési műveletek miatt, és a memóriahasználati szokások javítása.
Míg a geometriai táguláson alapuló egyszerű dinamikus tömbök hulladék lineáris (Ω ( n )) teret, ahol n a tömb elemeinek száma, addig a hasított tömbfák csak O ( √ n ) tárhelyet rendelnek . Az algoritmus optimalizálása lehetővé teszi az adatmásolás teljes kiküszöbölését, az elpazarolt hely növelésének költségével.
Állandó ( O (1)) időben képes elérni a hozzáférést , bár kissé lassabban, mint az egyszerű dinamikus tömbök. Az algoritmus O (1) amortizált teljesítménnyel rendelkezik, amikor objektumok sorozatát illesztik a hash tömbfa végéhez. Nevével ellentétben nem használ hash függvényeket .
Definíciók
A Sitarski meghatározása szerint a kivonatolt tömbfának van egy legfelső szintű könyvtár, amely két számú levéltömb hatványát tartalmazza . Minden levéltömb azonos méretű, mint a legfelső szintű könyvtár. Ez a szerkezet felületesen hasonlít egy hash tábla array alapú ütközés láncok, ami az alapja a neve kivonatolt tömb fa . A teljes hash tömbfa m 2 elemet tartalmazhat, ahol m a legfelső szintű könyvtár mérete. A kettő hatványainak használata gyorsabb fizikai címzést tesz lehetővé bitműveletekkel a hányados és a maradék aritmetikai műveletei helyett, és biztosítja az O (1) amortizált teljesítményét a függelék műveletnek alkalmi globális tömb-másolat jelenlétében, miközben bővül.
Bővítések és méretcsökkentések
Egy szokásos dinamikus tömb geometriai kiterjesztési sémában a tömböt egy teljes, szekvenciális memória darabként csoportosítják át, az új méret a jelenlegi méretének a duplája (és a teljes adat ezután az új helyre kerül). Ez biztosítja az O (1) amortizált műveleteket O (n) elpazarolt hely költségén, mivel a kibővített tömb új kapacitásának a feléig megtelt.
Ha a hash tömbfa megtelt, annak könyvtárát és leveleit a korábbi méretük kétszeresére kell átstrukturálni, hogy további függelék műveletek is helyet kapjanak. A régi struktúrában tárolt adatok az új helyekre kerülnek. Ezután csak egy új levél kerül kiosztásra, és hozzáadódik a legfelső tömbhöz, amely így csak új kapacitásának negyedéig töltődik be. Az összes extra levél még nincs kiosztva, és csak szükség esetén kerül kiosztásra, így csak O ( √ n ) tárhelyet pazarolunk el.
Számos alternatíva létezik a méret csökkentésére: ha egy kivonatolt tömbfa egy nyolcadik tele van, akkor átstrukturálható egy kisebb, félig tele hasított tömbfává; egy másik lehetőség csak a fel nem használt levéltömbök felszabadítása, a levelek átméretezése nélkül. A további optimalizálás magában foglalja az új levelek hozzáadását átméretezés nélkül, miközben szükség szerint növeli a könyvtár tömböt, esetleg geometriai kiterjesztéssel. Ez kiküszöböli az adatmásolás szükségességét, annak árán, hogy az elpazarolt hely O ( n ) legyen, kis állandóval, és csak akkor végezzen szerkezetátalakítást, ha egy meghatározott küszöbértéket elérnek.
Kapcsolódó adatszerkezetek
| Összekapcsolt lista | Sor | Dinamikus tömb | Kiegyensúlyozott fa | Véletlen hozzáférési lista | Összetört tömbfa | |
|---|---|---|---|---|---|---|
| Indexelés | Θ ( n ) | Θ (1) | Θ (1) | Θ (log n) | Θ (log n) | Θ (1) |
| Beszúrás / törlés az elején | Θ (1) | N / A | Θ ( n ) | Θ (log n) | Θ (1) | Θ ( n ) |
| Beszúrás / törlés a végén | Θ (1), amikor az utolsó elem ismert ; Θ ( n ), ha az utolsó elem ismeretlen |
N / A | Θ (1) amortizálva | Θ (log n ) | N / A | Θ (1) amortizálva |
| Helyezze be / törölje középre | keresési idő + Θ (1) | N / A | Θ ( n ) | Θ (log n ) | N / A | Θ ( n ) |
| Elpazarolt hely (átlag) | Θ ( n ) | 0 | Θ ( n ) | Θ ( n ) | Θ ( n ) | Θ ( √ n ) |
Brodnik és mtsai. dinamikus tömbalgoritmust mutatott be , amely hasonló töredékprofillal rendelkezik, mint a tömbfák hasítása. A Brodnik megvalósítása megőrzi a korábban kiosztott levéltömböket, a címzettszámítás funkcióval bonyolultabb, mint a hash tömbfáké.
