Tim Luo created HADOOP-11327:
--------------------------------
Summary: BloomFilter#not() omits the last bit, resulting in an
incorrect filter
Key: HADOOP-11327
URL: https://issues.apache.org/jira/browse/HADOOP-11327
Project: Hadoop Common
Issue Type: Bug
Components: util
Affects Versions: 2.5.1
Reporter: Tim Luo
Assignee: Tim Luo
Priority: Minor
There's an off-by-one error in {{BloomFilter#not()}}:
{{BloomFilter#not}} calls {{BitSet#flip(0, vectorSize - 1)}}, but according to
the javadoc for that method, {{toIndex}} is end-_exclusive_:
{noformat}
* @param toIndex index after the last bit to flip
{noformat}
This means that the last bit in the bit array is not flipped.
Specifically, this was discovered in the following scenario:
1. A new/empty {{BloomFilter}} was created with vectorSize=7.
2. Invoke {{bloomFilter.not()}}; now expecting a bloom filter with all 7 bits
(0 through 6) flipped to 1 and membershipTest(...) to always return true.
3. However, membershipTest(...) was found to often not return true, and upon
inspection, the BitSet only had bits 0 through 5 flipped.
The fix should be simple: remove the "- 1" from the call to {{BitSet#flip}}.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
