Apa itu hashtable?

Dalam ilmu komputer, 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.Misalnya, nama bisnis mungkin dipasangkan dengan alamatnya.Biasanya, setiap nilai dalam array memiliki nomor posisi yang disebut hash.Fungsi hash umumnya adalah satu set instruksi atau algoritma yang memetakan setiap nilai kunci ke hash mdash;Menghubungkan nama bisnis ke alamatnya, nomor teleponnya dan kategori bisnisnya, misalnya.Tujuan dari fungsi hash adalah untuk menetapkan setiap kunci ke nilai yang sesuai unik dalam array;Ini biasanya disebut sebagai hashing.Fungsi hash harus diformat dengan benar agar hashtable berfungsi dengan baik.

Kinerja hashtable pada satu set data tergantung pada efisiensi fungsi hashnya.Fungsi hash yang baik biasanya menyediakan pencarian kunci yang seragam dan distribusi pemetaan yang sama dalam array yang sesuai.Tabrakan hash terjadi ketika dua tombol ditugaskan ke nilai yang sama.Ketika tabrakan hash terjadi, fungsi hash biasanya dieksekusi lagi sampai nilai yang sesuai unik ditemukan;Ini biasanya menghasilkan waktu hashing yang lebih lama.Meskipun jumlah kunci dalam hashtable biasanya diperbaiki, kadang -kadang mungkin ada tombol duplikat.Meski begitu, hashtable yang dirancang dengan baik memiliki fungsi hash efektif yang memetakan setiap kunci ke nilai yang sesuai unik dalam array.

Terkadang, fungsi hash yang tidak efisien dalam hashtable juga dapat menghasilkan sekelompok pemetaan.Jika fungsi hash membuat sekelompok pemetaan untuk kunci yang ada, ini dapat meningkatkan 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 yang tersedia berikutnya dalam array.Jika sekelompok nilai besar telah ditetapkan, biasanya akan membutuhkan 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 array yang sesuai di hashable.Biasanya didefinisikan dengan membagi jumlah kunci yang sudah ditetapkan dengan ukuran array yang sesuai.Ketika faktor beban meningkat, fungsi hash yang baik biasanya masih akan mempertahankan jumlah tabrakan dan kelompok yang konstan hingga titik tertentu.Seringkali ambang batas ini dapat digunakan untuk menentukan seberapa efisien fungsi hash dengan sejumlah kunci tertentu dan ketika fungsi hash baru mungkin diperlukan.

Banyak peneliti ilmu komputer telah berusaha untuk menghasilkan fungsi hash yang sempurna mdash;Salah satu yang tidak menghasilkan tabrakan atau kelompok yang diberikan faktor beban yang meningkat.Secara teori, kunci untuk menghasilkan hashtable yang sempurna adalah dengan menghasilkan fungsi hash yang sempurna.Secara umum, para peneliti percaya bahwa fungsi hash yang sempurna harus memiliki kinerja mdash yang konstan;jumlah tabrakan dan kelompok mdash;dengan faktor beban yang meningkat.Dalam skenario terburuk, fungsi hash yang sempurna masih memungkinkan hashing konstan tanpa mencapai ambang batas.