std :: hashとの予期しない衝突

Question

32b intに無限の数のハッシュがあることを知っていますが、衝突を生成する必要があります。

これらの2つの文字列が同じハッシュを持つのは奇妙ではありませんか？

size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
//hash0 == hash1 

私はboost::hash<std::string>等を使用することができます知っているが、私はstd::hashと間違っているかを知りたいです。私はそれを間違って使っていますか？どういうわけか "シード"してはいけませんか？

Answer 1

std::hashの使用状況と間違って何もありません：私は別のハッシュ値（GCC 4.5）を取得します。問題は、Visual Studio 2010にバンドルされている標準ライブラリの実装で提供される特殊化std::hash<std::string>は、文字列の文字のサブセットのみを取り、ハッシュ値（おそらくパフォーマンスの理由から）を判断することです。偶然、14文字の文字列の最後の文字はこのセットの一部ではないため、両方の文字列が同じハッシュ値を生成します。

私が知る限り、この動作は標準に準拠しています。は、同じ引数を持つハッシュ関数への複数の呼び出しが常に同じ値を返さなければならないことを要求しています。しかし、ハッシュ衝突の確率はでなければなりません。 VS2010の実装は強制的な部分を満たしていますが、オプションのものは考慮していません。

詳細については、ヘッダファイルxfunctional（私のコピーの869行目から）とC++標準の§17.6.3.4（latest public draft）の実装を参照してください。

文字列にはより良いハッシュ関数が必要な場合は、自分で実装する必要があります。実際にはnot that hardです。

Answer 2

ハッシュ関数を設定していない場合は、せいぜい「それら」をソートすることができます。

この関数は正しい方法で使用され、この衝突はちょうど偶然になります。

ランダムキーで大量のテストを実行しない限り、ハッシュ関数が均等に分散されているかどうかはわかりません。

Answer 3

TR1ハッシュ関数と最新の標準では、文字列などの適切なオーバーロードが定義されています。 std :: tr1 :: hash（g ++ 4.1.2）を使ってこのコードを実行すると、これらの2つの文字列に対して異なるハッシュ値が得られます。

Answer 4

異なるハッシュ値が得られるはずです。

hashtest.cpp

#include <string> 
#include <iostream> 
#include <functional> 
int main(int argc, char** argv) 
{ 
size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n"; 
return 0; 
} 

出力

# g++ hashtest.cpp -o hashtest -std=gnu++0x 
# ./hashtest 
16797002355621538189 != 16797001256109909978 

Answer 5

正確なハッシュアルゴリズムは標準では指定されていないため、結果は です。文字列が10文字より長い場合、VC10で使用されるアルゴリズムは、 文字をすべて考慮していないようです。 は、インクリメントが1 + s.size()/10になります。これは合法ですが、QoIの観点からではありますが、むしろ失望していますが です。そのようなハッシュコード は、いくつかの典型的なデータセット（例えば、 のURL）に対して非常に不十分に機能することが知られています。私は強くあなたが総理メルセンヌに基づ​​いてFNVハッシュまたは 1のいずれかでそれを置き換えることをお勧めしたい：

FNVハッシュ：

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = (16777619 * result) 
        ^static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

メルセンヌ数ハッシュ：

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = 127 * result 
        + static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

（FNVハッシュはおそらくより良いと思われますが、Mersenneのプライムハッシュは、多くのマシンでは の方が速くなります。なぜなら127を掛けるほうが、しばしば を2166136261で乗算するよりも速くなるからです。