操作SHA256哈希的大型文本数据库的最有效方法？

Question

我必须经常在这种格式的大型（高达1G）CSV数据库中搜索哈希

sha256_hash, md5_hash, sha1_hash, field1, field2, field3 etc

在C.这需要非常快，内存使用不是问题（最低32G）。我发现这非常接近我的想法：将数据加载到内存中，一次性按哈希排序数据库，按哈希的第一个n字节索引，然后通过较小的子列表搜索。但是上面的帖子似乎没有解决我中间的一个问题。因为我不是一个密码学的家伙，我想知道哈希的分布，以及它是否可以用来更快地搜索子列表。对此或我的总体方法有什么建议吗？

Answer 1

散列的分布是统一的，这很有帮助，因为您可以将散列放在散列表中。

// something like this...
struct entry {
    bool used;
    unsigned char sha256[32];
    char field1[20];
    char field2[20];
};

如果您不需要从哈希表中删除条目，只需创建一个大数组结构条目，并将CSV中的记录插入到与SHA-256哈希中的一些位相对应的索引中。使用线性探测来插入条目：如果使用条目i，则使用i 1或i 2，直到找到一个空闲条目。

struct table {
    int nbits;
    struct entry *entries;
};

unsigned read_int(unsigned char *data)
{
    unsigned v = data[0] | (data[1] << 8) |
                 (data[2] << 16) | ((unsigned)data[3] << 24);
}

struct entry *find_entry(struct table *table, unsigned char *sha256)
{
    unsigned index = read_int(sha256);
    unsigned mask = (1u << table->nbits) - 1;
    while (1) {
        struct entry *e = &table->entries[index & mask];
        if (!e->used)
            return NULL;
        if (!memcmp(e->sha256, sha256, 32))
            return e;
        index++;
    }
}

Answer 2

这是一个非常容易用大量内存解决的问题。使哈希成为哈希表的键。将提供给表的哈希设置为哈希的前N个字节（因为它们是如此随机，地球上没有人能将它们与真正的随机数据区分开来）。

不确定您的想法是什么，用键前缀为表设置键，并使用子列表。任何提供哈希表的股票库都可以轻松解决您的问题。

或者将其放入任何数据库，并使哈希成为主键。

Answer 3

是的，通过使用散列位的分布，布鲁姆过滤器可以用来提前剔除“明确的否定”。

http://en.wikipedia.org/wiki/Bloom_filter

要为给定的bucket创建bloomfilter，可以使用逻辑或所有散列来创建过滤器。然后，使用目标哈希对逻辑和筛选器进行排序。如果结果是

必须注意桶大小，以便产生有意义的过滤器，因为所有高位的过滤器对任何人都没有价值。