是否有任何概率数据结构，让假阴性，但不误报？(Is there any probabilistic

我需要一个空间效率概率数据结构来存储我已经计算出的值。 对我来说，计算是便宜，但空间不是 - 所以，如果该数据结构返回一个假阴性，我还好，在一段时间重做一些工作，每一次，但误报是不可接受的。 所以，我在找的是那种一个相反的布隆过滤器 。

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.

同样布隆过滤误报

文章来源: Is there any probabilistic data structure that gives false negatives but not false positives?