配列とハッシュテーブル ── 最も使うデータ構造の内部構造
扱う概念：動的配列（Dynamic Array）、ハッシュ関数、衝突解決（チェイニング / オープンアドレス法）、負荷率とリハッシュ
この章で何ができるようになるか：配列とハッシュテーブルの内部動作を説明でき、「O(1) で検索できるのはなぜか」「なぜ最悪 O(n) になるか」を理解できる。
配列（Array）：メモリ上の連続した箱
配列は「同じ型のデータがメモリ上で隣り合って並んでいる」データ構造だ。
メモリ上のイメージ：
アドレス: 1000 1008 1016 1024 1032
値: [42] [17] [93] [28] [65]
インデックス: 0 1 2 3 4
arr[3] のアドレス = 先頭アドレス + (インデックス × 要素サイズ)
= 1000 + (3 × 8) = 1024
→ O(1) で直接アクセスできる（算術計算だけ）操作ごとの計算量
| 操作 | 計算量 | 理由 |
|---|---|---|
インデックスアクセス arr[i] | O(1) | アドレス計算だけ |
末尾に追加 append | O(1) 償却 | 容量不足時のみ再確保 |
| 先頭に挿入 | O(n) | 全要素を1つ右にシフト |
中間に挿入 insert(i, x) | O(n) | i 以降を右にシフト |
| 値で検索 | O(n) | 先頭から順に走査 |
末尾を削除 pop() | O(1) | |
中間を削除 pop(i) | O(n) | i 以降を左にシフト |
動的配列の実装
Python の list や Java の ArrayList は動的配列──容量が足りなくなると自動で拡張する。
class DynamicArray:
def __init__(self):
self._capacity = 4 # 初期容量
self._size = 0 # 現在の要素数
self._data = [None] * self._capacity
def append(self, value):
if self._size == self._capacity:
self._resize(self._capacity * 2) # 2倍に拡張
self._data[self._size] = value
self._size += 1
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i] # O(n) のコピー
self._data = new_data
self._capacity = new_capacity
def __getitem__(self, index):
if index < 0 or index >= self._size:
raise IndexError
return self._data[index] # O(1)
def __len__(self):
return self._sizeなぜ2倍に拡張するのか：1.5倍でもいいが、倍率が小さいほどリサイズ頻度が増える。2倍なら n 回の append で合計コピー回数は n + n/2 + n/4 + … ≈ 2n → 償却 O(1)。
ハッシュテーブル（Hash Table）：O(1) 検索の仕組み
「キーから値を O(1) で引ける」──Python の dict、Java の HashMap の内部構造。
ハッシュ関数
キー → 配列のインデックスへの変換。
def simple_hash(key: str, table_size: int) -> int:
"""単純なハッシュ関数"""
h = 0
for char in key:
h = h * 31 + ord(char) # 31 は素数（衝突が少ない経験則）
return h % table_size
simple_hash("hello", 16) # → 9（インデックス9 に格納）
simple_hash("world", 16) # → 3良いハッシュ関数の条件：
- 決定的（同じキーは必ず同じ値を返す）
- 均一分布（インデックスが偏らない）
- 高速（O(1) に近い計算コスト）
衝突（Collision）
異なるキーが同じインデックスになること。鳩の巣原理：テーブルサイズ m に m+1 個のキーを入れたら、必ず衝突が起きる。
衝突解決1：チェイニング（Separate Chaining）
各スロットにリンクリストを持つ。
class HashTableChaining:
def __init__(self, capacity: int = 16):
self._capacity = capacity
self._size = 0
self._buckets: list[list[tuple]] = [[] for _ in range(capacity)]
self._load_factor_threshold = 0.75
def _hash(self, key) -> int:
return hash(key) % self._capacity
def put(self, key, value):
idx = self._hash(key)
bucket = self._buckets[idx]
# 既存キーの更新
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
# 新規追加
bucket.append((key, value))
self._size += 1
# 負荷率チェック → リハッシュ
if self._size / self._capacity > self._load_factor_threshold:
self._rehash()
def get(self, key):
idx = self._hash(key)
for k, v in self._buckets[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
bucket = self._buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
self._size -= 1
return
raise KeyError(key)
def _rehash(self):
"""テーブルを2倍に拡張して全要素を再配置"""
old_buckets = self._buckets
self._capacity *= 2
self._buckets = [[] for _ in range(self._capacity)]
self._size = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)衝突解決2：オープンアドレス法（Open Addressing）
衝突したら次の空きスロットを探す。Python の dict はこちらを採用。
class HashTableOpenAddressing:
EMPTY = object()
DELETED = object() # 削除マーカー（墓石）
def __init__(self, capacity: int = 16):
self._capacity = capacity
self._size = 0
self._keys = [self.EMPTY] * capacity
self._values = [None] * capacity
def _probe(self, key, for_insert: bool = False) -> int:
"""線形探索（Linear Probing）"""
idx = hash(key) % self._capacity
first_deleted = -1
for _ in range(self._capacity):
if self._keys[idx] is self.EMPTY:
return first_deleted if (for_insert and first_deleted >= 0) else idx
if self._keys[idx] is self.DELETED:
if first_deleted < 0:
first_deleted = idx
elif self._keys[idx] == key:
return idx
idx = (idx + 1) % self._capacity # 次のスロットへ
return first_deleted if first_deleted >= 0 else -1
def put(self, key, value):
if self._size / self._capacity > 0.7:
self._rehash()
idx = self._probe(key, for_insert=True)
if self._keys[idx] is self.EMPTY or self._keys[idx] is self.DELETED:
self._size += 1
self._keys[idx] = key
self._values[idx] = value
def get(self, key):
idx = self._probe(key)
if self._keys[idx] is self.EMPTY or self._keys[idx] is self.DELETED:
raise KeyError(key)
return self._values[idx]チェイニング vs オープンアドレス法
| チェイニング | オープンアドレス法 | |
|---|---|---|
| 負荷率 > 1 | ✅ 問題なし | ❌ 不可能 |
| キャッシュ効率 | △ リスト参照が散らばる | ✅ メモリが連続（高速） |
| 削除 | ✅ リスト要素の削除 | △ 墓石（DELETED）が必要 |
| 実装の複雑さ | 低 | 中 |
| 採用例 | Java HashMap | Python dict, Rust HashMap |
負荷率（Load Factor）とリハッシュ
負荷率 = 要素数 / テーブル容量
負荷率が高いと：
チェイニング → リストが長くなり O(n/m) に劣化
オープンアドレス → クラスタリング（連続した埋まりブロック）が発生
一般的なしきい値：
Java HashMap: 0.75
Python dict: 0.67（2/3）
Go map: 0.65（6.5/10）面接頻出問題
Two Sum（O(n) 解法）
def two_sum(nums: list[int], target: int) -> list[int]:
"""ハッシュテーブルで「今まで見た値」を記録する"""
seen = {} # {値: インデックス}
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) 検索
return [seen[complement], i]
seen[num] = i # O(1) 挿入
return []
# 全体: O(n) 時間、O(n) 空間
# ❌ 素朴な二重ループは O(n²)Group Anagrams
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
"""ソートした文字列をキーにしてグルーピング"""
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # "eat" → ('a', 'e', 't')
groups[key].append(s)
return list(groups.values())
# O(n × k log k) n=文字列数, k=最長文字列長まとめ
| データ構造 | 検索 | 挿入 | 削除 | 順序 | 実際の使用例 |
|---|---|---|---|---|---|
| 配列 | O(n) / O(1)※ | O(n) / O(1)※※ | O(n) | ✅ 保持 | リスト、バッファ |
| ハッシュテーブル | O(1) 平均 | O(1) 平均 | O(1) 平均 | ❌ なし | dict, cache, index |
※ インデックスアクセスの場合 / ※※ 末尾追加の場合
ハッシュテーブルの「O(1)」はハッシュ関数の品質と負荷率の管理に依存する。最悪ケース（全キーが同じスロットに衝突）は O(n) になる。Java 8 以降の HashMap は、チェインが長くなると内部を Red-Black Tree に変換して最悪 O(log n) にする工夫をしている。