0

ハッシュ関数から多くの (2^30 x 50 ビット) 出力があります。何らかの方法でそれを保存し、すべての新しい要素を以前の要素と比較し、一意の場合は挿入する必要があります。新しい要素を挿入している間にハッシュ値の配列が台無しになっていない場合は、ハッシュ値を保存する必要はありません。それらは連続しています。

それを保存して重複を検索するにはどうすればよいですか?

ハッシュの値として、「1」、「2」、「3」、「4」、.....

EDITED：出力スペース50ビットのハッシュ関数のBAには、ほぼ1.25 * sqrt（2 ^ 50）の試行が必要です。すべての出力は 50 ビットです。つまり、250M バイト近くのスペースです。

4

2 に答える 2

0

std::mapの使用:

#include <string>
#include <map>
#include <sstream>
#include <algorithm>
#include <iterator>

using namespace std;

string toString(long value)
{
    ostringstream oss;
    oss << value;
    return oss.str();
}

long hash(const string& key)
{
    return 0;
}

string generateKey()
{
    static long value = 0;
    ++value;
    return toString(value);
}

pair<string, long> generateKeyValuePair()
{
    string key = generateKey();
    return make_pair(key, hash(key));
}

主な機能:

int main()
{
    map<string, long> hashes;

    generate_n(inserter(hashes, hashes.begin()), 5, generateKeyValuePair);

    return 0;
}
于 2012-05-17T10:40:56.443 に答える
0

何を達成しようとしているのか正確にはわかりませんが、プロセスを高速化するために、要素の存在を事前にチェックするためにブルーム フィルターを使用する必要があるかもしれません。

この記事で「m 個の異なるハッシュ関数」と記載されている場合、それが実際に意味することは、無関係な結果を生成する異なるパラメーターを持つ同じアルゴリズムである m 個の異なる関数ということです。たとえば、ハッシュするデータの先頭に 0 から までの値のバイトを追加するだけですm-1。または、SHA256 ハッシュの 256 ビットを取得して、それを 24 ビットのグループに分割するか、必要なフィルタの大きさに分割することができます。

于 2012-05-17T10:07:18.880 に答える