Lineáris hangzás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. február 9-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A lineáris szondázás  egy programozási séma a hash táblák ütközésének feloldására , a kulcs-érték párok manipulálására szolgáló adatszerkezetek az adott kulccsal társított értékek megtalálására. A rendszert 1954-ben Amdahl , Elaine McGraw és Arthur Samuel dolgozta ki, és Donald Knuth elemezte 1963-ban .

A másodfokú szondázással és a kettős tapintással együtt a lineáris tapintás egyfajta nyílt címzés . Ezekben a sémákban a hash tábla minden cellája egy kulcs-érték párt tartalmaz. Ha a hash függvény ütközik úgy, hogy az új kulcs értékét leképezi egy másik kulcs által elfoglalt hash táblázat cellájára, a lineáris vizsgálat a táblázatot a legközelebbi szabad következő celláig szkenneli, és oda szúrja be az új kulcsot. Az érték keresése ugyanígy történik, a tábla szekvenciális pásztázásával, a hash függvény által meghatározott pozíciótól kezdve, egészen addig, amíg kulcsegyezést, vagy üres cellát talál.

Ahogy Thorup és Zhang írta: "A hash táblák nagymértékben kihasználják a nem triviális adatstruktúrákat, és a legtöbb hardvermegvalósítás lineáris tesztelést használ, ami gyors és könnyen megvalósítható" [1] . A lineáris szondázás nagy teljesítményt nyújthat a módszer jó referencia lokalitása de érzékenyebb a hash függvény minőségére, mint más ütközésfeloldási sémák. Egy metódus átlagos várható keresési ideje állandó, ugyanez igaz a beszúrásokra és törlésekre is, ha a megvalósítás hash véletlenszerűsítést, 5-független hash-t vagy táblakivonatolást használ . A gyakorlatban azonban jó eredmények érhetők el más kivonatoló függvényekkel, mint például a MurmurHash [2] .

Műveletek

A lineáris próba a nyílt címzési sémák összetevője, amelyet hash-táblázatokban használnak szókincs-problémák megoldására . Egy szótárfeladatban az adatszerkezetnek kulcs-érték párok halmazán kell működnie, és lehetővé kell tennie a párok beszúrását és törlését, valamint a kulcshoz tartozó érték keresését. Nyílt címzésnél az adatstruktúra egy T tömb (hash table), amelynek T [ i ] cellái (ha nem üresek) egyetlen kulcs-érték párt tartalmaznak. A hash függvény minden kulcsot leképez egy T táblázatcellához, ahová a kulcsot el kell helyezni, általában úgy, hogy a kulcsokat úgy kódolják , hogy a közeli értékű kulcsok ne legyenek közel a táblázatban. Hash-ütközés akkor következik be, amikor a hash függvény leképez egy kulcsot egy olyan cellára, amelyet egy másik kulcs már foglalt. A lineáris szondázás egy olyan stratégia, amely az ütközéseket úgy oldja meg, hogy egy új kulcsot helyez el a legközelebbi szabad cellába [3] [4] .

Keresés

Adott x kulcs kereséséhez a T tábla celláit ellenőrizzük, kezdve a h ( x ) indexű cellával (ahol h  egy hash függvény), majd a h ( x ) + 1 , h ( x ) + 2 cellákkal , ..., amíg nem talál egy szabad cellát vagy egy olyan cellát, amely tartalmazza az x kulcsot . Ha a kulcsot tartalmazó cella megtalálható, a keresési eljárás az adott cellából származó értéket adja vissza. Ellenkező esetben, ha üres cellát találunk, a kulcs nem lehet a táblázatban, és az eljárás visszaadja, mivel a kulcs nem található [3] [4]

Beszúrás

Kulcs-érték pár ( x , v ) táblázatba történő beszúrásához (esetleg bármely létező pár lecserélése ugyanazzal a kulccsal), a beillesztési algoritmus ugyanazon a cellasorozaton megy keresztül, mint a keresésben, amíg üres cellát vagy cellát nem talál. x kulcsot tartalmaz . Az új kulcs-érték pár ebbe a cellába kerül [3] [4] .

Ha egy beszúrás után a tábla terhelési tényezője (az elfoglalt cellák hányada) meghalad valamilyen küszöbértéket, akkor az egész tábla lecserélhető egy új táblára, amely állandó tényezővel növekszik, mint egy dinamikus tömb esetében, egy új hash tábla. Ennek a küszöbértéknek a nullához közeli beállítása és a magas táblázatszórási tényező használata gyors műveleteket eredményez, de memóriaigényes. Az 1/2-es terhelési tényező elérésekor az asztal mérete általában megduplázódik, így a terhelés 1/4 és 1/2 között van [5]

Eltávolítás

Eltávolíthat egy kulcs-érték párt a szótárból. Azonban nem elég egyszerűen kiüríteni a cellát. Lehet, hogy van egy másik pár ugyanolyan hash értékkel, amelyet valahol a foglalt cella után helyeztek el. A cella törlése után egy második, azonos hash értékkel rendelkező érték keresése egy üres cellát talál, és a pár nem található.

Így az i cella törlésekor a következő cellákat kell néznünk, amíg nem találunk egy üres cellát, vagy egy kulcsot, amely átvihető az i cellába (vagyis olyan kulcsot, amelynek hash értéke egyenlő vagy kisebb, mint i ). Ha üres cellát talál, akkor törölheti az i cellát , és leállíthatja a törlési folyamatot. Ha olyan kulcsot talál, amely áthelyezhető az i cellába , helyezze át. Ez növeli az átvitt kulcs keresési sebességét, és egy másik cellát is töröl a foglalt cellák blokkjából. Tovább kell keresni egy kulcsot, amely átvihető erre a felszabadult helyre. Az átvitelhez szükséges kulcs keresése egy üres cellába történik, amíg el nem érjük az eredetileg üres cellát. Így a teljes törlési folyamat végrehajtási ideje arányos a törölt kulcsot tartalmazó blokk hosszával [3] .

Alternatív megoldásként egy lusta törlési stratégia is használható , amelyben a kulcs-érték pár eltávolításra kerül úgy, hogy az értéket egy speciális jelzővel helyettesítik , jelezve, hogy a kulcsot eltávolították. Az ilyen jelzők azonban a hash-tábla terhelési tényezőjének növekedését eredményezik. Ebben a stratégiában szükségessé válhat a zászlók eltávolítása a tömbből, és az összes fennmaradó kulcs-érték pár hash értékének újraszámítása, ha túl sok értéket távolítanak el [3] [4] .

Tulajdonságok

A lineáris tesztelés jó referencia lokalitást ad , ami azt jelenti, hogy műveletenként csak néhány nem gyorsítótárazott memória-hozzáférés szükséges. Ennek fényében az algoritmus alacsony terhelési tényező mellett magas fokú teljesítményt tud nyújtani. Azonban néhány más nyílt címzési stratégiához képest a teljesítmény gyorsabban romlik, ha betöltik az elsődleges klaszterezés miatt , ami azt jelenti, hogy egyetlen ütközés sok közeli ütközést okoz [3] . Ezenkívül ez a módszer jobb minőségű hash függvényt igényel, mint más ütközésfeloldási sémák [6] a jó teljesítmény eléréséhez . Ha az algoritmust rossz minőségű hash-függvénnyel valósítják meg, amely nem szünteti meg a bemeneti eloszlás heterogenitását, akkor a lineáris szondázás lassabb lehet, mint más nyílt címzési stratégiák, például a kettős szondázás , amely olyan sejtsorozatot próbál ki, amelynek elválasztása meghatározott. egy második hash függvénnyel vagy másodfokú szondázással , amikor az egyes lépések mérete a szondák sorozatában elfoglalt pozíciótól függően változik [7] .

Elemzés

Lineáris szondázás esetén a szótárműveletek megvalósíthatók állandó várható hozzáférési idővel. Más szavakkal, a beszúrási, törlési és keresési műveletek megvalósíthatók az O(1) -ben , feltéve, hogy a hash tábla terhelési tényezője egy állandónál szigorúan kisebb, mint egy [8] .

Pontosabban, az egyes műveletek (keresés, beszúrás vagy törlés) ideje arányos a lefoglalt cellák összefüggő blokkjának hosszával, amelyből a művelet kezdődik. Ha egy N cellát tartalmazó hash-táblázatban minden kezdő cella egyformán valószínű , akkor egy maximum k cellából álló blokk k / N valószínűséggel tartalmazza a kezdő keresési pozíciót, és O ( k ) időt vesz igénybe , bárhol is legyen a kezdő cella. Így a művelet várható végrehajtási ideje e két tag szorzataként számítható ki, O ( k 2 / N ) , a táblázat összes szomszédos cellájának maximális blokkjára összegezve. A tömbök hosszának négyzeteinek hasonló összege adja a szegélyszőnyeget. várakozási idő egy véletlenszerű hash függvényre (nem pedig egy véletlenszerű kezdőpozícióra a hash táblában) az összes létező blokk összegzésével (nem pedig a tábla aktuális állapotában ténylegesen létező blokkokkal), és megszorozzuk az egyes potenciális blokkok feltételeit annak valószínűségével, hogy a blokk foglalt. Vagyis ha a Block( i , k ) -t úgy definiáljuk, mint azt az eseményt, hogy van egy maximális összefüggő blokk a foglalt cellákból, amelyek hosszúsága i , mat indextől kezdődik . a műtét várakozási ideje

A képlet leegyszerűsíthető, ha a Block( i , k ) -t lecseréljük egy egyszerűbb szükséges Full( k ) feltételre , abban az esetben, ha legalább k elemnek van olyan hash értéke, amely egy k hosszúságú cellablokkon belül van . E csere után az összegen belüli érték már nem függ i -től , és az 1/ N tényező érvényteleníti a külső összegzés N tagját. Ezek az egyszerűsítések a határhoz vezetnek

De a Chernoff-korlát multiplikatív alakja szerint, ha a terhelési tényező szigorúan kisebb egynél, annak a valószínűsége, hogy a k blokkhossz legalább k hashed értéket tartalmaz, exponenciálisan kicsi k függvényében , ami azt jelenti, hogy az összeg n -től független konstans határolja [3] . Ugyanezt az elemzést a Stirling -formula használatával is elvégezhetjük a Chernoff-képlet helyett, amely annak valószínűségét becsüli meg, hogy egy blokk pontosan k hashed értéket tartalmaz [4] [9] .

Az α terhelési tényező szempontjából a sikeres keresés várható ideje O (1 + 1/(1 − α )) , a sikertelen keresés (vagy új kulcs beillesztése) pedig O (1 + 1/(1 − α ) 2 ) [10 ] . Állandó terhelési tényező esetén nagy valószínűséggel a leghosszabb vizsgáló szekvencia (a táblázat összes kulcsához tartozó vizsgálósorozatok közül) logaritmikus hosszúságú [11] .

Hash függvény kiválasztása

Mivel a lineáris szondázás nagyon érzékeny az egyenetlenül eloszló hash értékekre [7] , fontos, hogy a módszert kombináljuk egy jó minőségű hash függvénnyel, amely nem ad ilyen egyenlőtlenségeket.

A fenti elemzés feltételezi, hogy az egyes kulcsok hash-je egy véletlen szám, amely független a többi kulcs hash-eitől. Ez a feltételezés irreális a legtöbb kivonatolási alkalmazás esetében. Véletlenszerű vagy pszeudo-véletlen hash értékek azonban használhatók, ha az objektumok kivonatolása az azonosítójuk, nem pedig az érték alapján történik. Ez például a Java gyűjtemény keretrendszerének [12] osztály- és interfészkészletében található IdentityHashMap osztállyal való lineáris vizsgálattal történik . Az osztály által az egyes objektumokhoz társított hash-érték, az identitásHashCode garantáltan ugyanaz marad az objektum élettartama alatt, de más körülmények között ugyanazon objektum hash-értéke más lesz [13] . Mivel az IdentityHashCode objektumonként csak egyszer épül fel, és nem kell hozzárendelni az objektum értékéhez vagy címéhez, felépítése lassabb számítási eszközöket, például véletlen- vagy pszeudovéletlenszám-generátorok hívását is használhatja. Például a Java 8 az Xorshift [14] pszeudo-véletlen numerikus generátort használja az ilyen értékek létrehozásához .

A legtöbb kivonatolási alkalmazásnál minden egyes értékhez ki kell számítani a hash függvényt minden alkalommal, amikor kivonat szükséges, nem csak az objektum létrehozásakor. Az ilyen alkalmazásokban véletlenszerű vagy pszeudo-véletlen számok nem használhatók hash értékként, mert akkor az azonos értékű objektumok eltérő hash értékkel rendelkezhetnek. És a kriptográfiai hash függvények (amelyeket úgy terveztek, hogy ne legyenek megkülönböztethetők a valódi véletlen függvényektől) általában túl lassúak ahhoz, hogy hash-táblázatokban használják őket [15] . Ehelyett más módszereket használnak a hash függvények létrehozására. Ezek a módszerek gyorsan kiszámítják a hash függvényt, és bizonyíthatóan jól működnek a lineáris szondázással. A lineáris szondázást a k - független hash szempontjából elemezték , amely olyan hash függvények osztálya, amelyeket kis véletlenszámmal inicializálnak, és bármely k -különbözõ kulcsot leképeznek bármely k -sorra, ahol az indexek azonosak. valószínűség. A k paraméter felfogható a hash függvény minőségének mérőszámaként - minél nagyobb a k , annál több időbe telik a hash függvény kiszámítása, de a teljesen véletlenszerű függvényekhez közelebb fog viselkedni. Lineáris szondázás esetén az 5-ös függetlenség elegendő ahhoz, hogy garantálja a műveletenkénti állandó várható időt [16] , míg néhány 4-független hash függvény rosszul teljesít, és műveletenként logaritmikus időt igényel [6] .

A hash függvények jó minőségű és elfogadható sebességű felépítésének másik módja a táblázat hash . Ebben a módszerben a kulcs hash értékét úgy számítják ki, hogy a kulcs minden bájtjához egy indexet választanak a véletlenszámok táblázatában (minden bájthelyhez más táblázattal). Ezeknek a táblázatoknak a celláiból származó számokat ezután bitenként egyesítik az XOR művelettel . Az így felépített hash-függvények csak 3-függetlenek. Az ezeket a hash függvényeket használó lineáris próbák azonban műveletenként állandó várható időt igényelnek [4] [17] . Mind a táblakivonatolás, mind az 5 független hash-függvények generálására szolgáló szabványos módszerek a rögzített bitszámú kulcsokra korlátozódnak. Karakterláncokkal vagy más változó hosszúságú kulcsokkal való munkavégzéshez kombinálható az egyszerűbb univerzális kivonatolási technika , amely a kulcsokat közbülső értékekre képezi le egy kiváló minőségű (5 független vagy táblázatos ) hash függvénnyel, amely a közbenső értékeket képezi le. indexek kivonatolása - táblázatok [1] [18] .

Kísérleti összehasonlítások során Richter és munkatársai azt találták, hogy a hash függvények fold-shift családja (meghatározása: ) "a leggyorsabb hash függvény, ha minden hash sémában használták, azaz a legmagasabb átviteli sebességet és jó minőséget biztosít" a táblázatban. a kivonatolás "a legalacsonyabb áteresztőképességet" adta [2] . Kiemelték, hogy az egyes táblázatok megtekintése több ciklust igényel, ami drágább, mint az egyszerű aritmetikai műveletek. Azt is megállapították, hogy a MurmurHash jobb, mint a táblázatos hash: „A Mult és Murmur által bemutatott eredmények vizsgálata után úgy gondoljuk, hogy a táblázatosítás (…) kevésbé vonzó a gyakorlatban.”

Történelem

Konrad Zuse és Vanivar Busch [19] az 1940-es évek közepére nyúlik vissza egy asszociatív tömb ötlete , amely lehetővé teszi az adatokhoz az értékük, nem pedig a címük alapján való hozzáférést , de a hash táblákat addig nem írták le, amíg le nem írták őket. Lun [ egy IBM - memorandumban 1953-ban. Lun egy másik módszert alkalmazott az ütközések megoldására, a láncolást a lineáris szondázás helyett [20] .

Donald Knuth [8] összefoglalta a lineáris hangzás korai történetét. Ez volt a nyílt címzés első módja, és kezdetben a nyílt címzés szinonimája volt. Knuth szerint a módszert először Jean Amdahl , McGraw, Elani M. és Arthur Samuel alkalmazta 1954-ben egy IBM 701 -es assembler programban [8] . A lineáris hangzás első publikált leírását Peterson adta [21] [8] , aki említette Samuelt, Amdahlt és McGraw-t is, de hozzátette, hogy "a rendszer annyira természetes, hogy elég valószínű, hogy másoktól függetlenül létrehozhatták előtt vagy egy időben" [ 22] . Ennek a módszernek egy másik korai publikációja Andrej Petrovics Ershov szovjet kutatóé , 1958-ban [23] .

A lineáris szondázás első elméleti elemzését, amely megmutatta, hogy a módszer egy műveletenként állandó várható idő alatt működik egy véletlen hash függvényen, Knuth adta [8] . Sedgwick Knuth munkáját "mérföldkőnek nevezte az algoritmusok elemzésében" [10] . Lényegesen később a vizsgálatok a munkaidő valószínűségi eloszlásának részletesebb elemzéséhez vezettek [24] [25] és annak bizonyításához, hogy a lineáris szondázás műveletenként konstans időben működik a gyakorlati számításokhoz kényelmes hash-függvénnyel, és nem az ideális megoldással. a korábbi elemzésekben feltételezett véletlen függvény [16] [17] .

Jegyzetek

  1. ↑ 1 2 Thorup, Zhang, 2012 , p. 293–331.
  2. ↑ 1 2 Richter, Alvarez, Dittrich, 2015 , p. 293–331.
  3. ↑ 1 2 3 4 5 6 7 Goodrich, Tamassia, 2015 , p. 200–203.
  4. ↑ 1 2 3 4 5 6 Morin, 2014 , p. 108–116.
  5. ↑ Sedgewick, Wayne, 2011 ; Sedgwick és Wayne felezi az asztal méretét, ha az asztal terhelése túl alacsony lesz egy felosztásban, ami a lehetséges terhelési tényezők szélesebb tartományát [1/8,1/2] eredményezi.
  6. ↑ 1 2 Pătraşcu, Thorup, 2010 , p. 715–726.
  7. ↑ 1 2 Heileman, Luo, 2005 , p. 141–154.
  8. ↑ 1 2 3 4 5 Knuth, 1963 .
  9. ↑ Eppstein, 2011 .
  10. ↑ 12 Sedgewick , 2003 .
  11. ↑ Pittel, 1987 , p. 236–249.
  12. ↑ Java SE 7 dokumentáció .
  13. ↑ Friesen, 2012 , p. 376.
  14. ↑ Kabutz, 2014 .
  15. ↑ Weiss, 2014 , p. 3-11.
  16. ↑ 1 2 Pagh, Pagh, Ružić, 2009 , p. 1107–1120.
  17. ↑ 1 2 Pătrașcu, Thorup, 2011 , p. 1–10.
  18. ↑ Thorup, 2009 , p. 655–664.
  19. ↑ Parhami, 2006 , p. 67.
  20. ↑ Morin, 2004 , p. 9-15.
  21. ↑ Peterson, 1957 .
  22. ↑ Peterson, 1957 , p. 130–146.
  23. ↑ Ershov, 1958 , p. 3–6.
  24. ↑ Flajolet, Poblete, Viola, 1998 , p. 490–515.
  25. ↑ Knuth, 1998 , p. 561–568.

Irodalom