Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka
3,99 € Ielikt grozā
Gribi lētāk?
Identifikators:302777
 
Autors:
Vērtējums:
Publicēts: 06.04.2009.
Valoda: Latviešu
Līmenis: Augstskolas
Literatūras saraksts: 3 vienības
Atsauces: Nav
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
1.  Meklēšanas metodes    4
2.  Hešēšana    5
2.1  Hešfunkcijas un heštabulas    5
2.2  Problēmas ar heštabulām    7
3.  Kolīzijas    8
3.1  Rehešēšana (re-hashing)    8
3.1.1  Lineārā rehešēšana (linear probing)    9
3.1.2  Kvadrātiskā rehešēšana (quadratic probing)    9
4.  Heštabulas izmēru mainīšana    10
  Izmantotā literatūra    11
Darba fragmentsAizvērt

4. Heštabulas izmēru mainīšana
Ar labu hešfunkciju parasti heštabula var saturēt 70% - 80% elementu vairāk cik tajā var ievietot ierakstus un vēl uzrādīt labu failu pieejas laiku. Atkarībā no izvēlētā kolīziju novēršanas veida šis laiks var strauji pasliktināties tiklīdz pievieno jaunus elementus. Lai to novērstu tiek izveidota jauna, lielāka tabula, kad noslodzes koeficients pārsniegts kādu slieksni, kurā ievieto arī vecās tabulas saturu.
Taču šī operācija var dārgi maksāt un tās nepieciešamība ir heštabulas mīnuss. Gadījumos, kad heštabula tiek palielināta par vienu ierakstu ik reizi pēc jauna elementa pievienošanas, ātrdarbība strauji samazinās un zūd heštabulas jēga. Taču, ja heštabulu palielina par kādu konstantu lielumu, piemēram, par 10% vai 100%, tiek iegūts, ka heštabulas palielināšanas notiek neregulāri un reti un rezultātā informācijas meklēšanai patērētais laiks paliek konstants.
Taču reāllaika sistēmās heštabulu palielināšana nevar tikt veikta uzreiz, jo tā varētu pārtraukt svarīgas sistēmas operācijas. Viena vienkārša pieeja ir sākotnēji iedalīt tabulai pietiekami daudz vietas nepieciešamajiem datiem un nepieļaut pārāk daudz elementu pievienošanu. Cita, bet vairāk atmiņu noslogojošs paņēmiens ir mainīt izmēru pakāpeniski:
• izvietot jauno heštabulu, bet atstāt arī veco heštabulu un pārbaudīt tās abas meklējot informāciju;
• ik reizi, kad realizē ievietošanu, pievieno šo elementu jaunajai tabulai un arī pārvieto k elementus no vecās uz jauno tabulu;
• kad visi elementi ir pārvietoti no vecās tabulas atbrīvojas;
Cits veids kā uzlabot heštabulas izmēra izmainīšanu ir izvēlēties hešfunkciju, kuras rezultāti daudz nemainās mainot heštabulas izmēru.

Autora komentārsAtvērt
Darbu komplekts:
IZDEVĪGI pirkt komplektā ietaupīsi −3,98 €
Materiālu komplekts Nr. 1124956
Parādīt vairāk līdzīgos ...

Atlants

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties