ハッシュテーブル

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

Miriam Antona

Software engineer

定義

• データの集合を格納する

• キーと値のペア

    lasagna: 14.75
    moussaka: 21.15
    sushi: 16.05
  

• ほぼすべてのプログラミング言語には、ハッシュテーブルが組み込まれている：

  • ハッシュ、ハッシュマップ、辞書、連想配列など
  • Python：辞書と呼んでいる

構造

• 各位置：スロットまたはバケットと呼ぶ

ハッシュ関数

ハッシュ関数

• ハッシュ関数を適用する
  • 毎回、同じ入力に対して、同じ値を返す必要がある

検索

• 「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

• 要素を取得する

print(my_menu.items())

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

• キーを取得する

print(my_menu.keys())

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

• 値を取得する

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で学ぶデータ構造とアルゴリズム