PROFILPELAJAR.COM

Jaucējtabula

Neliela telefongrāmata kā heštabula.

Datorzinātnē jaucējtabula jeb heštabula (angļu: hash table)[1] ir datu struktūra, kura izmanto jaucējfunkcijas, lai sasaistītu identificējošas vērtības, zināmas kā atslēgas (piemēram, personas vārds) ar tām piesaistītajām vērtībām (piemēram, telefona numuriem). Līdz ar to heštabula ir asociatīva masīva realizācija. Hešfunkcijas 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ācijas 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[2]) izmaksām uz darbību.[3] [4]

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

  1. ↑ table/{{{lang}}} «Latvijas Nacionālais terminoloģijas portāls - hash table». termini.gov.lv.
  2. ↑ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 2005
  3. ↑ Donald Knuth. The Art of Computer Programming'. 3: Sorting and Searching (2nd izd.). Addison-Wesley, 1998. 513–558. lpp. ISBN 0-201-89685-0.
  4. ↑ 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.
Tipi
Masīvi
Saraksti
Koki
Grafi
Jēdzieni

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.