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

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

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Closed
    • Minor
    • Resolution: Fixed
    • 2.5.1
    • 2.7.0
    • util
    • None
    • 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

            epayne Eric Payne
            tim.luo Tim Luo
            Votes:
            4 Vote for this issue
            Watchers:
            9 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: