Bővíthető hasítás
A Wikiforrásból
Gyakori hozzáadásával új értékeket a hash tábla lehet olyan helyzet, amikor a hash tábla teljesen feltöltődik, és ez megköveteli pereheshirovat. Ha a hash asztal mérete kicsi, a teljes túlcsordulás nem okoz nehézséget. Mert nagy mérete a hash tábla, amely megköveteli a sok időt, és ha az értékek jönnek nagyon gyakran, gyakran pereheshirovat asztal bármely kiosztani hatalmas mennyiségű memória, amely nem feltétlenül szükséges, és ezért egyszerűen kárba Reserve. Szintén standard hash táblázatban ütközhet (két különböző érték érkezik ugyanabba a cellába). Ezeknek a problémáknak a megoldására, valamint arra, hogy ne adjunk ki sok kiegészítő memóriát, használhatjuk a bővíthető hasmenést.
[szerkesztés] Struktúra és algoritmus
Eljárás nyújtható tördelő (Engl. Extendible tördelés), hogy a hash tábla áll rendelkezésre, mint egy könyvtár (Engl. Könyvtár), és minden sejt jelzi a kapacitás (Engl. Bucket), amely egy bizonyos kapacitás (Engl. Capacity). Maga a hash asztal globális mélységgel rendelkezik, és mindegyik tartálynak van egy helyi mélysége. A globális mélység azt jelzi, hogy hány utolsó bitet használnak annak meghatározására, hogy melyik kapacitás adja meg az értékeket. A helyi mélység és a globális mélység különbségeiből azonban megérthetjük, hogy a katalógus mennyi cellája a kapacitásra utal. Ezt a képlet mutatja be, hol van a globális mélység, a helyi mélység és a referenciacellák száma. A kapacitás kereséséhez digitális fát használunk.
Vegye figyelembe az algoritmust, ha van egy bizonyos értéke:
- Az értéket bináris formában fordítjuk le, nézzük az utolsó biteket, és döntsük el, melyik kapacitást küldjük az értéknek.
- Ha a kapacitásnak van egy szabad helyzete, akkor minden hiba nélkül elhelyezzük az értéket, ha a kapacitás, ahol az értéket fel kell tüntetni, akkor nézzük meg a kapacitás helyi mélységét:
- Ha ez kevesebb, mint a globális átlag mélysége a tartály van néhány támpont, és mi elég pereheshirovat azt elosztjuk egyidejűleg két, és adja meg az új értékeket a két kapacitásokat növelni kell ezen kapacitások a helyi mélységet.
- Ha a helyi mélység megegyezik a globális értékkel, növeljük a globális mélységet, megduplázzuk a cellák számát, a mutatók számát a kapacitáshoz, és növeljük az utolsó bitek számát, amelyekkel az értékeket terjesztjük. Továbbá a túlcsordult kapacitás helyi mélysége kisebb lesz, és megismétli az előző algoritmust, vagyis felidézzük a kapacitást, két tartályra osztjuk és így tovább.
[szerkesztés] Példa
Tekintsük az algoritmust egy példára.
Tegyük fel, hogy egy bizonyos könyvtárunk van a mutatóinkkal, és szeretnénk hozzáadni értékeket (lásd az 1. ábrát), ahol hol van a globális mélység, a tartályok helyi mélysége és a tartályok kapacitása.
Az első bemenet értéke. Képzeld el bináris formában :. A vég a második cellának felel meg, tehát a második tartályra tekintünk. Van egy szabad hely, és csak beillesztettük (lásd a 2. ábrát). Ezzel befejeződik a munka.
Ezután a bemenet értéket kap. Képzeld el bináris formában :. Ez az érték véget ér, és az első tartályba kell menni, de az első tartály teljesen kitöltött. Ezért megnézzük az első kapacitás helyi mélységét, azaz. így a fenti leírt algoritmus, már kétszer annyi könyvtár sejtek, növeli a globális mélységben, majd számának növelése az utolsó bit amelyhez szétszórják értékek és pereheshirovat első hajó, felosztva azokat két, növelve a helyi mélysége és értékén új konténerek (lásd №3). Ezzel befejeződik a munka.
Az utolsó értéket kap. Képzeld el bináris formában :. Az utolsó bit () megfelel a harmadik tank, de ez is teljesen fel van töltve, mint a második esetben, de a helyi mélysége kisebb, mint a globális mélység, és ezért meg kell csak pereheshirovat kapacitás, felosztva azokat két, növelve a helyi mélysége és értékén új konténerek (lásd a 4. ábrát). Ezzel befejeződik a munka.
[szerkesztés] Használat
Leggyakrabban a kiterjeszthető hasmenés az adatbázisokban található, mert. Az adatbázisok rendkívül nagyok lehetnek, és a teljes adatbázis felülírása sok időt vesz igénybe, miközben tagadja a felhasználók hozzáférését az adatbázishoz. És egy kiterjeszthető hash használata esetén csak kis csoportoknak kell túlszárnyalniuk, ami nem lassítja az adatbázis működését. A kiterjeszthető hasítás jól működik egy dinamikusan változó rekordkészletben egy tárolt fájlban.