18以降は初級〜中級編です。
Overview
ハッシュテーブル（Hash Table） は、キーと値（Key-Value）のペアを効率的に管理するデータ構造。Python の dict はハッシュテーブルを使って実装されており、$O(1)$ の計算量でデータの検索・追加・削除が可能。
1.ハッシュテーブルの基本
2.ハッシュ関数と衝(Collision)
3.ハッシュテーブルの応用
4.典型問題を解いてみる
1. ハッシュテーブルの基本
(1) ハッシュテーブルとは？
キー（Key）をハッシュ関数で数値に変換し、対応する値（Value）を格納。
リストのインデックスのように、キーを直接検索できるため高速。
Python の dict（辞書型）はハッシュテーブルを内部で使用。
(2) Python の dict（辞書）の基本操作
# 辞書の作成
person = {"name": "Alice", "age": 25, "city": "Tokyo"}
# 値の取得
print(person["name"]) # Alice
# 値の追加・更新
person["age"] = 26
person["job"] = "Engineer"
# キーの存在チェック
print("city" in person) # True
# 値の削除
del person["city"]
# 辞書の全キー・値を取得
print(person.keys()) # dict_keys(['name', 'age', 'job'])
print(person.values()) # dict_values(['Alice', 26, 'Engineer'])
- ポイント
キーの検索・追加・削除が $O(1)$ で高速
リストとは異なり、キーを使って直接アクセス可能
キーの重複は許されない
2. ハッシュ関数と衝突（Collision）
(1) ハッシュ関数（Hash Function）とは？
キーを数値（ハッシュ値）に変換する関数。異なるキーは通常異なるハッシュ値を持つ。
(2) 衝突（Collision）とは？
異なるキーが同じハッシュ値を持つ場合、衝突が発生。
Python の dict は「オープンアドレス法」や「チェイン法」で衝突を解決している。
# Python でハッシュ値を確認
print(hash("apple")) # 毎回異なる数値
print(hash("banana"))
- ポイント
Python のdictは内部的にハッシュ関数を使ってキーを管理している。
衝突が発生しても、適切に処理されるため心配不要。
3. ハッシュテーブルの応用
(1) 頻度カウント
リスト内の要素の出現回数をカウント
from collections import Counter
words = ["apple", "banana", "apple", "orange", "banana", "apple"]
counter = Counter(words)
print(counter) # {'apple': 3, 'banana': 2, 'orange': 1}
print(counter["apple"]) # 3
- Counter を使うとキーの出現回数を簡単に数えられる
- 内部的にハッシュテーブルを利用
(2) 2つのリストを辞書に変換
keys = ["name", "age", "city"]
values = ["Alice", 25, "Tokyo"]
person = dict(zip(keys, values))
print(person) # {'name': 'Alice', 'age': 25, 'city': 'Tokyo'}
- zip() を使うとキーと値のペアを簡単に辞書に変換可能
(3) グループ化
data = [("apple", 3), ("banana", 5), ("apple", 7), ("banana", 2)]
grouped = {}
for key, value in data:
if key not in grouped:
grouped[key] = []
grouped[key].append(value)
print(grouped) # {'apple': [3, 7], 'banana': [5, 2]}
- 辞書を使うとカテゴリごとにデータを整理できる
4. 典型問題を解いてみる
例題1. 頻度カウント
問題: N 個の単語が与えられる。それぞれの単語が何回登場したかを出力せよ。
回答
from collections import Counter
N = int(input())
words = [input() for _ in range(N)]
counter = Counter(words)
for word, count in counter.items():
print(word, count)
例題2. 2つのリストを辞書に変換
問題: N 個のキーと値のペアが与えられる。辞書を作成し、指定されたキーの値を出力せよ。
回答
N = int(input())
mapping = {}
for _ in range(N):
key, value = input().split()
mapping[key] = value
Q = int(input())
for _ in range(Q):
query = input()
print(mapping.get(query, "Not Found"))
例題3. グループ化
問題: N 個のデータが与えられる。それぞれのカテゴリごとにデータをグループ化して出力せよ。
回答
N = int(input())
grouped = {}
for _ in range(N):
category, value = input().split()
if category not in grouped:
grouped[category] = []
grouped[category].append(value)
for category, values in grouped.items():
print(category, *values)
例題4. 辞書を使った最頻値の検索
問題: N 個の数値が与えられる。最も頻繁に出現する数値を出力せよ。
回答
from collections import Counter
N = int(input())
numbers = list(map(int, input().split()))
counter = Counter(numbers)
most_common = counter.most_common(1)[0][0] # 最頻値
print(most_common)
例題5. 文字列のカウント
問題: 文字列 S が与えられる。各文字の出現回数を出力せよ。
回答
from collections import Counter
S = input()
counter = Counter(S)
for char, count in sorted(counter.items()):
print(char, count)