Struktur Linear · Pelajaran 6 dari 10
Hash table
10 menit baca · BelajarCode
Hash table menyimpan pasangan kunci dan nilai. Kuncinya diubah oleh fungsi hash menjadi sebuah bilangan, lalu bilangan itu dipakai sebagai indeks array. Karena indeks dihitung langsung, pencarian rata-rata O(1). dict dan set di Python adalah hash table.
Fungsi hash dan tabrakan
Fungsi hash yang baik menyebarkan kunci secara merata. Tetapi karena kemungkinan kunci jauh lebih banyak daripada ukuran array, dua kunci berbeda bisa mendapat indeks yang sama. Kejadian ini disebut tabrakan (collision). Salah satu cara menanganinya adalah chaining: setiap posisi array berisi daftar pasangan.
1class HashTable:2 def __init__(self, ukuran=8):3 self.ember = [[] for _ in range(ukuran)]4 self.banyak = 056 def _hash(self, kunci):7 nilai = 08 for karakter in kunci:9 nilai = (nilai * 31 + ord(karakter)) % 1_000_000_00710 return nilai % len(self.ember)1112 def simpan(self, kunci, nilai):13 daftar = self.ember[self._hash(kunci)]14 for i, (k, _) in enumerate(daftar):15 if k == kunci:16 daftar[i] = (kunci, nilai)17 return18 daftar.append((kunci, nilai))19 self.banyak += 120 if self.banyak / len(self.ember) > 0.75:21 self._perbesar()2223 def ambil(self, kunci):24 for k, v in self.ember[self._hash(kunci)]:25 if k == kunci:26 return v27 raise KeyError(kunci)2829 def _perbesar(self):30 lama = self.ember31 self.ember = [[] for _ in range(len(lama) * 2)]32 self.banyak = 033 for daftar in lama:34 for k, v in daftar:35 self.simpan(k, v)363738nilai = HashTable()39for nama, n in [("andi", 80), ("bela", 92), ("citra", 75), ("dimas", 88),40 ("eka", 70), ("fajar", 95), ("gita", 81)]:41 nilai.simpan(nama, n)42print("Nilai fajar:", nilai.ambil("fajar"))43print("Ukuran array:", len(nilai.ember))44print("Isi tiap ember:", [len(e) for e in nilai.ember])Nilai fajar: 95 Ukuran array: 16 Isi tiap ember: [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]
Faktor muatan
Faktor muatan (load factor) adalah banyak data dibagi ukuran array. Jika terlalu tinggi, setiap ember berisi banyak data dan pencarian melambat. Karena itu hash table memperbesar arraynya saat faktor muatan melewati batas tertentu, pada contoh ini 0,75, lalu memasukkan ulang semua data. Seperti array dinamis, biaya ini teramortisasi menjadi O(1).
Kunci harus tidak bisa diubah
Kunci dict dan isi set di Python harus hashable, biasanya berarti tidak bisa diubah: angka, string, dan tuple boleh, list tidak boleh. Jika kunci bisa diubah setelah disimpan, nilai hash-nya berubah dan datanya tidak bisa ditemukan lagi.
Cek pemahaman
Apa yang dimaksud tabrakan (collision) pada hash table?
Latihan
Dua angka berjumlah target
Diberikan list angka dan sebuah target, kembalikan indeks dua angka yang jumlahnya sama dengan target. Gunakan dictionary supaya cukup satu kali lintasan, O(n).
Pembahasan
1def dua_jumlah(angka, target):2 dilihat = {}3 for i, x in enumerate(angka):4 pasangan = target - x5 if pasangan in dilihat:6 return dilihat[pasangan], i7 dilihat[x] = i8 return None910print(dua_jumlah([7, 2, 11, 15, 4], 6))11print(dua_jumlah([3, 3], 6))12print(dua_jumlah([1, 2, 3], 100))(1, 4) (0, 1) None
Dictionary menyimpan angka yang sudah dilihat beserta indeksnya. Untuk setiap angka x, cukup periksa apakah target - x pernah muncul, operasi O(1) rata-rata.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.