《アルゴリズムを学ぶ》18.ハッシュテーブル

18以降は初級〜中級編です。
# Overview
ハッシュテーブル（Hash Table） は、キーと値（Key-Value）のペアを効率的に管理するデータ構造。Python の `dict` はハッシュテーブルを使って実装されており、$O(1)$ の計算量でデータの検索・追加・削除が可能。
[1.ハッシュテーブルの基本](#1-ハッシュテーブルの基本)
[2.ハッシュ関数と衝(Collision)](#2-ハッシュ関数と衝突collision)
[3.ハッシュテーブルの応用](#3-ハッシュテーブルの応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. ハッシュテーブルの基本
### (1) ハッシュテーブルとは？
キー（Key）をハッシュ関数で数値に変換し、対応する値（Value）を格納。
リストのインデックスのように、キーを直接検索できるため高速。
Python の `dict`（辞書型）はハッシュテーブルを内部で使用。

### (2) Python の dict（辞書）の基本操作
```python
# 辞書の作成
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
# Python でハッシュ値を確認
print(hash("apple"))  # 毎回異なる数値
print(hash("banana"))
```
- ポイント
Python の `dict` は内部的にハッシュ関数を使ってキーを管理している。
衝突が発生しても、適切に処理されるため心配不要。

# 3. ハッシュテーブルの応用
### (1) 頻度カウント
リスト内の要素の出現回数をカウント
```python
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つのリストを辞書に変換
```python
keys = ["name", "age", "city"]
values = ["Alice", 25, "Tokyo"]

person = dict(zip(keys, values))
print(person)  # {'name': 'Alice', 'age': 25, 'city': 'Tokyo'}
```
- zip() を使うとキーと値のペアを簡単に辞書に変換可能

### (3) グループ化
```python
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](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題2. 2つのリストを辞書に変換
**問題: N 個のキーと値のペアが与えられる。辞書を作成し、指定されたキーの値を出力せよ。**
> [参考： ABC318 B - Key Value Map](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
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"))
```
</details>

### 例題3. グループ化
**問題: N 個のデータが与えられる。それぞれのカテゴリごとにデータをグループ化して出力せよ。**
> [参考： ABC319 C - Grouping Data](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題4. 辞書を使った最頻値の検索
**問題: N 個の数値が与えられる。最も頻繁に出現する数値を出力せよ。**
> [参考： ABC320 B - Most Frequent Number](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題5. 文字列のカウント
**問題: 文字列 S が与えられる。各文字の出現回数を出力せよ。**
> [参考： ABC322 C - Character Count](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
from collections import Counter

S = input()
counter = Counter(S)

for char, count in sorted(counter.items()):
    print(char, count)
```
</details>