Jaucējtabula: Atšķirības starp versijām

Dzēstais saturs Pievienotais saturs

Vienā rindā

Versija, kas saglabāta 2011. gada 13. maijs, plkst. 22.42

Datorzinātnē heštabula ir datu struktūra, kura izmanto hešfunkcijas, lai sasaistītu identificējošas vērtības, zināmas kā atslēgas (piemēram, perosnas vārds) ar tām piesaistītajām vērtībām (piermēram, telefona numuriem). Līdz ar to heštabula ir asociatīva masīva realizācija. Hešfunkijas izmanto, lai pārveidotu atslēgu par indeksu masīva elementam, kurā tiek glabāta atbilstošā vērtība.

Ideālā gadījumā hešfunkcijai vajadzētu piesaistīt katru iespējamo atslēgu unikālam indeksam, bet praksē tas tiek sasniegts reti (ja vien atslēgas ir fiksētas, t.i. pēc tabulas izveides netiek pievienoti jauni ieraksti). Tā vietā vairums heštabulu realizāciju pieņem, ka atslēgu kolīzija — atšķirīgas atslēgas, kuras norāda uz to pašu indeksu - notiks un šī problēma kaut kādā veidā ir jāatrisina.

Labi veidotā heštabulā vidējās izmaksas (katrai vērtības atrašanai nepieciešamais instrukciju skaits) ir neatkarīgas no tabulā uzglabāto vērtību skaita. Daudzas heštabulu realizācija pieļauj arī iespēju ievietot un dzēst esošus atslēgu un vērtību pārus ar konstantām vidējām (amortizētām^[1]) izmaksām uz darbību.^[2] ^[3]

Daudzās situācijās heštabulas izrādās efektīvākas kā meklēšanas koki vai jebkura cita meklēšanas tabulas struktūra. Šā iemesla dēļ tās tiek plaši izmantotas dažādās datorprogrammās, galvenokārt asociatīviem masīviem, datubāžu indeksiem, kešošanai un kopu datu struktūrām.

Atsauces

↑ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 2005
↑ Donald Knuth. The Art of Computer Programming'. 3: Sorting and Searching (2nd izd.). Addison-Wesley, 1998. 513–558. lpp. ISBN 0-201-89685-0. Ignorēts nezināms parametrs |note=
↑ Thomas H. Cormen; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms (second izd.). MIT Press and McGraw-Hill, 2001. 221–252. ISBN 978-0-262-53196-2.

Šis ar informācijas tehnoloģijām saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to.

[leiser-1] Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 2005

[knuth-2] Donald Knuth. The Art of Computer Programming'. 3: Sorting and Searching (2nd izd.). Addison-Wesley, 1998. 513–558. lpp. ISBN 0-201-89685-0. Ignorēts nezināms parametrs |note=

[cormen-3] Thomas H. Cormen; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms (second izd.). MIT Press and McGraw-Hill, 2001. 221–252. ISBN 978-0-262-53196-2.

[1]

[2]

[3]