用很少的位保存多个编号,可以快速排除某些不在集合中的对象。但多个编号可能落在相同位置,使筛选结果出现看似存在却实际没加入的情况。
位数组初始全零,对每个编号x设置两个位置:(3x加1)对m取余,以及(5x加7)对m取余。查询时两个位置都为一就回答可能存在,有任意一处为零就回答不存在;真实集合只用于本例对照。
位数组长度18,加入编号[2, 63, 15, 21, 48, 76, 72, 1]。加入后位数组为[0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1]。
查询 | 两个位置 | 可能存在 | 实际属于集合 | 是否误报 2 | [7, 17] | True | True | False 63 | [10, 16] | True | True | False 15 | [10, 10] | True | True | False 31 | [4, 0] | False | False | False 8 | [7, 11] | False | False | False 12 | [1, 13] | True | False | True 50 | [7, 5] | False | False | False 56 | [7, 17] | True | False | True 73 | [4, 12] | True | False | True 68 | [7, 5] | False | False | False 47 | [16, 8] | False | False | False 29 | [16, 8] | False | False | False
阅读记录时先确认编号代表的是格子、对象、时间还是数组位置,再逐项对应输入与输出。中间状态提供了定位差异的依据,最后的一个合计数字不能替代全部步骤;没有对象的集合与数值零也应区别看待。
所有已经加入的编号都应被判为可能存在,未加入的编号则可能误报。误报不是解码出了另一个编号,而是少量位无法完整区分不同集合;表格同时保留真实成员判断。
这只是成员筛选模型,不提供精确的物品拥有状态,也不能直接据此删除或发放道具。若删除对象时随意把其两位清零,还可能误伤共享这些位的其他对象;本例只执行加入与查询。
可以遮住结果表先按规则复算第一步,再选择一个边界输入重复操作。若更换规则中的任一前提,应重新推导结果,不要只调整最后答案。这样既能理解本例为何成立,也能看清它在哪些情况下不再适用。