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

^ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, hlm. 81–98
^ 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 asli tanggal August 7, 2009.
^ Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (edisi ke-dua). Addison-Wesley. hlm. 513–558. ISBN 978-0-201-89685-5.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (edisi ke-dua). MIT Press and McGraw-Hill. hlm. 221–252. ISBN 978-0-262-53196-2.

[ms2-1] Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, hlm. 81–98

[leiser-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 asli tanggal August 7, 2009.

[knuth-3] Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (edisi ke-dua). Addison-Wesley. hlm. 513–558. ISBN 978-0-201-89685-5.

[cormen-4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (edisi ke-dua). MIT Press and McGraw-Hill. hlm. 221–252. ISBN 978-0-262-53196-2.

[1]

[2]

[3]

[4]