c++ - 如何有效地存储和排序生日攻击的哈希值

Question

我有很多（2^30 x 50 位）哈希函数的输出。我需要以某种方式存储它并将每个新元素与以前的所有元素进行比较，如果它是唯一的则插入。如果我插入新元素时我的哈希值数组没有搞砸，那么我不需要存储哈希值，它们是顺序的。

我如何存储它然后搜索重复？

作为散列值，我只使用“1”，“2”，“3”，“4”，......

已编辑：输出空间为 50 位的散列函数的 BA 需要近 1.25*sqrt(2^50) 次尝试。每个输出 50 位。所以它有将近 250 MB 的空间。

Answer 1

使用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;
}

Answer 2

不确定您要实现的确切目标，但也许您需要使用布隆过滤器作为元素是否存在的初步检查，以加快处理过程。

请注意，当文章说“m 个不同的哈希函数”时，它的真正含义是，m 个不同的函数可以是具有不同参数的相同算法，产生不相关的结果。例如，您可以简单地在要散列的数据前面加上一个 0 到m-1. 或者，您可以获取 SHA256 哈希的 256 位并将其分成 24 位组，或者您需要过滤器的大小。