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. 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. 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.