はじめに
数値ベクトルからハッシュ値を得る方法は複数存在します。既存の手法がどの程度のパフォーマンスを示すのか気になったので調査してみました。
これから使用するハッシュ関数は以下のStack Overflowのページから引用しています。
評価方法
今回は性能の指標として、それぞれのハッシュ関数から出力される値をハッシュ値の衝突回数を調査しました。
こちらが、入力値を生成しハッシュ値の衝突をカウントするために使用したコードです。
//hashに変更するvectorを生成
std::vector<std::vector<int>> make_vector()
{
std::vector<std::vector<int>> vectors;
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
for (int k = 0; k < 100; k++)
{
vectors.push_back(std::vector<int>{i, j, k});
}
}
}
return vectors;
}
int main()
{
const std::vector<std::vector<int>> vectors = make_vector();
std::ofstream file;
file.open("vector_hash.csv");
int count = 0;
std::unordered_set<int> hash_set;
for (const std::vector<int> &vec : vectors)
{
const std::size_t hash = HASH(vec);
file << hash << " ";
if (hash_set.find(hash) != hash_set.end())
{
count++;
continue;
}
hash_set.insert(hash);
}
file.close();
std::cout << count << " 回衝突が起こりました " << std::endl;
return 0;
}
大文字のHASHを実際のハッシュ関数に置き換えます。
入力データ
vector[I,J,K]のそれぞれの変数を0から99の間で変化させ、100万通りのvectorを生成し、入力データとします。
検証
Holkannのコード
std::size_t holkann_hash(const std::vector<int> &vec)
{
std::size_t seed = vec.size();
for (auto &i : vec)
{
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
結果
593821回衝突が起こりました
ハッシュ値のヒストグラムはこのようになりました。
横軸はハッシュ値を表しています。
seeのコード
std::size_t see_hash(const std::vector<int> &vec)
{
std::size_t seed = vec.size();
for (auto x : vec)
{
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
seed ^= x + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
調べてみたところ、Appleが公開しているコードに記載されている、os_map_32_hash という関数のようです。
結果
106 回衝突が起こりました
ハッシュ値のヒストグラムはこのようになりました。
Wolfgang Brehmのコード
template <typename T>
T xorshift(const T &n, int i)
{
return n ^ (n >> i);
}
uint32_t hash(const uint32_t &n)
{
uint32_t p = 0x55555555ul; // pattern of alternating 0 and 1
uint32_t c = 3423571495ul; // random uneven integer constant;
return c * xorshift(p * xorshift(n, 16), 16);
}
template <typename T, typename S>
typename std::enable_if<std::is_unsigned<T>::value, T>::type constexpr rotl(const T n, const S i)
{
const T m = (std::numeric_limits<T>::digits - 1);
const T c = i & m;
return (n << c) | (n >> ((T(0) - c) & m));
}
std::size_t wolf_hash(const std::vector<int> &vec)
{
std::size_t ret = 0;
for (auto &i : vec)
{
ret = rotl(ret, 11) ^ hash(i);
}
return ret;
}
結果
355430 回衝突が起こりました
ハッシュ値のヒストグラムはこのようになりました。
Hemilのコード
std::size_t hemil_hash(const std::vector<int> &vec)
{
std::hash<uint32_t> h;
std::size_t ret = vec.size();
for (auto &i : vec)
{
ret ^= h(i) | i;
}
return ret;
}
std::hashを用いた単純な方法のようです。
結果
999872 回衝突が起こりました
ハッシュ値のヒストグラムはこのようになりました。
かなりの回数で重複が起こっているようです、ハッシュ値もかなり狭い範囲に集中しています。
boostのコード
参考としてboost のハッシュ関数を使用してみました。
std::size_t boost_hash(const std::vector<int> &vec)
{
std::size_t hash = vec.size();
for (const int e : vec)
{
hash ^= e + 0x9e3779b9 + (hash << 6) + (hash >> 2);
}
return hash;
}
結果
593821 回衝突が起こりました
ハッシュ値のヒストグラムはこのようになりました。
Holkann のコードにおけるハッシュの初期値を変更しただけだったので、似たような結果が得られました。
結果まとめ
各関数の衝突回数を棒グラフにまとめると以下のようになりました。
この棒グラフより、seeのコードが圧倒的に衝突回数が少なく、関数自体が似ているboostとHolkannは同等でHemilは衝突回数が抜けて多いということがわかります。
ハッシュ値は32bitの整数であり、ハッシュ値の空間は2^32通り（約43億）あるはずです。これに対し入力データは100万通りであるため、ハッシュ値の空間に対して十分な余裕があるにもかかわらず、数十万回の衝突が起こっていたことがかなり驚きでした。
今回は数値ベクトルを入力として試しましたが、文字列などを入力とした場合、どのような結果が出るか検証してみても良いかもしれません。