Example Analysis of Bitmap and Bloom filter in C++

This article mainly introduces the C++ bitmap and Bloom filter example analysis, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.

Bitmap and Bloom filter for C++ hash application

1. Bitmap 1. The concept of bitmap

The so-called bitmap is that each bit is used to store a certain state, which is suitable for scenarios where there is no repetition of massive data. It is usually used to determine whether a certain data exists.

two。 Face-to-face questions for bitmaps

Give 4 billion unrepeated unsigned integers, unsorted. Give an unsigned integer, how to quickly determine whether a number is in these 4 billion numbers. [Tencent]

Traversal, time complexity O (N).

Sort (O (NlogN)), using binary search: logN.

Bitmap solution.

Whether the data is in the given shaping data, and the result is in or out, happens to be in two states, so you can use a binary bit to represent the information about the existence of the data. If the binary bit is 1, it means it exists. 0 means it doesn't exist. For example:

3. Realization of bitmap

# include#include#includenamespace yyw {class bitset {public: bitset (size_t N) {_ bits.resize (N / 32 + 1,0); _ num = 0;} / / set the bit of x to 1 void set (size_t x) {size_t index = x / 32; / / map out the shaping size_t pos = x% 32 / / map out the position of x in the shaping position _ bits [index] | = (1)