Catatan Kuliah: Hash Tables oleh Gayle Laakmann McDowell

Pengantar

• Pembicara: Gayle Laakmann McDowell, penulis Cracking the Coding Interview
• Topik: Hash Tables
• Pentingnya: Struktur data vital untuk wawancara dan aplikasi kehidupan nyata.

Gambaran Umum tentang Hash Tables

• Definisi: Struktur data yang menyediakan pencarian key-value untuk pengambilan data yang cepat.
• Penggunaan: Mengaitkan nama seseorang dengan informasi mereka untuk akses cepat menggunakan hash tables.

Konsep Kunci

• Key dan Value: Keduanya dapat berupa tipe data apapun (misalnya, string, objek).
• Fungsi Hash: Mengonversi key menjadi bilangan bulat (kode hash), yang dipetakan ke indeks dalam array.

Implementasi

• Penyimpanan: Objek disimpan dalam sebuah array.
• Proses:
  • Mengonversi key menjadi kode hash menggunakan fungsi hash.
  • Memetakan kode hash ke indeks dalam array.
  • Mengambil nilai yang terkait dengan key dengan cepat.
• Catatan: Kode hash bukanlah indeks array; kode hash dipetakan ke indeks yang lebih kecil karena ukuran array yang terbatas.

Penanganan Tabrakan

• Tabrakan: Terjadi ketika dua key dipetakan ke indeks yang sama.
• Teknik Resolusi:
  • Chaining: Menyimpan item yang bertabrakan dalam linked list pada indeks yang sama dan mencarinya sesuai kebutuhan.

Alur Proses

1. Masukkan: Gunakan fungsi hash untuk mendapatkan kode hash, petakan ke indeks, dan masukkan nilai dalam linked list pada indeks tersebut.
2. Ambil: Hitung kode hash, petakan ke indeks, cari key dalam linked list, ambil nilai.

Kompleksitas Waktu

• Asumsi: Dengan fungsi hash yang baik, operasi (masukkan, temukan, hapus) dapat memakan waktu konstan (O(1)).
• Kasus Terburuk: Fungsi hash yang buruk dapat menyebabkan waktu linier (O(n)) karena distribusi yang buruk dan tabrakan.

Kesimpulan

• Ringkasan: Hash tables menyediakan pengambilan data yang efisien, tetapi memerlukan pemahaman tentang penanganan tabrakan dan kualitas fungsi hash.
• Rekomendasi: Pelajari lebih dalam tentang penanganan tabrakan, pengubahan skala, dan berlatih menggunakan hash tables.
• Saran: Kenali aspek dasar dan kompleks untuk wawancara dan penggunaan praktis.