Geek asks and answers

What am I doing wrong in this flowering filter implementation?

I have this bit table for a segmented flowering filter. Here, each column is controlled by a single hash function.

unsigned char bit_table_[ROWS][COLUMNS];//bit_table now have 8*ROWS*COLUMNS bits
unsigned char bit_mask[bits_per_char] = { 0x01,0x02,0x04,0x08,
                                          0x10,0x20,0x40,0x80};

The number of ROWS hash functions , each of which handles the setting and verification of COLUMNS * 8 bits .

Elements are hashed and index_bit and bit are computed as

compute_indices(unsigned int hash)
{
   bit_index=hash%COLUMNS;
   bit=bit_index%8;
}

Now insetion runs as

for (std::size_t i = 0; i < ROWS; ++i)
      {
        hash=compute_hash(i,set_element);
        compute_indices(hash);
        bit_table_[i][bit_index ] |= bit_mask[bit]; 
      }

And request

for (std::size_t i = 0; i < ROWS; ++i)
      {
     hash=compute_hash(i,set_element);
      compute_indices(hash);

      if (((bit_table_[i][bit_index])& bit_mask[bit]) != bit_mask[bit])
         {
            return false;
         }      
  }

My problem is that the flower filter is filling up too early, and I suspect that I am not using individual bits of characters correctly. For example, I suppose I should have something like:

table bit [i] [index bit] [bit] | = mask_bit [bit];

, bit_table , .

, char?

- , . , .

EDIT:    compute_hash (i, set_elemnt) - , .

+3
1

compute_indices .

, modulo 8 . . , 10 2.

:

compute_indices(unsigned int hash)
{
    int bitIndex = hash % (COLUMNS * 8);
    bit_index= bitIndex / 8;
    bit = bitIndex % 8;
}
+1

More articles:


All Articles