Összehasonlítását a hash tábla és egy térkép a

Hasonlítsuk össze a hash tábla, és a mar a Standard Template Library (STL). Hogy van a hash tábla? Mi adatstruktúra optimális kis mennyiségű adatot?

A hash tábla érték alá, ha hívja a kettőskereszt gombot. Maguk az értékek vannak tárolva rendezetlenül. Mivel a hash tábla egy kulcsot használ az indexelés elemek behelyezése vagy adatok lekérdezése tart O (1) idő (figyelembe véve a minimális számú ütközések hash táblák). A hash tábla is kell kezelni a potenciális konfliktus. Erre a célra a lánc - kapcsolt lista az összes értékek és kulcsok jelennek meg egy adott index.

térkép (STL) beilleszti a kulcs / érték párokat egy bináris keresési fa alapú kulcsokat. Nincs szükség kezelni a konfliktust, valamint a fa kiegyensúlyozott, beillesztését és keresési idő O (log N).

Hogyan kell végrehajtani a hash tábla?

A hash tábla van megvalósítva egy sor kapcsolódó listák. Ha azt akarjuk, hogy helyezzen be egy kulcs / érték párt, akkor a hash függvény feltérképezése a kulcsot a index. Ha ez az érték esik egy megadott helyre egy láncolt lista.

Azt nem mondhatjuk, hogy az elemek egy láncolt lista egy adott tömb index ugyanazt a kulcsot. Inkább, hashFunction (kulcs) funkció ezen értékek egybeesnek. Ezért, hogy megkapjuk megfelelő értékkel a legfontosabb, amit meg kell tárolni minden egyes csomópont és a kulcs és az érték.

Összefoglalva: a hash táblában van megvalósítva egy sor kapcsolódó listák, minden csomópont a listán két komponenst tartalmaz: az érték az eredeti kulcs. Nézzük sorolja a funkciók végrehajtásának hash táblák:

1. Be kell használni egy jó hash függvény, annak érdekében, hogy a billentyűket helyesen elosztva. Ha a billentyűk rosszul elosztott, nem lesz sok konfliktus és sebességét az elem csökken.
2. Nem számít, hogy milyen jó a hash függvény, konfliktusok támadnak, és szükségünk lesz a kezelésük. Ez magában foglalja a kapcsolt listák láncok (vagy más módszer a probléma megoldására).
3. Lehetőség van az eljárások megvalósítására dinamikusan növeli vagy csökkenti a méretét a hash tábla. Például, ha az arány az elemek a méret a táblázat meghalad egy bizonyos értéket, akkor növelni kell a méret a hash tábla. Ez azt jelenti, hogy létre kell hozni egy új hash tábla, és adja oda egy régi felvétel. Mert ez nagyon időigényes folyamat, meg kell tenni mindent annak érdekében, tábla mérete nem változott túl gyakran.

Mit lehet cserélni a hash tábla, ha dolgozik, kis mennyiségű adatot?

Használhatja a mar (az STL), vagy egy bináris fa. Bár ez O (log (n)) idő, adatmennyiség nem nagy, így a szükséges idő kicsi lesz.

Mi az előnye a térkép?

A fának legalább egy külön előnye, mint a hash tábla. A térkép sétálhat egy bejáró növekvő vagy csökkenő kulcsokat és nem gyorsan. Hash tábla ebben a tekintetben elveszik.