Tabel hash: cara kerja dict dan set

Tabel hash menyimpan pasangan kunci dan nilai dalam larik berisi slot. Fungsi hash mengubah kunci menjadi bilangan bulat, dan bilangan itu menentukan slot tempat kunci disimpan. Mencari kunci tidak perlu membandingkannya dengan semua kunci lain: hitung hash-nya, lalu langsung buka slotnya. Karena itu biaya rata-rata mencari, menyisipkan, dan menghapus tidak bergantung pada banyaknya data. dict dan set di Python adalah tabel hash.

Dua kunci berbeda bisa jatuh ke slot yang sama. Kejadian ini disebut tabrakan, dan tabel hash punya cara menyelesaikannya, misalnya mencari slot lain atau menyimpan beberapa kunci di satu slot. Tabrakan yang sedikit tidak terasa; itu sebabnya biaya tetap tadi disebut rata-rata, bukan jaminan untuk setiap operasi. Tabel hash juga tidak menyimpan urutan berdasarkan nilai kunci, jadi untuk data yang perlu diurut tetap dibutuhkan pengurutan.

kode_aktif = {"BRG-01", "BRG-07", "BRG-12"}   # set
harga = {"BRG-01": 12500, "BRG-07": 8000}   # dict

print("BRG-07" in kode_aktif)   # True, tanpa memeriksa satu per satu
print(harga.get("BRG-99", 0))   # 0, kunci tidak ada

Kunci dict dan anggota set harus hashable: nilai hash-nya tidak boleh berubah selama objek hidup. Tipe bawaan yang tidak bisa diubah seperti str, int, dan tuple berisi nilai hashable memenuhi syarat itu. list dan dict tidak, karena isinya bisa berubah sesudah disimpan dan hash-nya akan menunjuk slot yang salah. Pencarian x in daftar pada list memeriksa data satu per satu; pada set cukup satu perhitungan hash.