C DSALesson 64Preview gratis
C Hash Tables
Lesson ini bagian dari C · Semua level
Ringkasan
Hash table menyimpan pasangan kunci dan nilai dengan mengubah kunci menjadi indeks array melalui fungsi hash, sehingga akses rata-rata berlangsung sangat cepat mendekati O(1). Karena dua kunci berbeda bisa menghasilkan indeks yang sama, diperlukan penanganan collision melalui chaining berupa linked list per bucket atau open addressing yang mencari slot kosong berikutnya. Kualitas fungsi hash dan load factor menentukan apakah performa tetap baik saat data bertambah.
Poin kunci
- Posisi data ditentukan oleh hash(k) modulo kapasitas tabel.
- Collision adalah dua kunci yang jatuh ke bucket sama; selesaikan dengan chaining atau probing terbuka.
- Load factor adalah rasio jumlah data terhadap kapasitas; bila terlalu tinggi tabel perlu diperbesar.
- Rata-rata operasi insert, search, dan delete mendekati O(1), tetapi bisa menjadi O(n) bila semua kunci bentrok.
- Fungsi hash yang baik harus cepat dihitung, merata, dan selalu konsisten untuk kunci yang sama.
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.