Dalam ilmu komputer, hashtable adalahstruktur datauntuk menyimpan data yang terdiri dari daftar nilai, yang disebut kunci, yang dipasangkan dengan daftar nilai yang sesuai, yang disebut array.Misalnya, nama bisnis mungkin dipasangkan dengan alamatnya.Biasanya, setiap nilai dalam array memiliki nomor posisi yang disebut sebagai hash.Fungsihashumumnya adalah sekumpulan instruksi ataualgoritmeyang memetakan setiap nilai kunci ke hash — menghubungkan nama bisnis ke alamatnya, nomor teleponnya, dan kategori bisnisnya, misalnya.Tujuan dari fungsi hash adalah untuk menetapkan setiap kunci ke nilai unik yang sesuai dalam array;ini biasanya disebut sebagai hashing.Fungsi hash harus diformat dengan benar agar hashtable berfungsi dengan baik.
Hashtable adalah struktur data untuk menyimpan data yang terdiri dari daftar nilai, yang disebut kunci, yang dipasangkan dengan daftar nilai yang sesuai, yang disebut array.
Performa hashtable pada sekumpulan data bergantung pada efisiensi fungsi hashnya.Fungsi hash yang baik biasanya menyediakan pencarian kunci yang seragam dan pemerataan pemetaan dalam larik yang sesuai.Tabrakan hash terjadi ketika dua kunci ditetapkan ke nilai yang sama.Ketika tabrakan hash terjadi, fungsi hash biasanya dijalankan lagi sampai nilai unik yang sesuai ditemukan;ini biasanya menghasilkan waktu hashing yang lebih lama.Meskipun jumlah kunci dalam tabel hash biasanya tetap, terkadang mungkin ada kunci duplikat.Meski begitu, hashtable yang dirancang dengan baik memiliki fungsi hash efektif yang memetakan setiap kunci ke nilai unik yang sesuai dalam array.
Terkadang, fungsi hash yang tidak efisien dalam tabel hash juga dapat menghasilkan sekelompok pemetaan.Jika fungsi hash membuat sekelompok pemetaan untuk kunci yang ada, ini dapat menambah jumlah waktu yang diperlukan untuk mencari nilai yang sesuai.Ini dapat memperlambat hashing untuk kunci masa depan karena sebagian besar fungsi hash umumnya mencari posisi berikutnya yang tersedia dalam array.Jika sekelompok besar nilai telah ditetapkan, biasanya akan memakan waktu lebih lama untuk mencari nilai yang belum ditetapkan untuk kunci baru.
Faktor beban adalah konsep lain yang terkait dengan efisiensi fungsi hash;faktor beban adalah jumlah hashing yang sudah ada dalam kaitannya dengan ukuran keseluruhan dari array yang sesuai dalam tabel hash.Biasanya ditentukan dengan membagi jumlah kunci yang sudah ditetapkan dengan ukuran array yang sesuai.Saat faktor beban meningkat, fungsi hash yang baik biasanya akan tetap mempertahankan jumlah tabrakan dan klaster yang konstan hingga titik tertentu.Seringkali ambang batas ini dapat digunakan untuk menentukan seberapa efisien fungsi hash dengan sejumlah kunci tertentu dan kapan fungsi hash baru mungkin diperlukan.
Banyak peneliti ilmu komputer telah berusaha keras untuk menghasilkan fungsi hash yang sempurna — yang tidak menghasilkan tabrakan atau klaster karena faktor beban yang meningkat.Secara teori, kunci untuk menghasilkan hashtable yang sempurna adalah menghasilkan fungsi hash yang sempurna.Secara umum, para peneliti percaya bahwa fungsi hash yang sempurna harus memiliki kinerja yang konstan — jumlah tabrakan dan klaster — dengan faktor beban yang meningkat.Dalam skenario terburuk, fungsi hash yang sempurna masih memungkinkan hashing konstan tanpa mencapai ambang batas.