Internal Fungsi Hash dan Penanganan Tabrakan
Pahami cara Python melakukan hashing terhadap objek, cara open addressing dan chaining mengatasi tabrakan, serta alasan O(1) rata-rata dapat menurun menjadi O(n).
Internal Fungsi Hash dan Penanganan Tabrakan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Peta Hash?
Peta hash (kamus dalam Python) memetakan kunci ke data menggunakan fungsi hash yang mengubah kunci apa pun menjadi indeks bilangan bulat ke dalam larik yang mendasarinya. Fungsi hash ideal menyebarkan kunci secara merata ke seluruh larik, sehingga memungkinkan pencarian, penyisipan, dan penghapusan pada kasus rata-rata O(1). Larik yang mendasarinya disebut tabel hash atau larik wadah.
Dalam Python, dict adalah peta hash yang sangat dioptimalkan. Memahami internalnya membantu Anda menalar perilaku kasus terburuk dan memilih kunci yang tepat.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Fungsi Hash dan Metode __hash__
Python memanggil __hash__(key) untuk menghitung bilangan bulat dari kunci, lalu mengambil sisa pembagian bilangan tersebut dengan ukuran tabel untuk menemukan indeks wadah. Tipe bawaan seperti int, str, dan tuple memiliki implementasi hash bawaan yang cepat. list dan dict tidak dapat di-hash (keduanya dapat diubah, dan perubahan pada keduanya akan membuat hash yang tersimpan tidak valid).
Fungsi hash yang baik mendistribusikan kunci secara merata, bersifat deterministik, dan cepat dihitung. Hash string Python diacak pada setiap proses (sebagai fitur keamanan) — gunakan PYTHONHASHSEED=0 untuk menonaktifkannya demi hasil yang dapat direproduksi dalam pengujian.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Tabrakan: Saat Hash Dua Kunci Mengarah ke Wadah yang Sama
Tabrakan terjadi ketika dua kunci berbeda menghasilkan indeks wadah yang sama. Tabrakan tidak dapat dihindari (berdasarkan prinsip sarang merpati: jumlah kunci tidak terbatas, sedangkan jumlah wadah terbatas). Dua strategi penyelesaian standar adalah perantaian dan pengalamatan terbuka. Python menggunakan varian pengalamatan terbuka dengan penelusuran semu-acak.
Perantaian menyimpan daftar berantai (atau larik dinamis) pada setiap wadah; semua kunci yang bertabrakan pada wadah tersebut membentuk satu rantai. Pengalamatan terbuka mencari wadah kosong berikutnya berdasarkan urutan penelusuran.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NonePengalamatan Terbuka: Penelusuran Linear
Dalam penelusuran linear, ketika terjadi tabrakan pada indeks i, peta memeriksa i+1, i+2, ... (kembali ke awal jika mencapai ujung) hingga menemukan slot kosong. Pencarian harus menelusuri urutan yang sama untuk menemukan kunci tersebut. Penghapusan memerlukan penanda khusus, bukan mengosongkan slot, agar rantai penelusuran tidak terputus.
Pengelompokan adalah kelemahan utama: setelah sekelompok slot terisi terbentuk, penyisipan berikutnya ke area tersebut memperbesar kelompok itu, sehingga kinerja menurun hingga mendekati O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Faktor Muatan dan Pengubahan Ukuran
Faktor muatan adalah perbandingan antara entri yang tersimpan dan kapasitas total: α = n/m. Saat α meningkat, kemungkinan tabrakan bertambah dan kinerja menurun. Dict Python mengubah ukuran (menggandakan kapasitas) ketika faktor muatan melebihi sekitar 2/3. Pengubahan ukuran menghitung ulang hash semua entri yang ada ke dalam tabel baru yang lebih besar — operasi O(n) yang jarang terjadi, sehingga biaya penyisipan teramortisasi tetap O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) Rata-rata vs O(n) Kasus Terburuk
Dengan fungsi hash yang baik, tabrakan jarang terjadi dan panjang rantai yang diharapkan tetap konstan, terlepas dari n. Karena itu, pencarian, penyisipan, dan penghapusan pada kasus rata-rata adalah O(1). Namun, skenario kasus terburuk — misalnya masukan yang sengaja dirancang agar semua kunci masuk ke wadah yang sama — menurunkan semua operasi menjadi O(n). Benih hash acak Python mengurangi dampak serangan ini, tetapi secara teoretis tidak menghilangkan kasus terburuk.
Untuk analisis wawancara, katakanlah 'O(1) pada rata-rata, O(n) pada kasus terburuk karena tabrakan'.
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyPeta Hash Python vs Peta dengan Nilai Bawaan vs Penghitung
Python menyediakan tiga varian peta hash yang perlu diketahui. dict adalah peta serbaguna; mengakses kunci yang tidak ada akan memunculkan KeyError. defaultdict(factory) mengembalikan nilai bawaan saat kunci yang diakses tidak ada (berguna untuk mengumpulkan larik atau menghitung). Counter adalah subkelas khusus untuk menghitung objek yang dapat di-hash; tipe ini juga mendukung operasi aritmetika antarpenghitung.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionPeta Hash vs Himpunan Hash
Himpunan hash hanya menyimpan kunci (tanpa nilai terkait), serta mendukung pengujian keanggotaan, penyisipan, dan penghapusan dalam O(1). set Python adalah himpunan hash. Gunakan himpunan jika Anda hanya perlu menjawab 'apakah elemen ini ada?' tanpa menyimpan data terkait. Gunakan kamus jika Anda perlu mengaitkan nilai (jumlah, hasil, dan sebagainya) dengan kunci.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Mengimplementasikan Peta Hash dari Nol (Versi Wawancara)
Pewawancara terkadang meminta Anda mengimplementasikan peta hash dasar. Komponen utamanya adalah: larik wadah berukuran tetap (gunakan 16 atau 1024), setiap wadah berupa daftar pasangan (kunci, nilai) untuk perantaian, fungsi hash (gunakan hash bawaan Python % kapasitas), serta pengubahan ukuran ketika faktor muatan melebihi 0,7. Menyebutkan pengubahan ukuran dan faktor muatan secara proaktif menunjukkan kedalaman pengetahuan.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedSaat Peta Hash Gagal: Kunci yang Tidak Dapat Di-hash
Hanya objek yang dapat di-hash yang dapat menjadi kunci kamus. Dalam Python, objek dapat di-hash jika memiliki metode __hash__ dan metode __eq__, serta nilai hash-nya tidak berubah selama masa hidupnya. Larik, himpunan, dan kamus dapat diubah, sehingga tidak dapat di-hash. Tuple dan himpunan beku merupakan alternatif yang dapat di-hash untuk larik dan himpunan jika digunakan sebagai kunci.
Jebakan umum dalam wawancara: pengelompokan anagram mengharuskan penggunaan tuple terurut (bukan larik terurut) sebagai kunci kamus.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Ringkasan: Kompleksitas Peta Hash
Peta hash memberikan operasi penyisipan, penghapusan, dan pencarian dengan kompleksitas rata-rata O(1) — dasar bagi banyak solusi wawancara yang optimal. Asumsi utamanya adalah: fungsi hash yang baik mendistribusikan kunci secara merata, faktor muatan tetap terbatas (pengubahan ukuran mempertahankan kondisi ini), dan objek kunci tidak dapat diubah serta dapat di-hash. Jika asumsi ini terpenuhi, peta hash mengubah pemindaian linear O(n) menjadi pencarian O(1), sehingga memungkinkan solusi seperti Jumlah Dua dalam O(n), bukan O(n²).
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: peta hash memetakan kunci ke indeks wadah menggunakan fungsi hash dan mencapai operasi kasus rata-rata O(1), tabrakan diselesaikan melalui perantaian (daftar berantai per wadah) atau pengalamatan terbuka (menelusuri slot kosong berikutnya), dan hanya objek yang tidak dapat diubah serta dapat di-hash yang dapat menjadi kunci kamus — gunakan tuple, bukan larik, jika diperlukan kunci berupa urutan. Selanjutnya kita akan menyelesaikan Jumlah Dua dan berbagai variannya dalam wawancara.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Internal Fungsi Hash dan Penanganan Tabrakan” gratis?
Ya — teks lengkap “Internal Fungsi Hash dan Penanganan Tabrakan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Internal Fungsi Hash dan Penanganan Tabrakan”?
Pahami cara Python melakukan hashing terhadap objek, cara open addressing dan chaining mengatasi tabrakan, serta alasan O(1) rata-rata dapat menurun menjadi O(n). Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Internal Fungsi Hash dan Penanganan Tabrakan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Internal Fungsi Hash dan Penanganan Tabrakan
- Two-Sum dan Berbagai Variasinya
- Penghitungan Frekuensi dan Pengelompokan
- Urutan Berurutan Terpanjang dan Cache LRU