Struktur DataMenengahFase D–FE1E5

Hash Table

Hash Table memetakan kunci ke indeks bucket lewat fungsi hash sehingga pencarian rata-rata O(1). Bila dua kunci jatuh ke bucket sama (tabrakan), keduanya disambung dalam rantai (chaining). Cara kerja dictionary/map di balik layar.

Contoh kasus

Struktur dictionary di banyak bahasa pemrograman: menyimpan dan mencari nilai berdasarkan kunci secara instan.

Silabus

Fungsi hash memetakan kunci langsung ke lokasi bucket, sehingga menyimpan dan mencari data rata-rata secepat O(1).

Tujuan Belajar

·Memahami peran fungsi hash mengubah kunci jadi indeks bucket
·Menjelaskan cara menangani tabrakan lewat rantai (chaining)
·Menerapkan hash table sebagai dictionary/map

Cara Kerja

·Ubah kunci menjadi indeks bucket lewat fungsi hash
·Simpan nilai pada bucket sesuai indeks tersebut
·Untuk mencari, hitung ulang hash kunci lalu buka bucketnya
·Bila dua kunci jatuh ke bucket sama, sambung dalam rantai
·Telusuri rantai bucket itu untuk temukan kunci yang tepat

Prasyarat

·Array
·Konsep fungsi

Contoh Nyata

·Struktur dictionary/map di balik banyak aplikasi dan bahasa program
·Cache username agar cek ketersediaan akun terasa instan

Kompleksitas O(1) rata-rata