哈希表

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 字典

• 空字典

my_empty_dictionary = {}

• 含有项的字典

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

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

Python 字典 - 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 字典 - 插入

my_menu['samosas'] = 13

print(my_menu.items())

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

Python 字典 - 修改

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20

Python 字典 - 删除

• 删除整个字典

del my_menu

• 删除一个键值对

del my_menu["sushi"]

• 清空字典

my_menu.clear()

Python 字典 - 遍历

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 字典 - 遍历

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 字典 - 嵌套字典

• 嵌套字典

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

Ayo berlatih!

Python 中的数据结构与算法