雜湊表

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

定義

• 儲存一組項目

• 鍵值對

    lasagna: 14.75
    moussaka: 21.15
    sushi: 16.05
  

• 幾乎所有程式語言都內建雜湊表：

  • hashes、hash maps、dictionaries、associative arrays
  • Python：dictionaries

結構

• 每個位置：slot/bucket

雜湊函式

雜湊函式

• 每次套用雜湊函式
  • 對於相同輸入必須回傳相同值

查找

• 尋找「lasagna」
  • hash("lasagna") -> 5

查找

• 尋找「lasagna」
  • hash("lasagna") -> 5
  • 回傳 14.75
• $O(1)$

衝突

• 雜湊函式可能對不同輸入回傳相同輸出
• hash("moussaka") -> 1

• 插入：moussaka -> 21.15
• 衝突！
  • 必須解決
  • 有多種技術

Python dictionary

• 空的 dictionary

my_empty_dictionary = {}

• 含項目的 dictionary

my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}

Python dictionary - 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

Python dictionary - items、keys 與 values

• 取得 items

print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])

• 取得 keys

print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])

• 取得 values

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Python dictionary - 插入

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])

Python dictionary - 修改

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20

Python dictionary - 移除

• 完全刪除整個 dictionary

del my_menu

• 移除一組鍵值對

del my_menu["sushi"]

• 清空 dictionary

my_menu.clear()

Python dictionary - 迭代

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

Python dictionary - 迭代

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05

Python dictionary - 巢狀字典

• 巢狀 dictionary

my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}

一起來練習吧！

Data Structures and Algorithms in Python