導入：なぜunordered_mapの「負荷率」を気にする必要があるのか？
C++の標準ライブラリには、キーと値のペアを高速に検索できる「unordered_map」という便利なコンテナがあります。しかし、何も考えずに使い続けると、データ量が増えるにつれて急に検索速度が落ちてしまうことがあります。この原因の多くが「負荷率（load_factor）」にあります。今回は、unordered_mapの裏側で何が起きているのか、そしてパフォーマンスを維持するために知っておくべき負荷率について解説します。
基礎知識：バケットと負荷率の仕組み
unordered_mapは内部で「ハッシュテーブル」という仕組みを使っています。データを格納するための箱（これを「バケット」と呼びます）がいくつか用意されており、ハッシュ関数を使ってどの箱に入れるかを決めています。
ここで重要なのが「負荷率（load_factor）」です。
負荷率 = 現在の要素数 / バケット数
この値が大きくなると、一つのバケットに複数のデータが溜まりすぎてしまい、検索時に「目的のデータを探すために一つずつ確認する」という処理が発生し、unordered_mapの強みである「高速な検索」ができなくなります。
実装：負荷率をチェックして制御する
unordered_mapには、現在の負荷率を確認する関数load_factor()が用意されています。また、この負荷率が一定を超えると、自動的にバケット数を増やして再配置（リハッシュ）が行われます。プログラミングの現場では、あらかじめ要素数が分かっている場合、バケット数を多めに確保しておくことで、この再配置のコストを抑えることが可能です。
サンプルプログラム：負荷率の確認とバケットの確保
以下のコードで、要素を追加した際の負荷率の変化を確認し、バケットを事前に確保する方法を見てみましょう。
include <iostream>
include <unordered_map>
int main() {
std::unordered_map<int, std::string> um;
// 1. 現在の負荷率を表示（最初は0）
std::cout << "初期の負荷率: " << um.load_factor() << std::endl;
// 2. データを追加して負荷率を変化させる
for (int i = 0; i < 10; ++i) {
um[i] = "Data";
}
std::cout << "10個追加後の負荷率: " << um.load_factor() << std::endl;
// 3. 事前にバケット数を確保して負荷率を下げる（リハッシュを防ぐ）
// reserveを使うと、要素数に応じてバケット数を最適化できます
um.reserve(100);
std::cout << "reserve(100)後の負荷率: " << um.load_factor() << std::endl;
return 0;
}
応用・注意点：現場で役立つポイント
1. 最大負荷率（max_load_factor）の調整:
max_load_factor()関数を使うと、自動リハッシュが発生するしきい値を設定できます。メモリを消費してでも検索速度を最優先したい場合は、この値を小さく設定します。
2. 再配置（リハッシュ）のコスト:
要素数が急激に増えるタイミングで、自動的なバケットの拡張が発生すると、その瞬間に処理が重くなります。大量のデータを扱うことがあらかじめ分かっている場合は、必ずreserve()を使って必要なサイズを確保しておくのが「プロの技」です。
3. やりすぎに注意:
バケット数を極端に大きくしすぎると、今度はメモリの無駄遣いになってしまいます。負荷率とメモリ使用量のバランスを考えながら、適切なサイズを指定するようにしましょう。
コメント