1

割り当てに問題があります。特定の関数のアルゴリズムを作成して、文字列を取り、それを 40 ビット ハッシュに変換します。これにより、同じ値を持つ 2 つの異なるハッシュを見つける必要があります。TA は、妥当な確率を得る前に、誕生日のパラドックスを使用して個別の文字列の量を見つけることについてヒントを与えてくれました。私の質問は、文字列がなく、長さが設定されていない場合、どのようにこれにアプローチする必要があるかということです。

4

2 に答える 2

3

「誕生日のパラドックス」(まったくパラドックスではない) に関するヒントを考慮すると、あなたの割り当てでは、多くの文字列を生成してハッシュし、衝突する 2 つを見つける必要があると思います。

40 ビットのハッシュ関数を使用しているため、最初の衝突を見つけるには (平均で) 2 20 個の文字列を試行する必要があると予想されます。これにアプローチする 1 つの方法は、長さが 0 以上のあらゆる文字列を生成してハッシュ化することです。

それを行う1つの方法は次のようなものです: (私は実際にこのコードを試したことはありません.)

using std::string;

template <typename F>
bool GenAllStrings_Worker (string & s, unsigned idx, string const & char_set,
                           unsigned long long & cnt, F f)
{
    if (idx >= s.size())
        return f(s, ++cnt);

    for (auto c : char_set)
    {
        s[idx] = c;
        if (GenAllStrings_Worker(s, idx + 1, char_set, cnt, f))
            return true;
    }

    return false;
}

// Continues generating successively longer strings until "f" returns true.
// Passes each generated string and number of strings generated so far to "f".
template <typename F>
void GenAllStrings (string const & char_set, F f)
{
    unsigned long long cnt = 0;

    for (unsigned len = 0; ; ++len)
    {
        string s (len, '?');
        if (GenAllStrings_Worker (s, 0, char_set, cnt, f))
            return;
    }
}

hash_codeそして、次のように使用できます: (型と関数を提供する必要があることを忘れないでくださいMyHashFunction。)

std::unordered_map<hash_code, string> generated_hashes;

GenAllStrings ("abcdef...ABCD...0123...whatever",
    [&](string const & s, unsigned long long cnt){
        hash_code h = MyHashFunction(s);
        if (generated_hashes.find(h) != generated_hashes.end())
        {
            std::cout << "#" << cnt << " - Found a collision: '" << s <<"'"
                 << " collides with '" << generated_hashes[h] << "'"
                 << ", with a hash of " << h << std::endl;
            return true;
        }
        h[h] = s;
        return false;
    });

GenAllStrings最初の衝突後に停止する関数に渡すラムダを記述しました。ただし、必要な数の衝突を生成することができます (または時間があれば)、特定の長さの文字列に達したら停止します。

于 2013-09-20T00:42:38.200 に答える
1

ヒント: 誕生日のパラドックスを適用する場合、これらの文字列のうち 2 つが同じ 40 ビット ハッシュを持つ確率が高くなるためには、いくつのランダム文字列が必要ですか?

そんなに多くの文字列を生成するプログラムを書いて、衝突を見つけてみませんか?

于 2013-09-20T00:42:05.097 に答える