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 個の単語が与えられる。それぞれの単語が何回登場したかを出力せよ。

参考： ABC315 B - Word Frequency

回答　

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 個のキーと値のペアが与えられる。辞書を作成し、指定されたキーの値を出力せよ。

参考： ABC318 B - Key Value Map

回答　

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 個のデータが与えられる。それぞれのカテゴリごとにデータをグループ化して出力せよ。

参考： ABC319 C - Grouping Data

回答　

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 個の数値が与えられる。最も頻繁に出現する数値を出力せよ。

参考： ABC320 B - Most Frequent Number

回答　

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 が与えられる。各文字の出現回数を出力せよ。

参考： ABC322 C - Character Count

回答　

from collections import Counter

S = input()
counter = Counter(S)

for char, count in sorted(counter.items()):
    print(char, count)