ハッシュマップ

実装: data-structures/hashmap/ / 実行: go test ./data-structures/hashmap/

Go の map も Python の dict も、正体は同じになる。キーをハッシュ関数でバケット番号に変え、その1つだけ見る。数えてみると、件数を1万倍にしても1回引くのにたどる数は 1.2 前後で動かない。ただしそれはハッシュが散らばっているからで、散らばらなければ同じ実装のまま線形探索に落ちる。

この章で作るもの

map[string]int のような連想配列を自分で実装する。B-Tree が「順序を保つ木」で log n だったのに対し、ハッシュマップは順序を捨てる代わりに平均 O(1) を得る。

順に見ていく。

1バケットだけ見る: どこを見ればいいかを計算で出せるので、件数が増えても探す範囲が広がらない
たどる数が件数で動かない: 1万倍に増やしても 1.2 前後。負荷率を守るために配り直すから
ハッシュが散らばらなければ全部台無し: 同じ実装のまま、2000件で平均 1000.5 個たどることになる

① 1バケットだけ見る

配列の「何番目に置くか」をキーから直接計算できれば、1回のアクセスで済む。そのための道具がハッシュ関数だ。キー(文字列でも整数でも)を数値に潰す関数である。その数値をバケット数で割った余りが、置き場所(バケット番号)になる。

"apple"  ──hash──▶ 8281...  ── % 8 ──▶ バケット 1
"banana" ──hash──▶ 4472...  ── % 8 ──▶ バケット 0
"cherry" ──hash──▶ 9915...  ── % 8 ──▶ バケット 3

キー → ハッシュ値 → バケット番号。同じキーは必ず同じバケットに落ちるので、探すときも1バケットだけ見れば済む

// bucketIndex はキーが落ちるバケット番号を返す。
// ハッシュ値をバケット数で割った余り。バケット数が2の冪ならビットマスクでも同じ。
func (m *Map[K, V]) bucketIndex(key K) int {
	return int(m.hash(key) % uint64(len(m.slots)))
}

// Put は key=value を入れる(既存キーなら更新)。
func (m *Map[K, V]) Put(key K, value V) {
	i := m.bucketIndex(key)
	for j := range m.slots[i] {
		if m.slots[i][j].key == key {
			m.slots[i][j].val = value // 更新
			return
		}
	}
	m.slots[i] = append(m.slots[i], entry[K, V]{key, value})
	m.count++

	if float64(m.count)/float64(len(m.slots)) > maxLoadFactor {
		m.resize()
	}
}

// Get は key の値を返す。落ちるバケットを1つ求め、その中のリストだけを線形探索する。
// 負荷率が低ければリストは平均1個ほどなので、これが平均 O(1) の正体。
func (m *Map[K, V]) Get(key K) (V, bool) {
	i := m.bucketIndex(key)
	for _, e := range m.slots[i] {
		m.probes++
		if e.key == key {
			return e.val, true
		}
	}
	var zero V
	return zero, false
}

// Delete は key を消す。消したら true。
func (m *Map[K, V]) Delete(key K) bool {
	i := m.bucketIndex(key)
	for j := range m.slots[i] {
		if m.slots[i][j].key == key {
			// バケット内リストから j 番を取り除く(順序は問わないので末尾で埋める)。
			last := len(m.slots[i]) - 1
			m.slots[i][j] = m.slots[i][last]
			m.slots[i] = m.slots[i][:last]
			m.count--
			return true
		}
	}
	return false
}

② たどる数が件数で動かない

ハッシュ値は無限、バケットは有限。だから別のキーが同じバケットに落ちることは必ず起きる(鳩の巣原理)。この章のチェイン法は、各バケットを「リスト」にして、落ちてきた要素を並べる。Get はそのリストだけを線形に探す。

バケット0: [ banana ]
バケット1: [ apple ] → [ grape ]   ← 衝突。リストで吸収
バケット2: [ ]
バケット3: [ cherry ]

チェイン法。バケット1に apple と grape が衝突しても、リストに並べて両方持てる。Get はこのリストだけ見る

負荷率(件数 ÷ バケット数)が低ければ、各リストは平均1個ほどになる。だから「1バケット求めて、短いリストを見る」で済む。

これは言葉で終わらせずに数えられる。Get のたびに、鍵を見比べた回数を足していけばよい:


// Probes は Get で鍵を見比べた回数の累計を返す。
//
// 引いた回数で割れば、1回あたり何個たどったかになる。
// 負荷率を守れていれば、件数がいくら増えてもここは 1 前後で止まる。
func (m *Map[K, V]) Probes() int { return m.probes }

// Resizes は配り直した回数を返す。倍々に増やすので、件数の対数ぶんしか起きない。
func (m *Map[K, V]) Resizes() int { return m.resizes }

// LoadFactor は「件数 / バケット数」。ここが上限を超えると配り直す。
func (m *Map[K, V]) LoadFactor() float64 {
	return float64(m.count) / float64(len(m.slots))
}

// ResetStats は数え直す。
func (m *Map[K, V]) ResetStats() { m.probes = 0 }

件数を変えて測るとこうなった:

件数	1回引くのにたどる数	配り直した回数	負荷率
100	1.150	5	0.391
1,000	1.243	8	0.488
10,000	1.305	11	0.610
100,000	1.193	15	0.381
1,000,000	1.239	18	0.477

1万倍に増やしても、たどる数は 1.2 前後で動かない。これが「平均 O(1)」の中身になる。テストで、1000件と10万件でたどる数がほとんど変わらないことを固定した。

配り直しは倍々なので、対数回しか起きない

要素を入れ続けると負荷率が上がり、リストが伸びて遅くなる。そこで負荷率が上限(この実装は 0.75)を超えたらバケット数を倍にして、全要素を配り直す(rehash)。

// resize はバケット数を倍にして、全要素を配り直す(rehash)。
// バケット数が変わると bucketIndex の余りも変わるので、全要素の引っ越しが必要。
// 1回の resize は O(n) かかる。この「たまに重い」が、平均 O(1) の裏側にある。
func (m *Map[K, V]) resize() {
	m.resizes++
	old := m.slots
	m.slots = make([][]entry[K, V], len(old)*2)
	for _, bucket := range old {
		for _, e := range bucket {
			i := m.bucketIndex(e.key)
			m.slots[i] = append(m.slots[i], e)
		}
	}
}

バケット数が変わると余りも変わるので、全要素の引っ越しが要る。つまり1回の配り直しは件数に比例する。

だが上の表のとおり、100万件を入れても配り直しは 18回 しか起きていない。倍々に増やすので、件数の対数ぶんしか起きないからだ。普段は一定時間、たまに重い、ならすと一定時間になる。この「たまに重い」があること自体は、遅れが気になる場面では知っておく価値がある。

テストで、10万件を入れても配り直しが20回を超えないこと、そのあいだ負荷率が上限 0.75 を超えないことを固定した。

試す: 追加していくと負荷率が上がり、0.75 を超えた瞬間にバケットが倍増して (枠が光る)、要素が配り直される。最長チェインが伸びすぎず一定に保たれるのが見える。

デモハッシュマップのバケット負荷率 0.00

0件 / 8バケット / 最長チェイン 0

③ ハッシュが散らばらなければ全部台無し

ここまでの速さは、全部「キーがバケットに散らばる」という前提の上に乗っている。前提が崩れたらどうなるかも測れる。

どのキーに対しても同じ値を返すハッシュを渡してみる:

件数	良いハッシュ	全部同じバケツ
100	1.150	50.5
1,000	1.243	500.5
2,000	1.243	1000.5

件数の半分をたどっている。バケットが1つしか使われないので、リストに全件が並び、端から見ていくことになる。これは配列を線形に探すのとまったく同じ形だ。

しかも配り直しはちゃんと起きている(2000件で9回)。バケットを増やしても、全部が同じ番号に落ちるので何の役にも立たない。仕組みは正しく動いていて、それでも遅い。テストで、この差を固定した。

だから、ハッシュマップの性能はハッシュ関数の質に丸ごと依存する。そしてこれは攻撃にもなる。同じバケットに落ちるキーを狙って送り込めば、相手のハッシュマップを線形探索に落とせる(HashDoS)。実物の言語処理系が起動ごとに乱数の種を混ぜているのは、狙い撃ちを防ぐためだ。

設計の観点

場所を計算で出す: どこを見ればいいかが分かれば、探す範囲は件数に依らない
前提を数えて確かめる: 「平均 O(1)」は前提つきの主張なので、前提が崩れた場合も測る
たまに重いを受け入れる: 倍々に広げれば、ならして一定時間になる。ただし遅れの山は残る
崩れたときにどう壊れるかを知る: なだらかに悪くなるのではなく、線形探索まで一気に落ちる
外から壊せる形かを見る: 入力を選べる相手が居るなら、最悪の形は狙って作られる
順序を捨てた対価を意識する: 範囲で取り出す用途には使えない

対照と実例

	衝突の吸収	順序	最悪	特徴
チェイン法	バケット内のリスト	無し	件数に比例	実装が単純。削除も楽
オープンアドレス法	別の空き枠を探す	無し	件数に比例	連続したメモリで速い。削除が面倒
Robin Hood	空き枠を探す + 並べ替え	無し	件数に比例	探索長のばらつきが小さい
B-Tree	(衝突しない)	あり	対数	範囲で取り出せる
スキップリスト	(衝突しない)	あり	対数(期待値)	実装が木より簡単

裏どり:

Go の map: バケットあたり8スロットを持ち、ハッシュ値の上位バイトを先に比べて枝刈りする。起動ごとに乱数の種を混ぜて HashDoS を防いでいる
Python の dict: オープンアドレス法。3.7 からは挿入順を保つが、それはハッシュ表とは別に順序の配列を持っているからで、ハッシュ表自体に順序があるわけではない
HashDoS(2011): 同じバケットへ落ちるキーを大量に送って、Web フレームワークのパラメータ解析を止める攻撃が実証された。多くの言語処理系がこのあと乱数の種を入れた
負荷率の上限: この実装は 0.75。オープンアドレス法だと探索長が 1/(1-負荷率) で効くので、もっと低め(0.5 前後)に取ることが多い
ID Generation: 「等価検索だけならハッシュのほうが速い」の実体がここになる

簡略化したこと

チェイン法のみ: オープンアドレス法(衝突したら別の空き枠を探す)は扱わない
乱数の種なし: ハッシュ関数は固定。HashDoS への手当ては入れていない
縮小しない: 要素が減ってもバケットは減らさない
並行安全でない: ロックの分割も sync.Map のような仕掛けも無い
配り直しは一度に: 実物は少しずつ引っ越して遅れの山をならすことがある
バケットは1要素ずつ: Go の map のように、1バケットに複数スロットを詰める形にはしていない

参考資料

Go maps in action — Go の map の設計
Python dict の実装 — オープンアドレス法の実物
CLRS 11章(ハッシュ表) — チェイン法・オープンアドレス法・普遍ハッシュ
実装: data-structures/hashmap

ハッシュマップ ​

この章で作るもの ​

① 1バケットだけ見る ​

② たどる数が件数で動かない ​

配り直しは倍々なので、対数回しか起きない ​

③ ハッシュが散らばらなければ全部台無し ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​