第8章: マップ - ハッシュテーブルの深層理解
学習目標
この章を終えると、以下ができるようになります：
- マップの内部実装（ハッシュテーブル）を理解できる
- バケット構造とコリジョン処理を説明できる
- マップのイテレーション順序がランダムな理由を理解できる
- マップの落とし穴を回避し、最適なパフォーマンスを実現できる
- sync.Mapの使い方と通常のmapとの違いを理解できる
---
イントロダクション: マップとは何か
🔑 根本的な問い: なぜマップは O(1) で要素にアクセスできるのか？
答えは、ハッシュテーブルという巧妙なデータ構造にあります。
他のデータ構造との比較
┌───────────────┬─────────┬─────────┬──────────┬──────────┐
│ 操作 │ 配列 │ スライス│ マップ │ 理由 │
├───────────────┼─────────┼─────────┼──────────┼──────────┤
│ 検索 │ O(n) │ O(n) │ O(1)* │ ハッシュ │
│ 挿入 │ O(1)** │ O(1)* │ O(1)* │ 直接配置 │
│ 削除 │ O(n) │ O(n) │ O(1)* │ マーク │
│ 順序保証 │ ○ │ ○ │ × │ 仕様 │
└───────────────┴─────────┴─────────┴──────────┴──────────┘
* 平均計算量（最悪: O(n)）
** インデックスがわかっている場合
💡 重要: マップの O(1) は平均的な場合であり、最悪の場合は O(n) になる可能性があります。
---
マップの基本
マップの作成
// 宣言（nilマップ）
var m map[string]int
// m["key"] = 1 // panic: assignment to entry in nil map
// makeで作成
m := make(map[string]int)
m["Alice"] = 25
m["Bob"] = 30
// リテラルで初期化
ages := map[string]int{
"Alice": 25,
"Bob": 30,
"Carol": 28,
}
// 空マップ
m := map[string]int{} // makeと同じ
// 容量を指定（最適化のヒント）
m := make(map[string]int, 100) // 100要素分のヒント
メモリレイアウト: マップはどこに存在するのか
🔑 マップの内部構造:
Goのマップは、ランタイムで管理されるハッシュテーブルです。
マップ変数（スタック）:
┌──────────────────────┐
│ hmap ポインタ │──┐
└──────────────────────┘ │
8バイト │
↓
ヒープ上の hmap 構造体:
┌────────────────────────────────────┐
│ count: 3 （要素数） │
│ B: 1 （バケット数: 2^B） │
│ buckets: *bmap （バケット配列） │
│ oldbuckets: nil │
│ ... その他のフィールド ... │
└────────────────────────────────────┘
│
↓
バケット配列:
┌─────────┬─────────┐
│ bucket0 │ bucket1 │
└─────────┴─────────┘
hmap 構造体の詳細
Goランタイムの実装（簡略版）:
// runtime/map.go
type hmap struct {
count int // マップのサイズ（len(m)の結果）
flags uint8 // 状態フラグ（イテレーション中など）
B uint8 // バケット数の指数（バケット数 = 2^B）
noverflow uint16 // オーバーフローバケット数の概算
hash0 uint32 // ハッシュシード（ランダム化）
buckets unsafe.Pointer // バケット配列（2^B個）
oldbuckets unsafe.Pointer // リハッシュ時の古いバケット
nevacuate uintptr // リハッシュの進行状況
extra *mapextra // オーバーフロー情報
}
💡 重要なフィールド:
B: バケット数は 2^B（2のべき乗）hash0: ランダムなシード（セキュリティ対策）buckets: 実際のデータを格納するバケット配列
---
ハッシュテーブルの仕組み
ハッシュ関数とは
🔑 ハッシュ関数の役割:
- 任意のキー → 固定長の整数（ハッシュ値）
- 同じキー → 常に同じハッシュ値
- 異なるキー → できるだけ異なるハッシュ値
キー ハッシュ関数 ハッシュ値（64ビット）
"Alice" ────→ hash() ────→ 0x7A3B9C...
"Bob" ────→ hash() ────→ 0x2F1E8D...
"Carol" ────→ hash() ────→ 0x9C4A2B...
バケットの選択
ハッシュ値からバケットインデックスを計算：
hash := hash_function(key)
bucketIndex := hash & (2^B - 1) // 下位Bビットを使用
💡 なぜ hash % 2^B ではなく hash & (2^B - 1) なのか？
2^B - 1 は全ビットが1:
B=3 の場合: 2^3 - 1 = 7 = 0b00000111
hash & 0b00000111 は、下位3ビットを取り出す高速な操作
（modulo演算より速い）
例:
hash = 0b10110101
& 0b00000111
= 0b00000101 = 5 ← バケットインデックス
バケット構造の詳細
🔑 bmap（バケット）構造:
// runtime/map.go
type bmap struct {
// tophash[i] は keys[i] のハッシュ値の上位8ビット
tophash [8]uint8
// 以下のフィールドは実際にはコンパイル時に動的に生成される
// keys [8]keytype
// values [8]valuetype
// overflow *bmap // オーバーフローバケットへのポインタ
}
実際のメモリレイアウト：
1つのバケット (bmap):
┌────────────────────────────────────────┐
│ tophash[0..7]: ハッシュ上位8ビット │
├────────────────────────────────────────┤
│ keys[0..7]: キー配列（最大8個） │
├────────────────────────────────────────┤
│ values[0..7]: 値配列（最大8個） │
├────────────────────────────────────────┤
│ overflow: オーバーフローへのポインタ│
└────────────────────────────────────────┘
各バケットは最大8個のキーバリューペアを格納
💡 なぜ8個なのか？
完全な例: マップへの挿入
m := make(map[string]int)
m["Alice"] = 25
内部で起こること：
Step 1: ハッシュ値を計算
hash("Alice") = 0x7A3B9C...
^^^^^^^^ 上位8ビット（tophash）
^^^ 下位ビット（バケット選択）
Step 2: バケットを選択
B = 2 の場合（4個のバケット）
bucketIndex = hash & 0b11 = 2
バケット配列:
┌─────────┬─────────┬─────────┬─────────┐
│ bucket0 │ bucket1 │ bucket2 │ bucket3 │
└─────────┴─────────┴─────────┴─────────┘
↑
ここに配置
Step 3: bucket2 の空きスロットに格納
bucket2:
┌──────────────────────────┐
│ tophash: [0x7A, _, _, ...] │ ← ハッシュ上位8ビット
│ keys: ["Alice", ...] │
│ values: [25, ...] │
└──────────────────────────┘
---
コリジョン（衝突）処理
コリジョンとは
🔑 定義: 異なるキーが同じバケットにマップされること
hash("Alice") = 0x...02
hash("Bob") = 0x...02 ← 同じバケット！
バケット2に両方格納される必要がある
チェイン法（Goの実装）
Goはオープンチェイン法を使用：
同じバケットに複数の要素:
bucket2:
┌─────────────────────────────────┐
│ tophash: [0x7A, 0x2F, _, ...] │
│ keys: ["Alice", "Bob", ...] │
│ values: [25, 30, ...] │
└─────────────────────────────────┘
バケットが満杯の場合:
bucket2:
┌─────────────────────────────────┐
│ tophash: [0x7A, 0x2F, ...（8個）] │
│ keys: ["Alice", "Bob", ...] │
│ values: [25, 30, ...] │
│ overflow: ─────────────────────┐│
└──────────────────────────────┼──┘
↓
オーバーフローバケット:
┌─────────────────────────────────┐
│ tophash: [0x9C, _, ...] │
│ keys: ["Carol", ...] │
│ values: [28, ...] │
│ overflow: nil │
└─────────────────────────────────┘
要素の検索プロセス
value := m["Alice"]
内部動作：
Step 1: ハッシュ値を計算
hash("Alice") = 0x7A3B9C...
tophash = 0x7A
bucketIndex = hash & mask = 2
Step 2: bucket2 を探索
bucket2:
┌─────────────────────────────────┐
│ tophash: [0x7A, 0x2F, 0x9C, ...] │
│ ↑
│ 0x7A と一致！
│
│ keys[0] == "Alice" ? → Yes!
│ return values[0] → 25
└─────────────────────────────────┘
💡 tophash を先にチェックすることで、
高速な整数比較でフィルタリングできる
⚠️ 重要: tophashが一致しても、キーの完全一致を確認する必要がある（ハッシュ衝突の可能性）
---
マップの拡張（リハッシュ）
いつ拡張されるのか
🔑 拡張条件:
// runtime/map.go の条件（簡略版）
if count > 8 * (2^B) {
// 負荷率 > 6.5 → 拡張
grow()
}
💡 負荷率（Load Factor）:
負荷率 = 要素数 / バケット数
例:
要素数 = 20
バケット数 = 4（B=2）
負荷率 = 20 / 4 = 5.0
Goの目標負荷率: ~6.5
拡張プロセス
拡張前: B=2（4バケット）
┌─────────┬─────────┬─────────┬─────────┐
│ bucket0 │ bucket1 │ bucket2 │ bucket3 │
└─────────┴─────────┴─────────┴─────────┘
拡張後: B=3（8バケット）
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ bucket0 │ bucket1 │ bucket2 │ bucket3 │ bucket4 │ bucket5 │ bucket6 │ bucket7 │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
各要素は新しいバケットに再配置される
漸進的リハッシュ
⚠️ 重要: Goは一度に全部リハッシュしない
hmap 構造体:
┌──────────────────────────┐
│ B: 3 │ ← 新しいサイズ
│ buckets: ────┐ │ ← 新しいバケット配列
│ oldbuckets: ─┼─┐ │ ← 古いバケット配列（まだ存在）
└──────────────┼─┼─────────┘
│ │
↓ ↓
新 / 旧 バケット
💡 漸進的リハッシュの利点:
- 大きいマップでも一時停止が短い
- 読み書き操作の遅延が均一
- メモリの急激な増加を防ぐ
リハッシュの動作：
マップ操作のたびに、少しずつ移行:
読み取り操作:
1. oldbuckets から探す
2. buckets から探す
3. 見つかった方を返す
書き込み操作:
1. oldbuckets の対応バケットを移行
2. 新しい buckets に書き込む
数回の操作後:
oldbuckets の全要素が buckets に移行完了
→ oldbuckets を解放
---
マップのイテレーション順序
なぜランダムなのか
🔑 3つの理由:
理由1: ハッシュテーブルの性質
キーの挿入順序とバケットの順序は無関係:
挿入順序:
Alice → Bob → Carol
バケット配置（ハッシュ値に依存）:
bucket0: Carol
bucket1: Alice
bucket2: Bob
理由2: リハッシュ
拡張前:
bucket0: [Alice, Bob]
bucket1: [Carol]
拡張後: キーが再配置される
bucket0: [Alice]
bucket1: [Carol]
bucket2: []
bucket3: [Bob]
理由3: 意図的なランダム化
// Goの実装：イテレーションの開始位置をランダム化
startBucket := rand.Intn(2^B)
💡 なぜわざわざランダム化？
順序に依存したコードを書くのを防ぐため。
// 悪い例: 順序に依存
m := map[string]int{"a": 1, "b": 2, "c": 3}
for k := range m {
if k == "a" {
// "a" が最初に来ると仮定 → 危険！
}
break
}
イテレーションの内部動作
for key, value := range m {
// ...
}
内部処理:
1. ランダムな開始バケットを選択
2. 各バケットを順番に走査
3. 各バケット内の8スロットを走査
4. オーバーフローバケットも走査
5. 全バケット走査後、開始地点に戻る
図解:
┌─────────┬─────────┬─────────┬─────────┐
│ bucket0 │ bucket1 │ bucket2 │ bucket3 │
└─────────┴─────────┴─────────┴─────────┘
↑
ランダム開始（例: bucket1）
走査順序: bucket1 → bucket2 → bucket3 → bucket0
ソート済みイテレーション
順序が必要な場合：
// キーを取り出してソート
keys := make([]string, 0, len(m))
for k := range m {
keys = append(keys, k)
}
sort.Strings(keys)
// ソート順に処理
for _, k := range keys {
fmt.Printf("%s: %d\n", k, m[k])
}
メモリレイアウト：
元のマップ（順序なし）:
m: bucket0[Carol→28], bucket1[Alice→25], bucket2[Bob→30]
keys スライス（ソート済み）:
["Alice", "Bob", "Carol"]
イテレーション:
keys[0] = "Alice" → m["Alice"] = 25
keys[1] = "Bob" → m["Bob"] = 30
keys[2] = "Carol" → m["Carol"] = 28
---
マップの削除
deleteの動作
delete(m, "Alice")
内部処理：
Step 1: バケットを特定
hash("Alice") = 0x7A3B9C...
bucketIndex = 2
Step 2: bucket2 内を探索
bucket2:
┌─────────────────────────────────┐
│ tophash: [0x7A, 0x2F, _, ...] │
│ keys: ["Alice", "Bob", ...] │
│ values: [25, 30, ...] │
└─────────────────────────────────┘
↑
0x7A を発見
Step 3: 削除をマーク
bucket2:
┌─────────────────────────────────┐
│ tophash: [empty, 0x2F, _, ...] │ ← tophash[0] = empty
│ keys: ["", "Bob", ...] │ ← keys[0] をクリア
│ values: [0, 30, ...] │ ← values[0] をゼロ化
└─────────────────────────────────┘
💡 実装の詳細:
- 要素は物理的に削除されない（スロットは空きマーク）
- count（要素数）は減少
- メモリは即座に解放されない（GCが後で回収）
存在しないキーの削除
delete(m, "Nonexistent") // パニックしない（何も起こらない）
🔑 重要: deleteは安全な操作（存在チェック不要）
---
マップの容量
makeの容量指定
m := make(map[string]int, 100) // 容量ヒント
内部で起こること：
// runtime/map.go の疑似コード
func makemap(hint int) *hmap {
// 必要なバケット数を計算
B := 0
for overLoadFactor(hint, B) {
B++
}
// 2^B 個のバケットを割り当て
h := &hmap{
B: uint8(B),
buckets: makeBucketArray(B),
hash0: fastrand(),
}
return h
}
💡 容量指定の効果:
容量なし:
m := make(map[string]int)
→ B=0（1バケット）から開始
→ 要素追加で複数回リハッシュ
容量あり:
m := make(map[string]int, 100)
→ B=4（16バケット）で開始
→ リハッシュ回数が減る
---
マップの型制約
キーに使える型
🔑 比較可能な型のみ:
// OK: 比較可能な型
map[string]int // string
map[int]string // int
map[float64]bool // float64（注意が必要）
map[*int]string // ポインタ
map[struct{x int}]int // 比較可能な構造体
map[interface{}]int // 空インターフェース
⚠️ NG: 比較不可能な型:
// コンパイルエラー
// map[[]int]string // スライス
// map[map[string]int]int // マップ
// map[func()]int // 関数
float64 をキーに使う際の注意
m := map[float64]string{}
m[0.1] = "A"
// 浮動小数点の精度問題
val := 0.3 - 0.2 // 理論上 0.1 だが...
fmt.Println(m[val]) // "" （見つからない可能性）
fmt.Println(0.3 - 0.2 == 0.1) // false!
💡 推奨: float64 キーは避けるか、文字列に変換する
// 解決策: 整数に変換
m := map[int]string{}
key := int(value * 100) // 小数点2桁を整数化
m[key] = "A"
---
マップの落とし穴
落とし穴1: nilマップへの書き込み
⚠️ 問題:
var m map[string]int // nil マップ
m["key"] = 1 // panic!
実行時の動作：
Step 1: m は nil ポインタ
m: nil
Step 2: マップに書き込もうとする
runtime が nil チェック
→ panic: assignment to entry in nil map
🔑 解決策:
// 方法1: make で初期化
m := make(map[string]int)
m["key"] = 1 // OK
// 方法2: リテラルで初期化
m := map[string]int{}
m["key"] = 1 // OK
💡 nil マップの読み取りは安全:
var m map[string]int // nil
value := m["key"] // OK（ゼロ値を返す）
_, ok := m["key"] // OK（ok=false）
len(m) // OK（0を返す）
落とし穴2: マップは参照型
m1 := map[string]int{"a": 1}
m2 := m1 // 参照をコピー
m2["a"] = 99
fmt.Println(m1["a"]) // 99 （m1も変わる！）
メモリレイアウト：
スタック:
┌────────────┐
│ m1: 0x1000 │─┐
└────────────┘ │
┌────────────┐ │
│ m2: 0x1000 │─┤ ← 同じアドレスを指す
└────────────┘ │
↓
ヒープ:
0x1000: hmap{count:1, ...}
└→ buckets → ["a": 99]
🔑 解決策: マップをコピーする
// ディープコピー
m2 := make(map[string]int, len(m1))
for k, v := range m1 {
m2[k] = v
}
m2["a"] = 99
fmt.Println(m1["a"]) // 1 （変わらない）
落とし穴3: イテレーション中の変更
⚠️ 問題:
m := map[string]int{"a": 1, "b": 2, "c": 3}
// 削除は一般的にOK
for k := range m {
if m[k] == 2 {
delete(m, k) // 安全
}
}
// 追加は予測不可能
for k := range m {
m[k+"_new"] = m[k] // 危険！
// 追加した要素がイテレーションに含まれるかは未定義
}
🔑 解決策: キーを先に収集
keys := make([]string, 0, len(m))
for k := range m {
keys = append(keys, k)
}
// 収集したキーを使って追加
for _, k := range keys {
m[k+"_new"] = m[k] // 安全
}
落とし穴4: 並行アクセス
⚠️ 問題: マップは並行安全ではない
m := make(map[string]int)
// 競合状態（race condition）
go func() {
m["key"] = 1 // 書き込み
}()
go func() {
m["key"] = 2 // 書き込み
}()
// → panic または不正な状態
Goのランタイムは競合を検出：
fatal error: concurrent map writes
goroutine 1:
マップに書き込み中
goroutine 2:
同時にマップに書き込み
→ ランタイムが検出してパニック
🔑 解決策1: sync.Mutex
var mu sync.Mutex
var m = make(map[string]int)
// 書き込み
mu.Lock()
m["key"] = 1
mu.Unlock()
// 読み込み
mu.Lock()
value := m["key"]
mu.Unlock()
🔑 解決策2: sync.RWMutex（読み込みが多い場合）
var mu sync.RWMutex
var m = make(map[string]int)
// 書き込み
mu.Lock()
m["key"] = 1
mu.Unlock()
// 読み込み（複数同時OK）
mu.RLock()
value := m["key"]
mu.RUnlock()
---
sync.Map: 並行安全なマップ
sync.Map の特徴
🔑 通常のmap vs sync.Map:
┌────────────────┬──────────────────┬────────────────────┐
│ 特性 │ map + Mutex │ sync.Map │
├────────────────┼──────────────────┼────────────────────┤
│ 型安全 │ ○ │ × (interface{}) │
│ パフォーマンス │ 単純 │ 最適化済み │
│ ユースケース │ 汎用 │ 特定パターン │
│ API │ シンプル │ やや複雑 │
└────────────────┴──────────────────┴────────────────────┘
sync.Map の内部構造
sync.Map:
┌────────────────────────────────────┐
│ read: atomic.Value │ ← 読み取り専用マップ（高速）
│ └→ readOnly{m: map[...]} │
│ │
│ dirty: map[interface{}]*entry │ ← 書き込み用マップ
│ mu: sync.Mutex │ ← dirtyの保護用
│ misses: int │ ← キャッシュミスカウント
└────────────────────────────────────┘
読み取り: read から（ロックなし）
書き込み: dirty へ（ロックあり）
sync.Map の使い方
var m sync.Map
// 書き込み
m.Store("Alice", 25)
m.Store("Bob", 30)
// 読み込み
if value, ok := m.Load("Alice"); ok {
age := value.(int) // 型アサーション必須
fmt.Println("Alice:", age)
}
// 削除
m.Delete("Bob")
// 存在すれば読み込み、なければ書き込み
actual, loaded := m.LoadOrStore("Carol", 28)
if loaded {
fmt.Println("Carol already exists:", actual)
} else {
fmt.Println("Carol added with age 28")
}
// 存在すれば削除して値を返す
if value, loaded := m.LoadAndDelete("Alice"); loaded {
fmt.Println("Deleted:", value)
}
// イテレーション
m.Range(func(key, value interface{}) bool {
fmt.Printf("%s: %v\n", key, value)
return true // false を返すと中断
})
sync.Map の最適なユースケース
✅ sync.Map が適している:
- 読み取りが多い (read-heavy)
- 書き込みが少ない
- キーのセットが安定 (頻繁に追加削除しない)
❌ sync.Map が不適:
- 書き込みが多い (write-heavy)
- 型安全が重要
- 複雑な操作 (トランザクションなど)
// 適している例: 設定キャッシュ
type ConfigCache struct {
cache sync.Map
}
func (c *ConfigCache) Get(key string) (string, bool) {
value, ok := c.cache.Load(key)
if !ok {
return "", false
}
return value.(string), true
}
func (c *ConfigCache) Set(key, value string) {
c.cache.Store(key, value)
}
// 不適な例: 頻繁な更新
// 通常の map + Mutex の方が良い
---
マップの実用パターン
パターン1: セット（集合）の実装
// map[T]bool でセット
type StringSet map[string]bool
func (s StringSet) Add(value string) {
s[value] = true
}
func (s StringSet) Remove(value string) {
delete(s, value)
}
func (s StringSet) Contains(value string) bool {
return s[value] // 存在しなければ false
}
func (s StringSet) Size() int {
return len(s)
}
// 使用例
set := make(StringSet)
set.Add("apple")
set.Add("banana")
set.Add("apple") // 重複は無視
fmt.Println(set.Contains("apple")) // true
fmt.Println(set.Size()) // 2
💡 省メモリ版: struct{} を使う
// map[T]struct{} はメモリ効率が良い
type StringSet map[string]struct{}
func (s StringSet) Add(value string) {
s[value] = struct{}{} // 空の構造体（0バイト）
}
func (s StringSet) Contains(value string) bool {
_, exists := s[value]
return exists
}
メモリ比較：
┌──────────────────┬──────────────┬──────────────┐
│ 型 │ キー8B │ 値 │
├──────────────────┼──────────────┼──────────────┤
│ map[string]bool │ 8バイト │ 1バイト │
│ map[string]struct{}│ 8バイト │ 0バイト │
└──────────────────┴──────────────┴──────────────┘
1000要素のセット:
map[string]bool: ~9000バイト
map[string]struct{}: ~8000バイト
節約: ~11%
パターン2: 頻度カウント
func countWords(text string) map[string]int {
counts := make(map[string]int)
words := strings.Fields(text)
for _, word := range words {
counts[word]++ // 存在しなければ0、存在すれば増加
}
return counts
}
text := "apple banana apple cherry banana apple"
counts := countWords(text)
// map[apple:3 banana:2 cherry:1]
パターン3: グルーピング
type Person struct {
Name string
City string
}
func groupByCity(people []Person) map[string][]Person {
groups := make(map[string][]Person)
for _, p := range people {
groups[p.City] = append(groups[p.City], p)
}
return groups
}
people := []Person{
{"Alice", "Tokyo"},
{"Bob", "Osaka"},
{"Carol", "Tokyo"},
}
groups := groupByCity(people)
// map[Tokyo:[{Alice Tokyo} {Carol Tokyo}] Osaka:[{Bob Osaka}]]
パターン4: メモ化（キャッシュ）
type Cache struct {
mu sync.RWMutex
store map[string]Result
}
type Result struct {
Value interface{}
Time time.Time
}
func (c *Cache) Get(key string) (interface{}, bool) {
c.mu.RLock()
defer c.mu.RUnlock()
result, ok := c.store[key]
if !ok {
return nil, false
}
// TTL チェック
if time.Since(result.Time) > 5*time.Minute {
return nil, false
}
return result.Value, true
}
func (c *Cache) Set(key string, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
c.store[key] = Result{
Value: value,
Time: time.Now(),
}
}
---
マップのパフォーマンス最適化
最適化1: 容量の事前確保
// 悪い例
m := make(map[string]int)
for i := 0; i < 1000000; i++ {
m[fmt.Sprintf("key%d", i)] = i
}
// 良い例
m := make(map[string]int, 1000000)
for i := 0; i < 1000000; i++ {
m[fmt.Sprintf("key%d", i)] = i
}
パフォーマンス差：
リハッシュ回数:
悪い例: log₂(1000000) ≈ 20回
良い例: 0-1回
実行時間:
悪い例: ~500ms
良い例: ~300ms ← 40%高速化
最適化2: マップ vs スライス
小さいデータセット（<100要素）では、スライスの方が速い場合がある：
// マップ: O(1) だが定数コストが高い
m := map[string]int{
"Alice": 25,
"Bob": 30,
}
age := m["Alice"]
// スライス: O(n) だが小さいnでは速い
type KeyValue struct {
Key string
Value int
}
slice := []KeyValue{
{"Alice", 25},
{"Bob", 30},
}
for _, kv := range slice {
if kv.Key == "Alice" {
age := kv.Value
break
}
}
ベンチマーク結果（概算）：
┌───────────┬─────────┬─────────┬─────────┐
│ 要素数 │ マップ │ スライス│ 推奨 │
├───────────┼─────────┼─────────┼─────────┤
│ 10 │ 20ns │ 10ns │ slice │
│ 100 │ 25ns │ 50ns │ map │
│ 1000 │ 30ns │ 500ns │ map │
└───────────┴─────────┴─────────┴─────────┘
最適化3: キーの型
// 遅い: string キー（動的メモリ、ハッシュコスト高）
m1 := map[string]int{
"key1": 1,
"key2": 2,
}
// 速い: int キー（固定サイズ、ハッシュコスト低）
m2 := map[int]int{
1: 1,
2: 2,
}
// 中間: 小さい構造体キー
type Key struct {
A, B int
}
m3 := map[Key]int{
{1, 2}: 1,
}
---
まとめ
この章では、Goのマップについて深く学びました。
重要ポイント
🔑 内部構造:
- ハッシュテーブル（バケット配列）
- 各バケットは最大8要素
- オーバーフローチェーン
- 漸進的リハッシュ
🔑 特性:
- 平均 O(1) の操作
- イテレーション順序はランダム
- 負荷率 ~6.5 で拡張
- 並行安全ではない
🔑 落とし穴:
- nil マップへの書き込み
- 参照型（共有される）
- イテレーション中の変更
- 並行アクセス
ベストプラクティス
✅ 推奨:
- makeで容量を事前確保
- キーの存在チェックは2番目の戻り値
- 並行アクセスには Mutex または sync.Map
- struct{} を使って省メモリなセット
- 順序が必要ならキーをソート
❌ 非推奨:
- nil マップへの書き込み
- イテレーション順序への依存
- 並行アクセスの保護なし
- float64 キー（精度問題）
---
次の章では、構造体について学びます。構造体はGoにおける最も重要なデータ型の一つです。