Pengguna:LGA EGA/Tabel hash: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
Tidak ada ringkasan suntingan |
||
Baris 1:
[[Berkas:Hash_table_3_1_1_0_1_0_0_SP.svg|ka|jmpl|315x315px| Buku telepon kecil sebagai tabel hash]]
Dalam [[Komputasi (teknologi informasi)|komputasi]], '''tabel hash'''([[bahasa Inggris]]: Hash table), juga dikenal sebagai '''peta hash''' atau '''kumpulan hash''', adalah [[struktur data]] yang mengimplementasikan array asosiatif, juga disebut kamus. Ini adalah [[tipe data abstrak]] yang memetakan kunci ke [[Nilai (ilmu komputer)|nilai]].<ref name="ms">{{Citation|chapter=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first=Kurt|last=Mehlhorn|first2=Peter|last2=Sanders|publisher=Springer|year=2008|pages=81–98|url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf}}</ref> Tabel hash menggunakan [[Fungsi pineta|fungsi hash]] untuk menghitung ''indeks'', yang juga disebut ''kode hash'', ke dalam array ''keranjang'' atau ''slot''. Dari slot inilah nilai yang diinginkan dapat ditemukan.
Selama pencarian, kunci di-hash, dan hash yang dihasilkan menunjukkan di mana nilai terkait disimpan. Dalam tabel hash yang dirancang dengan baik, kompleksitas waktu rata-rata untuk setiap pencarian tidak bergantung pada jumlah elemen yang disimpan dalam tabel. Banyak desain tabel hash juga memungkinkan penyisipan dan penghapusan pasangan kunci-nilai secara sewenang-wenang, dengan biaya rata-rata konstan per operasi yang diamortisasi.<ref name="leiser">{{Cite web|last=Leiserson|first=Charles E.|date=Fall 2005|title=Lecture 13: Amortized Algorithms, Table Doubling, Potential Method|url=http://videolectures.net/mit6046jf05_leiserson_lec13/|website=course MIT 6.046J/18.410J Introduction to Algorithms|archive-url=https://web.archive.org/web/20090807022046/http://videolectures.net/mit6046jf05_leiserson_lec13/|archive-date=August 7, 2009|url-status=live}}</ref> <ref name="knuth">{{Cite book|last=Knuth|first=Donald|year=1998|title=The Art of Computer Programming|publisher=Addison-Wesley|isbn=978-0-201-89685-5|edition=dua|volume=3: ''Sorting and Searching''|pages=513–558}}</ref> <ref name="cormen">{{Cite book|last=Cormen|first=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|year=2001|title=Introduction to Algorithms|title-link=Introduction to Algorithms|publisher=MIT Press and McGraw-Hill|isbn=978-0-262-53196-2|edition=dua|pages=[https://archive.org/details/introductiontoal00corm_691/page/n243 221]–252|chapter=Chapter 11: Hash Tables}}</ref>
| |||