Tabel hash

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Definisi

  • Menyimpan kumpulan item

  • Pasangan kunci-nilai

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Hampir semua bahasa pemrograman punya tabel hash bawaan:

    • hashes, hash maps, dictionaries, associative arrays
    • Python: dictionaries
Struktur Data dan Algoritma di Python

Struktur

  • Tiap posisi: slot/bucket

Representasi skematis tabel hash kosong.

Struktur Data dan Algoritma di Python

Fungsi hash

Representasi skematis tabel hash kosong. Harga lasagna dimasukkan pada posisi kelima.

Struktur Data dan Algoritma di Python

Fungsi hash

Representasi skematis tabel hash dengan kata "Fungsi hash" di tengah panah yang memetakan kata "Lasagna" ke nilai pada posisi kelima.

  • Setiap kali fungsi hash diterapkan
    • harus mengembalikan nilai yang sama untuk masukan yang sama
Struktur Data dan Algoritma di Python

Pencarian

Representasi skematis tabel hash dengan beberapa nilai.

  • Cari "lasagna"
    • hash("lasagna") -> 5
Struktur Data dan Algoritma di Python

Pencarian

Representasi skematis tabel hash dengan beberapa nilai. Nilai pada posisi kelima berwarna hijau.

  • Cari "lasagna"
    • hash("lasagna") -> 5
    • kembalikan 14,75
  • $O(1)$
Struktur Data dan Algoritma di Python

Tabrakan (collision)

  • Fungsi hash bisa mengembalikan keluaran yang sama untuk masukan berbeda
  • hash("moussaka") -> 1

Representasi skematis tabel hash dengan beberapa nilai. Nilai pada posisi pertama berwarna kuning.

  • sisipkan: moussaka -> 21,15
  • Tabrakan!
    • harus diselesaikan
    • beberapa teknik
Struktur Data dan Algoritma di Python

Dictionary Python

  • Kamus kosong
my_empty_dictionary = {}
  • Kamus dengan item
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Struktur Data dan Algoritma di Python

Dictionary Python - get

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None
Struktur Data dan Algoritma di Python

Dictionary Python - items, keys & values

  • Ambil item
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • Ambil kunci
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • Ambil nilai
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Struktur Data dan Algoritma di Python

Dictionary Python - insert

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Struktur Data dan Algoritma di Python

Dictionary Python - modify

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Struktur Data dan Algoritma di Python

Dictionary Python - remove

  • Menghapus dictionary sepenuhnya
del my_menu
  • Menghapus sepasang kunci-nilai
del my_menu["sushi"]
  • Mengosongkan dictionary
my_menu.clear()
Struktur Data dan Algoritma di Python

Dictionary Python - iterasi

for key, value in my_menu.items():
  print(f"\nkey: {key}")
  print(f"value: {value}")

key: lasagna
value: 14.75

key: moussaka
value: 21.15

key: sushi
value: 16.05
Struktur Data dan Algoritma di Python

Dictionary Python - iterasi

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05
Struktur Data dan Algoritma di Python

Dictionary Python - nested dictionaries

  • Dictionary bertingkat (nested)
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Struktur Data dan Algoritma di Python

Ayo berlatih!

Struktur Data dan Algoritma di Python

Preparing Video For Download...