data-structures - 是否有任何概率数据结构会产生假阴性但不会产生假阳性？

Question

我需要一个空间高效的概率数据结构来存储我已经计算过的值。对我来说计算很便宜但空间不是 - 所以如果这个数据结构返回一个假阴性，我可以每隔一段时间重做一些工作，但假阳性是 Not Acceptable 。所以我正在寻找的是与 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.

类似的布隆过滤器用于误报