Tabel hash

Buku telepon kecil sebagai tabel hash

Dalam 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.[1] Tabel hash menggunakan 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.[2] [3] [4]

Hashing adalah contoh trade-off ruang-waktu. Jika 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 pencarian biner atau pencarian linier dapat digunakan untuk mengambil elemen.

Referensi

  1. ^ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, hlm. 81–98
  2. ^ Leiserson, Charles E. (Fall 2005). "Lecture 13: Amortized Algorithms, Table Doubling, Potential Method". course MIT 6.046J/18.410J Introduction to Algorithms. Diarsipkan dari versi aslinya tanggal August 7, 2009.
  3. ^ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (Edisi dua). Addison-Wesley. hlm. 513–558. ISBN 978-0-201-89685-5.
  4. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (Edisi dua). MIT Press and McGraw-Hill. hlm. 221–252. ISBN 978-0-262-53196-2.

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.