この記事のポイント

  • unordered_mapの内部構造と設計特性をレビューアー視点で整理
  • パフォーマンス優位性と設計上の落とし穴を理解
  • ハッシュ関数・衝突管理・API契約への影響を学ぶ

そもそもunordered_mapとは

C++標準ライブラリにおけるunordered_mapは、ハッシュ表（hash table）を内部に採用する連想配列です。
平衡木（map）と異なり、要素の順序を保証せず、高速な検索性能を提供します。

特徴 unordered_map map
内部構造 ハッシュ表 平衡二分木
探索性能 平均 O(1) O(log N)
最悪性能 O(N)（衝突多発時） O(log N)
要素順序 無保証 ソート順保証
ハッシュ依存 必須 不要

なぜこれをレビューするのか

レビューアー視点

unordered_mapは安易に「速そうだから使った」で選定されやすいです。
だが、ハッシュ表の設計には以下のような注意点が伴います。

  • ハッシュ関数設計の責任所在確認
    → 標準hashで良いのか、独自hashが必要か

  • キー型の適格性確認
    → クラス型キーに対し比較演算子ではなくhashとequal_toの実装確認

  • 順序非保証の契約明記
    → API利用側が順序依存していないか確認

  • 衝突発生時の性能劣化予測
    → 事前に衝突率を推計しているか

  • 負荷分散設計（バケット拡張設計）の理解有無
    → パフォーマンスが急激に悪化しうる箇所を把握しているか

開発者視点

  • mapより速いらしいから使う
  • 順序保証が無いことを意識せず使う
  • クラス型キーでビルドエラー後に適当なoperator==実装
  • ハッシュ品質を考慮しない
  • バケットサイズ・リハッシュの動作を理解しない

レビューではこれらの「感覚選定」を未然に防止します。

良い実装例

ユースケース：大量requestIdの高速探索（順序不要）

良い実装例：unordered_mapの特性を活かす 
#include <unordered_map>
#include <string>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_.insert({ log.requestId, log });
    }

    const ApiRequestLog* find(const std::string& requestId) const {
        auto iter = logs_.find(requestId);
        if (iter != logs_.end()) {
            return &(iter->second);
        }
        return nullptr;
    }

private:
    std::unordered_map<std::string, ApiRequestLog> logs_;
};
  • requestIdはランダム文字列で分布が期待できる
  • 順序要件無し
  • 期待される件数が数百万規模でもO(1)探索性能
  • ハッシュ衝突率が極端に偏るケースが少ない

レビュー観点

  • キーの分布特性（ランダム性）を見積もっているか
  • 順序非保証がAPI契約上許容されるか
  • operator[]による不要な上書きが発生していないか
  • ハッシュ衝突が増えた場合の退避設計（バケット拡張など）を考慮しているか
  • クラス型キーならhash, equal_to定義が適切か

良くない実装例: ケース1

以下は順序依存があるのにunordered_mapを使った例です。

順序依存誤用例 
#include <unordered_map>
#include <string>
#include <vector>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_.insert({ log.requestId, log });
        order_.push_back(log.requestId);
    }

    void dumpLogs() const {
        for (const auto& id : order_) {
            auto iter = logs_.find(id);
            if (iter != logs_.end()) {
                // ログ出力処理
            }
        }
    }

private:
    std::unordered_map<std::string, ApiRequestLog> logs_;
    std::vector<std::string> order_;
};

@Reviewer
順序保持が必要ならmapまたは別の順序保証構造を検討してください。unordered_map単体は順序保証しません。

問題点

  • 順序保証をvector側で実質実装してしまっている
  • mapのソート順利用でもよかった可能性が高い
  • データ冗長保持による二重管理

改善例

修正例：順序保証ならmap利用 
#include <map>

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_.insert({ log.requestId, log });
    }

    void dumpLogs() const {
        for (const auto& [id, log] : logs_) {
            // ログ出力処理
        }
    }

private:
    std::map<std::string, ApiRequestLog> logs_;
};
  • mapなら挿入順でなくキー順に安定出力可能
  • 二重管理が不要になる

良くない実装例: ケース2

次はクラス型キーに対してhash関数未定義でビルドエラー後、苦し紛れにoperator<だけ実装した例です。

クラス型キー誤用例 
#include <unordered_map>
#include <string>
#include <cstdint>

struct CompositeKey {
    std::string clientIp;
    int responseCode;

    bool operator<(const CompositeKey& other) const {
        return std::tie(clientIp, responseCode) < std::tie(other.clientIp, other.responseCode);
    }
};

struct ApiRequestLog {
    CompositeKey key;
    std::string requestId;
    std::string endpoint;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_[log.key] = log;
    }

private:
    std::unordered_map<CompositeKey, ApiRequestLog> logs_;
};

@Reviewer
unordered_mapではoperator<は使用されません。hash関数とequal_toの定義が必要です。

問題点

  • unordered_mapはoperator<を参照しない
  • ビルド通らない（コンパイルエラー）
  • ハッシュ関数責任が不明確

改善例

修正例：hash関数定義 
#include <functional>

struct CompositeKey {
    std::string clientIp;
    int responseCode;

    bool operator==(const CompositeKey& other) const {
        return clientIp == other.clientIp && responseCode == other.responseCode;
    }
};

namespace std {
template<>
struct hash<CompositeKey> {
    size_t operator()(const CompositeKey& key) const {
        return hash<std::string>()(key.clientIp) ^ (hash<int>()(key.responseCode) << 1);
    }
};
}
  • unordered_mapではhashとoperator==が最低条件
  • operator<は全く参照されない
  • ビルドエラーはレビューでも即発見可能

PlantUML: unordered_mapの内部責務整理

UML Diagram

観点チェックリスト

まとめ

unordered_mapは極めて強力ですが正しく設計されて初めて真価を発揮するデータ構造です。
レビューアーは「順序保証の有無」「ハッシュ関数の品質」「重複検知責務」「衝突率とその予測」まで読み解く役割を持ちます。
適切にレビューできれば、安易なunordered_map万能信仰を未然に防ぎ、堅牢な設計を支援できます。