Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 06

Tabel hash

44 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Tabel hash mengubah kunci menjadi nomor ember dengan satu perhitungan, lalu hanya memeriksa ember itu.
  • Tabrakan pasti terjadi; chaining menyimpan list per ember, pengalamatan terbuka mencari slot lain dan butuh tanda bekas untuk menghapus.
  • Dengan sebaran merata dan faktor muat α terjaga, operasi O(1 + α) harapan; rehash berlipat membuat simpan O(1) amortisasi.
  • Kunci harus mematuhi kontrak: a == b berarti hash(a) == hash(b), dan hash tidak berubah selama di tabel.
  • Kasus terburuk Θ(n) bisa dipaksa penyerang; karena itu hash() string diacak per proses. Untuk hash yang stabil, pakai hashlib.

Sebelum mulai

±4 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: menjelaskan bagaimana fungsi hash memetakan kunci ke ember dan menilai sebarannya; menangani tabrakan dengan chaining dan pengalamatan terbuka (termasuk tanda bekas); menganalisis faktor muat, biaya harapan O(1 + α), dan pertumbuhan berlipat; menegakkan kontrak __eq__/__hash__; serta menjelaskan kenapa hash() string diacak per proses dan bagaimana hash universal bertahan dari hash flooding.

Proyek: Kurir Makmur langkah 6: TabelHash dengan chaining yang tumbuh dua kali lipat saat faktor muat melewati 0,75, untuk mengindeks pesanan per id dan per tujuan (kontrak Proyek Kurir §3).

Istilah di modul ini (11)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 30 contoh kode
  • 8 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • contoh_k1_06_37.py
  • contoh_k1_06_76.py
  • contoh_k1_06_92.py
  • contoh_k1_06_108.py
  • contoh_k1_06_232.py
  • contoh_k1_06_361.py
  • contoh_k1_06_501.py
  • contoh_k1_06_527.py
  • contoh_k1_06_563.py
  • contoh_k1_06_602.py
  • contoh_k1_06_691.py
  • contoh_k1_06_736.py
  • contoh_k1_06_993.py
  • contoh_k1_06_1031.py
  • contoh_k1_06_1067.py
  • contoh_k1_06_1096.py
  • contoh_k1_06_1126.py
  • contoh_k1_06_1149.py
  • contoh_k1_06_1271.py
  • contoh_k1_06_1316.py
  • contoh_k1_06_1342.py
  • contoh_k1_06_1704.py
  • contoh_k1_06_1745.py
  • contoh_k1_06_1762.py
  • contoh_k1_06_1802.py
  • contoh_k1_06_2053.py
  • contoh_k1_06_2306.py
  • contoh_k1_06_2352.py
  • contoh_k1_06_2402.py
  • contoh_k1_06_2420.py
  • test_k1_06_1.py
  • test_k1_06_2.py
  • test_k1_06_4.py
  • test_k1_06_3.py
  • test_k1_06_5.py
  • test_k1_06_7.py
  • test_k1_06_6.py
  • test_k1_06_8.py
  • peta.json