Räsitabel selgitatud: mis see on ja kuidas seda rakendada

Räsi tabel, mida nimetatakse ka räsi kaardiks, on andmestruktuur, mis kaardistab võtmed väärtustele. See on üks osa räsimiseks nimetatud tehnikast, teine ​​osa on räsifunktsioon. Räsifunktsioon on algoritm, mis loob indeksi selle kohta, kus väärtuse räsitabelis leidub või salvestatakse.

Mõned olulised märkused räsitabelite kohta:

  1. Väärtusi ei salvestata järjestatud järjekorras.
  2. Sa arvestad võimalike kokkupõrgetega. Seda tehakse tavaliselt tehnikaga, mida nimetatakse aheldamiseks. Aheldamine tähendab lingitud väärtuste loendi loomist, mille võtmed kaardistuvad kindla indeksiga.

Räsitabeli rakendamine

Räsimise põhiidee on jaotada võtme / väärtuse paarid räsitabeli kohahoidjate massiivi või "ämbrite" vahel.

Räsitabel on tavaliselt lingitud loendite massiiv. Kui soovite sisestada võtme / väärtuse paari, peate kõigepealt kasutama räsifunktsiooni, et kaardistada võti räsitabeli indeksisse. Antud võtme korral võib räsifunktsioon soovitada indeksi, kust saab väärtuse leida või salvestada:

index = f(key, array_size)

Seda tehakse sageli kahes etapis:

hash = hashfunc(key) index = hash % array_size

Selle meetodi kasutamine hashei sõltu räsitabeli suurusest. hashvähendatakse indeksiks - arvuks vahemikus 0, massiivi algus ja massiivi array_size - 1lõpp - kasutades moduli (%) operaatorit.

Mõelge järgmisele stringile S:

string S = “ababcd”

Peate loendama kõigi märkide sagedust S. Lihtsaim viis seda teha on kõigi võimalike tähemärkide kordamine ja nende sageduse ükshaaval lugemine.

See töötab, kuid see on aeglane - sellise lähenemise ajaline keerukus on O (26 * N), kusjuures Nstringi suurus Skorrutatakse 26 võimaliku AZ-i tähemärgiga.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Väljund:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Vaatame lahendust, mis kasutab räsimist.

Võtke massiiv ja kasutage räsifunktsiooni, et räsida massiivi indeksitega 26 võimalikku märki. Seejärel korrake Sja suurendage stringi praeguse tähemärgi väärtust iga märgi vastava indeksiga.

Selle räsimisviisi keerukus on O (N), kus N on stringi suurus.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Väljund

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Räsikokkupõrked

Kuna teie räsikaart on tõenäoliselt oluliselt väiksem kui teie töödeldav andmemaht, on räsikokkupõrked vältimatud. Kokkupõrgete käsitlemisel on kaks peamist lähenemist: aheldamine ja avatud pöördumine .

Aheldamine

Nagu varem mainitud, tähendab aheldamine seda, et iga räsitabeli võti / väärtuspaar on väärtus pigem lingitud andmete loend kui üks lahter.

Kujutage näiteks ette, et võtmel 152 on väärtus "John Smith". Kui samale võtmele lisatakse väärtus "Sandra Dee", lisatakse võtmele 152 teise elemendina "Sandra Dee" vahetult pärast sõna "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Aheldamise peamine puudus on aja keerukuse suurenemine. 0 (1) asemel, nagu tavalise räsitabeli puhul, võtab iga otsing rohkem aega, kuna õige väärtuse leidmiseks peame läbima iga lingitud loendi.

Avatud adresseerimine

Avatud adresseerimine tähendab, et kui väärtus on juba hõivatud võtmega kaardistatud, liigute räsitabeli klahvide abil seni, kuni leiate tühja. Näiteks kui "John Smith" kaardistati 152-ga, kaardistatakse "Sandra Dee" järgmise avatud indeksiga:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Avatud adresseerimise peamine puudus on see, et kui otsite väärtusi, ei pruugi need olla võtmekaardil, mida eeldate. Selle asemel peate otsitava väärtuse leidmiseks läbima räsitabeli erinevad osad.