布隆过滤器的对立面？

Question

我正在尝试优化一个基本上运行数百万次测试的软件。这些测试的生成方式可能会有一些重复。当然，如果我能有效地避免已经运行过的测试，我不想花时间运行这些测试。

因此，我正在考虑使用Bloom filter来存储已经运行的测试。然而，Bloom过滤器在不安全的方面对我来说是错误的。它会给出假阳性结果。也就是说，它可能会报告我运行了一个我没有运行过的测试。虽然这在我正在工作的场景中是可以接受的，但我想知道是否有一个等同于Bloom filter的测试，但在相反的方面，也就是只给出假阴性。

我粗略地浏览了一下文献，却一无所获。

Answer 1

是的，有损哈希表或LRUCache是一种具有快速O(1)查找的数据结构，它只会给出假阴性--如果您问“是否运行测试X"，它将告诉您”是的，您肯定记得“，或者”我记不住了“。

请原谅非常粗糙的伪代码：

setup_test_table():
    create test_table( some large number of entries )
    clear each entry( test_table, NEVER )
    return test_table

has_test_been_run_before( new_test_details, test_table ):
    index = hash( test_details , test_table.length )
    old_details = test_table[index].detail
    // unconditionally overwrite old details with new details, LRU fashion.
    // perhaps some other collision resolution technique might be better.
    test_table[index].details = new_test_details
    if ( old_details === test_details ) return YES
    else if ( old_details === NEVER ) return NEVER
    else return PERHAPS    

main()
    test_table = setup_test_table();
    loop
        test_details = generate_random_test()
        status = has_test_been_run_before( test_details, test_table )
        case status of
           YES: do nothing;
           NEVER: run test (test_details);
           PERHAPS: if( rand()&1 ) run test (test_details);
    next loop
end.

Answer 2

完成此任务的确切数据结构是Direct-mapped cache，通常在CPU中使用。

function set_member(set, item)
    set[hash(item) % set.length] = item

function is_member(set, item)
    return set[hash(item) % set.length] == item

Answer 3

有没有可能存储你而不是运行的测试？这应该会颠倒过滤器的行为。