Pengguna:LGA EGA/Tabel hash: Perbedaan antara revisi

[[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''', juga dikenal sebagai '''peta hash''' atau '''kumpulan hash''', adalah [[struktur data]] yang mengimplementasikan array asosiatif, juga disebut kamus, yang merupakan [[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|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|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'', juga disebut ''kode hash'', ke dalam array ''keranjang'' atau ''slot'', yang darinya nilai yang diinginkan dapat ditemukan. Selama pencarian, kunci di-hash dan hash yang dihasilkan menunjukkan di mana nilai terkait disimpan.

 

Dalam tabel hash berdimensi 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.|authorlink=Charles E. Leiserson|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=2nd|volume=3: ''Sorting and Searching''|pages=513–558|author-link=Donald Knuth}}</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=2nd|pages=[https://archive.org/details/introductiontoal00corm_691/page/n243 221]–252|chapter=Chapter 11: Hash Tables|author-link=Thomas H. Cormen|author-link2=Charles E. Leiserson|author-link3=Ronald L. Rivest|author-link4=Clifford Stein}}</ref>

 

Hashing adalah contoh tradeoff ruang-waktu . Jika [[Memori (komputer)|memori]] tidak terbatas, seluruh kunci dapat digunakan secara langsung sebagai indeks untuk menemukan nilainya dengan satu akses memori. Di sisi lain, jika tersedia waktu tak terbatas, nilai dapat disimpan tanpa memperhatikan kuncinya, dan [[Algoritma pencarian biner|pencarian biner]] atau [[Pencarian linear|pencarian linier]] dapat digunakan untuk mengambil elemen. {{R|algo1rob}} <sup class="reference nowrap"><span title="Page: 458">&#x3A;&#x200A;458&#x200A;</span></sup>

 

== Referensi ==

 

<nowiki>