ふと、std::hash<std::size_t>の実装がどうなっているか気になった。
ハッシュ関数は、何かの型の値を整数型に変換する。特にstd::hashはsize_tに変換する関数である。同じ値に対しては同じハッシュ値を返し、別の値同士が同じハッシュ値を取らないようにする。一般にはハッシュ値を計算すべき型の取りうる値よりもハッシュ値の型がとる状態の方が少ないことが多いので、異なる値のハッシュ値が同一になり得る。これを衝突と呼ぶ。
ハッシュ関数は長い文字列などを単一の数値型に落とし込むことができるので、重複の検出に用いることができる。同一の文字列は必ず同じハッシュ値を保つので、ハッシュ値を使ってアクセスした配列の要素に文字列を挿入していくと、重複した文字列は必ず同じ配列要素に含まれる。これによって「同じである可能性のある文字列」の集合をかなり減らすことができ、力ずくの探索に比べて効率よく重複した文字列を検出できる。しかしハッシュ関数が頻繁に衝突するようだと、「同じである可能性のある文字列」の集合はあまり小さくならず、効率もあまりよくならない。また、ハッシュ関数の計算に文字列そのものの比較の100万倍の時間がかかるようだと、これも文字列そのものを比較する方が高速だ。なので、ハッシュ関数は十分高速に動作し、かつハッシュ値を十分散らす必要がある。
同様の使い道として、値に対応するキーのハッシュ値を配列のインデックスとして使う「ハッシュテーブル」がある。これは任意の型をキーとして値を繋いでおける連想配列だが、二分探索木と異なり定数時間でアクセスが可能である。ハッシュ関数の計算量は連想配列のサイズに無関係で定数だし、インデックスが求まれば配列よろしく定数時間でアクセスできるからだ。ここでも衝突が問題となる。二つのキーが指す要素インデックスが衝突してしまうとキーと値の対応が保てなくなるので、何らかの方法でどちらかのキーを別の位置へ割り当てる手法が必要になる。もちろんこのような必要はない方が良い。この用途に使うためにもハッシュ関数は十分高速で、かつハッシュ値を十分散らさなければならない。
表題に戻ろう。異なる2つのsize_tの値が異なる2つのsize_tの値になるように変換するもっとも簡単で高速だろう方法は、恒等変換だ。ほかの組み込みの整数は大抵の場合size_tよりもサイズが小さい。なのでintegral_typeは全て、単純なsize_tへのキャストがハッシュ関数に求められる2つの条件を満たすだろう。これらのハッシュ関数はどう実装されているのだろうか。謎のビット演算によってsize_tの値がなす集合の各地へ散らされているのだろうか。それとも単にそのまま返されているのだろうか。
というわけで見てみることにした。ポピュラーだろうからGCC実装にしよう。bits/functional_hash.hppの中に定義がある。
gcc/functional_hash.h at master · gcc-mirror/gcc · GitHub
見ていくとポインタへの部分特殊化があった。引用してみる。
template<typename _Tp>
struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
{
size_t
operator()(_Tp* __p) const noexcept
{ return reinterpret_cast<size_t>(__p); }
};
reinterpret_castしている。性質上、size_tのサイズとポインタ型のサイズは同じであることが期待される。なので値は変えずそのまま返している。他の整数型はどうだろう。そのすぐ下に、マクロ定義がある。これは「trivialなハッシュ」のための特殊化を作るマクロで、static_cast<size_t>だけして返すようなハッシュ関数を定義している。そして整数型のそれぞれに対するマクロ展開が延々と続く。使い終わったらちゃんとundefしてあるので安心だ。
#define _Cxx_hashtable_define_trivial_hash(_Tp) \
template<> \
struct hash<_Tp> : public __hash_base<size_t, _Tp> \
{ \
size_t \
operator()(_Tp __val) const noexcept \
{ return static_cast<size_t>(__val); } \
};
という訳で、恒等変換が先に述べたハッシュ関数に期待される条件を両方満たす時は「trivialな」ハッシュ関数となり、GCC実装の標準ライブラリでもそのように実装されていることがわかった。もしかしたら自作ハッシュ定義で少しだけ速度を挙げられるかも、と一瞬期待したので悔しい。
しかし考えて見てほしい、ハッシュ関数がほぼ自明になるケースが整数型以外にもある。8文字以下の(1byte)文字列やstd::pair<bool, int>のような、全部合わせて64bit以下の整数型N個の組だ。これらは単に連結してstd::size_tに変換すれば良い。少し面倒だが以下のようなことになるだろうか。
template<>
struct hash<std::pair<bool, std::int32_t>>
{
std::size_t
operator()(std::pair<bool, std::int32_t> p) const noexcept
{
return (static_cast<std::size_t>(p.first) << 32ul) |
(static_cast<std::size_t>(p.second) & 0x00000000ffffffff));
}
};
あるいはsizeof(T) == 8ならそのままreinterpret_castでも良い。何となく、アセンブラの方が「あのレジスタの下32bit部分にこれを書き込む」と言うような命令で高速化できそうな気もする。
今までstd::pairのハッシュ値を計算するときはboost::hash_combine的なものを使っていたが、ビットシフトで散らしてから繋げるよりも単にこうやって繋げた方が早い可能性はある。となると今まで少し時間をロスしていたのだろうか。今まで「std::pair<T1, T2>とかstd::tuple<Ts...>に対する特殊化として標準でhash_combineで繋げたバージョンを用意してくれればいいのに」と思っていたが、そうなるとreinterpret_castによる高速化の機会を逸するのが提供されない理由だったのだろうか。
ところで、上のような「trivialな」ハッシュ関数が使えない場合が存在する。そのような場合の一つに、改竄の検出がある。大きなファイル全体のdiffを取るのではなく、ハッシュ値が一致しているかを確認するのだ。例として、広く使われているプログラムの配布元と使用者の間に割って入って、悪意のあるコードを実行するよう改変したプログラムにすり替える攻撃を考える。もし配布元がプログラムのハッシュ値を公開していれば、この攻撃は極端に難しくなる。衝突しないよう注意深く設計されたハッシュ関数の返す値を衝突させ、かつ悪意のあるコードを実行するように改変を加えるのは容易ではないからだ。このような用途に使うハッシュ関数が返すべき値は、衝突しにくいことはもちろん、予測不能であることが望ましい。当然このような用途に「trivialな」ハッシュ関数を使うのは愚の骨頂だろう。上記のような高速化は、重複検出、検索、ハッシュテーブルについて行われるべきものだ。
