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

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Array
·Konsep fungsi

Real-World Uses

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

Complexity O(1) rata-rata