Uploaded image for project: 'Hadoop Common'
  1. Hadoop Common
  2. HADOOP-11327

BloomFilter#not() omits the last bit, resulting in an incorrect filter

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 2.5.1
    • Fix Version/s: 2.7.0
    • Component/s: util
    • Labels:
      None
    • Target Version/s:
    • Hadoop Flags:
      Reviewed

      Description

      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:

      * @param  toIndex index after the last bit to flip
      

      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.

        Attachments

        1. HADOOP-11327.v2.txt
          2 kB
          Eric Payne
        2. HADOOP-11327.v1.txt
          1 kB
          Eric Payne

          Activity

            People

            • Assignee:
              eepayne Eric Payne
              Reporter:
              tim.luo Tim Luo
            • Votes:
              4 Vote for this issue
              Watchers:
              9 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: