#️⃣

unordered_map が最悪ケースで O(1) でない理由

に公開
C++
vector
計算量
std
オーダー
tech

この記事ではstd::unordered_mapの検索・挿入の最悪時間計算量が O(N)になってしまう理由を説明する．

setではなくmapを扱う理由

std::setはstd::mapの特殊な場合，std::unordered_setはstd::unordered_mapの特殊な場合と考えることができる．
よって，それぞれ後者について述べれば，前者についても含めた議論となる．
そのため，この記事ではsetではなくmapを扱う．

削除を扱わない理由

この記事では，挿入と削除がほとんど同じ手続きのデータ構造を扱う．
また結果として，それらのデータ構造の挿入と削除の時間計算量は等しい．
そのため，この記事では削除については省略する．

検索・挿入の時間計算量

この記事では複数の要素を格納する代表的なデータ構造としてstd::vector，std::map，std::unordered_mapを扱う．
以下にそれらの検索・挿入の時間計算量を示す．（Nは要素数）

検索 挿入
std::vector std::find
平均・最悪 O(N) 		std::vector::insert
平均・最悪 O(N)
std::map std::map::find
平均・最悪 O(log_2 N) 		std::map::insert[1]
平均・最悪 O(log_2 N)
std::unordered_map std::unordered_map::find
平均 O(1)
最悪 O(N) 		std::unordered_map::insert[2]
平均 O(1)
最悪 O(N)

このように，std::unordered_mapは最悪ケースでは，std::mapの平均ケースより挿入・検索の計算オーダーが大きくなってしまう．

各データ構造の実装と計算オーダー

ここで説明する実装は一般的な実装の一例であり，stdの内部実装とは異なる可能性がある．

std::vector

std::vectorは連結リストで実装されていると考えられる．
検索は線形探索のため O(N)．
挿入は要素を挿入するアドレスの検索が O(N)，アドレスの更新（連結リストの要素のつなぎ変え）が O(1)であるため全体で O(N)．

std::map

std::mapは平衡二分木で実装されていると考えられる．
検索は二分探索で O(log_2 N)（平衡二分木の高さ）．
挿入は挿入場所の検索が O(log_2 N)，アドレスの更新（平衡二分木の要素のつなぎ変え）が O(1)，平衡二分木の再平衡化（いわゆる回転）が O(1)であるため全体で O(log_2 N)．

余談

std:mapは上記の通り平衡二分木で実装されており，これは二分探索木の一種である．
そのためstd::mapの内部の要素は常にソートされいるという特徴がある．

つまり，平衡二分木の要素（std::mapのkey）となるには要素がソート可能である必要がある．
「要素がソート可能」を言い換えると「要素に全順序が定義されている」となる．

したがって，任意のクラスをstd:mapのkeyにするためには，任意の要素同士の大小比較ができる比較関数を定義すればよい．
（例：ベクトルの第２成分で大小比較する比較関数）

std::unordered_map

std::unordered_mapは連想配列クラスでデータを保持し，チェイン法で実装されていると考えられる．
チェイン法とはざっくり表すと以下の図ようなデータ構造である．

チェイン法のイメージ

以下にデータ（keyとvalueのペア）を挿入するときの手順を示す．

  1. hash関数でkeyからハッシュ値を計算
  2. ハッシュ値を，格納する場所（図上部の０～５，以後「バケット」と呼ぶ）として受け取る
  3. ハッシュ値に対応するバケットを見て，それに接続されている要素のkeyをすべて確認
    • 現在追加しようとしている要素のkeyが重複していないか確認する目的
  4. 新しい要素を対応バケットの連結成分の末尾に接続

上記の挿入操作のうち，手順1~3が検索操作に該当する．

hash関数の計算は O(1)である．
対応バケットに接続しているすべての要素の確認は平均ケースで O(1)，最悪ケースで O(N)である．
また，要素の接続は O(1)である．

したがって，検索・挿入は平均ケースで O(1)，最悪ケースで O(N)．

最悪ケースとして全要素がひとつのバケットに連結している場合も考えれらるため，最悪時間計算量はO(N)．
挿入は重複判定をするために対応バケットの要素をすべて確認する必要があるため，平均時間計算量はO(N)，最悪時間計算量はO(N)．

ちなみに，二分木で実装されているstd::mapではkeyとなるためにkey同士の大小比較ができることを要求するのに対し，std::unordered_mapは等価比較できることを要求する．
これは上記の通り，std::unordered_mapの内部でkeyの順番を保持せず，検索や挿入時の重複判定にkey同士が一致するか確認するためである．
具体的にはkeyにしたいクラスに対して，等価演算子==が適切に設定されていればよい．

また，std::unordered_mapのkeyになるためには他にも，hash関数が定義されている必要がある．
これは対応バケットを算出するためである．
このhash関数が"適切に"設定されているか否かで検索や挿入の計算効率が変化する．
不適切なhash関数であると，一部のバケットに要素が集中し負荷が高くなる．
その結果，上記の最悪ケースのようにバケットを算出した後の要素のチェックに時間がかかってしまう．

上記の問題を解決するために，C++ではstd::unordered_map::rehashやstd::unordered_map::reserveなどの関数が用意されている．
（いつか書きたい）

以下の記事では，良いハッシュ関数を作る方法などが紹介されている．
https://codeforces.com/blog/entry/62393

まとめ

軽くプログラムを書きたいくらいであれば，std::mapとstd::unordered_mapのどちらを使用するかはそこまで気にする必要はない．
ただ，計算量等を気にする必要がある場合は上記のようなことに留意すべきである．

おつかれさまでした

脚注

  1. map::insert - cpprefjp C++日本語リファレンス の(1)～(6)のケース ↩︎

  2. unordered_map::insert - cpprefjp C++日本語リファレンス の(1)～(6)のケース ↩︎

Discussion