unordered 系コンテナの max_load_factor 周りについて - melpon日記 - HaskellもC++もまともに扱えないへたれのページ

この記事は LL/ML Advent Calendar １９日目の記事です。

C++11 で追加された unordered 系のコンテナは、ハッシュを使って要素を管理するコンテナです。
そのハッシュを使ったアルゴリズムもいくつかありますが、C++11 では OpenHashing 方式を想定しているようです。
OpenHashing 方式は、同じバケットに対して複数の要素が入ってしまう場合、リンクリストなどでそれらの要素を繋いでやる方式です。
細かいことやその他の方式については SlideBoom closed down を見ましょう。

この記事では C++11 の unordered 系コンテナ特有の、バケットやリハッシュ関数について説明します。

バケット操作関数

バケットの数は bucket_count() で取得できます。また、n 番目のバケットに入っている要素数は bucket_size(n) で取得できます。
つまり、以下のようなイメージです。

バケット数は構築時に指定できます。構築時に x を指定した場合、x <= bucket_count() であることが保証されます。

n 番目のバケットに入っている要素は、begin(n), end(n) を使うことで列挙できます。
つまり、以下のようなイメージです。

begin(n), end(n) が返すイテレータは local_iterator （const の場合は const_local_iterator）で、iterator や const_iterator と同じカテゴリ（つまり ForwardIterator）になります。

ある要素 k が何番目のバケットに入るのかを確認するためには bucket(k) 関数を使います。
つまり、ある要素 k がコンテナに含まれているかどうかを確認する場合、以下の様に書くことが可能です。

#include <unordered_set>
#include <iostream>
#include <iomanip>

bool contain(const std::unordered_set<int>& u, int k) {
  std::size_t bucket = u.bucket(k);
  for (auto it = u.begin(bucket); it != u.end(bucket); ++it) {
    if (*it == k) return true;
  }
  return false;
}

int main() {
  std::unordered_set<int> u = { 314, 159, 265, 359 };
  std::cout << std::boolalpha << "contain(159): " << contain(u, 159) << std::endl;
  std::cout << std::boolalpha << "contain(100): " << contain(u, 100) << std::endl;
}

contain(159): true
contain(100): false

もちろん普段はこんなのを書かず、find() や count() 関数を使ったほうがいいでしょう。

占有率の確認

１つのバケットあたりに、平均でいくつの要素が入っているかという値を、占有率（load factor）と呼びます。
占有率が高くなると、バケットから要素を辿る量が平均的に多くなるので、速度が遅くなってきます。
そこで、多くの OpenAddressing 方式では、占有率がある一定量を超えると、より大きなバケットを作り、既存の要素をそのバケットに対して入れ直します。これをリハッシュと呼びます。

C++11 の unordered 系もこの戦略を採用しています。
占有率を返す関数が load_factor() 関数です。内部的には単に static_cast(size()) / static_cast(bucket_count()) しているだけです。
占有率がどれぐらいまで増えるとリハッシュを行うかというしきい値（最大占有率）が max_load_factor() 関数です。構築直後は 1.0f になっています。
max_load_factor(0.5) などのように、最大占有率を設定することもできます。この際、リハッシュが行われることがあります。
リハッシュが行われると、そのコンテナに対する既存のイテレータは全て無効になるので注意しましょう。

ある要素を insert() などで追加した場合にリハッシュが発生するかどうかを知りたい場合、以下の様なコードで判断できます。

// u に n 個の要素を insert したときにリハッシュが発生するかどうか
template<class UnorderedContainer>
bool will_be_rehash(const UnorderedContainer& u, std::size_t n) {
  return u.size() + n >= u.max_load_factor() * u.bucket_count();
}

挿入した場合の要素数が u.size() + n で、(u.size() + n) / u.bucket_count() が新しい占有率になります。これが最大占有率以上になるかどうかなので、(u.size() + n) / u.bucket_count() >= u.max_load_factor() となり、除算は怖いので乗算に直すと上記の式になります。

リハッシュ関数

rehash(n) 関数は、n 個以上のバケット数でリハッシュを行います。
つまり実行後は必ず n <= bucket_count() となるようにリハッシュを行います。最初から n <= bucket_count() になっているなら、リハッシュを行わない可能性もあります。

reserve(m) 関数は、少なくとも m 個の要素まではリハッシュを行わないようにします。
つまり最低でも m / max_load_factor() 個より多いバケットを用意します*1。

ここでの reserve() 関数は、指定した要素数以上は格納できるようにするという点で vector::reserve() とよく似ています。
しかし、vector::reserve(m) は、m が capacity() より小さい場合には何もしないと規定されている（つまりコンテナサイズは小さくならない）のに対し、unordered 系の reserve() 関数にはそのような規定はありません。つまり、reserve() によって bucket_count() が小さくなる可能性もあるということです（もちろん load_factor() が max_load_factor() を超えることはありませんが）。
これは reserve() だけでなく、rehash() や max_load_factor() などでも同じです。
ただし、必ず小さくなる訳ではないので、確実にバケット数を減らしたいなら Shrink to Fit イディオムを使いましょう。

まとめ

unordered 系のコンテナ特有のバケット関数やリハッシュ関数を見てきました。
C++ で、しかも Associative Container ではなく Unordered Associative Container が必要であるという状況は、かなり速度が必要である場面である可能性が高いでしょう。
そのため、このような関数は重要です。
このあたりの関数をうまく使って、unordered 系のコンテナを効率的に扱いましょう。

*1:仕様上では a.rehash(ceil(n / a.max_load_factor())) と同じ、となっています