ハッシュテーブル

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

定義

• 要素の集合を保持

• キーと値の組

    lasagna: 14.75
    moussaka: 21.15
    sushi: 16.05
  

• ほぼ全言語に組み込みあり:

  • hash, hash map, dictionary, 連想配列
  • Python: 辞書（dictionary）

構造

• 各位置は「スロット/バケット」

ハッシュ関数

ハッシュ関数

• 毎回ハッシュ関数を適用すると
  • 同じ入力には必ず同じ値を返す

検索

• 「lasagna」を探す
  • hash("lasagna") -> 5

検索

• 「lasagna」を探す
  • hash("lasagna") -> 5
  • 14.75 を返す
• $O(1)$

衝突

• 異なる入力でも同じ出力になることがある（ハッシュ関数）
• hash("moussaka") -> 1

• 追加: moussaka -> 21.15
• 衝突（Collision）
  • 解決が必要
  • 複数の手法

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'
  }
}

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム