位图与布隆过滤器-创新互联

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。这个问题怎么解决呢？

【位图方法】：

位图（BitMap）

是用一个数组中的每个数据的每个二进制位表示一个数是否存在。1表示存在，0表示不存在。

相当于把数组分成很多块的空间，每一块是32个比特位。

原来32个比特位放一个数据，现在一个位就可以放一个数据。16GB/32=0.5GB=512MB。

#ifndef __BITMAP_H__
#define __BITMAP_H__
#include
using namespace std;

#include

class BitMap
{
public:
   BitMap(size_t size = 0)
       :_size(0)
   {
       //_a开辟多一个空间，如size=36/32=1,需要两块空间才能放下
       _a.resize((size >> 5) + 1);
   }

   void Set(size_t x)
   {
       //size_t index = x / 32;
       size_t index = (x >> 5);
       size_t num = x % 32;

       //if(!(_a[index] & (1 << num))表示该二进制位不存在，则该位二进制置成1
       if (!(_a[index] & (1 << num)))
       {
           _a[index] |= (1 << num);
           ++_size;
       }
   }

   void Reset(size_t x)
   {
       //size_t index = x / 32;
       size_t index = x >> 5;
       size_t num = x % 32;

       //该位存在则将该位二进制置为0
       if (_a[index] & (1 << num))
       {
           _a[index] &= ~(1 << num);
           --_size;
       }
   }

   bool Test(size_t x)
   {
       //size_t index = x / 32;
       size_t index = x >> 5;
       size_t num = x % 32;
       if (_a[index] & (1 << num))
       {
           return true;
       }
       return false;
   }

   void Resize(size_t size)
   {
       _a.resize(size);
   }
private:
   vector _a;
   size_t _size;
};

#endif //__BITMAP_H__

【布隆过滤器】（仿函数实现，选5个位图）

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __COMMON__
#define __COMMON__

size_t _GetnewSize(size_t _size)
{
   static const int _PrimeSize = 28;
   static const unsigned long _PrimeList[_PrimeSize] =
   {
       53ul, 97ul, 193ul, 389ul, 769ul,
       1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
       49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
       1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
       50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
       1610612741ul, 3221225473ul, 4294967291ul
   };

   for (int i = 0; i < _PrimeSize; i++)
   {
       if (_PrimeList[i]> _size)
       {
           return _PrimeList[i];
       }
   }
   return _PrimeList[_PrimeSize - 1];
}

template
struct __HashFunc1
{
   size_t BKDRHash(const char *str)
   {
       register size_t hash = 0;
       while (size_t ch = (size_t)*str++)
       {
           hash = hash * 131 + ch;  // 也可以乘以31、131、1313、13131、131313..

       }
       return hash;
   }

   size_t operator()(const T& key)
   {
       return BKDRHash(key.c_str());
   }
};

template
struct __HashFunc2
{
   size_t SDBMHash(const char *str)
   {
       register size_t hash = 0;
       while (size_t ch = (size_t)*str++)
       {
           hash = 65599 * hash + ch;
           //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
       }
       return hash;
   }

   size_t operator()(const T& key)
   {
       return SDBMHash(key.c_str());
   }
};

template
struct __HashFunc3
{
   size_t RSHash(const char *str)
   {
       register size_t hash = 0;
       size_t magic = 63689;
       while (size_t ch = (size_t)*str++)
       {
           hash = hash * magic + ch;
           magic *= 378551;
       }
       return hash;
   }

   size_t operator()(const T& key)
   {
       return RSHash(key.c_str());
   }
};

template
struct __HashFunc4
{
   size_t JSHash(const char *str)
   {
       if (!*str)       // 这是由本人添加，以保证空字符串返回哈希值0
           return 0;
       register size_t hash = 1315423911;
       while (size_t ch = (size_t)*str++)
       {
           hash ^= ((hash << 5) + ch + (hash >> 2));
       }
       return hash;
   }

   size_t operator()(const T& key)
   {
       return JSHash(key.c_str());
   }
};

template
struct __HashFunc5
{
   size_t DEKHash(const char* str)
   {
       if (!*str)       // 这是由本人添加，以保证空字符串返回哈希值0
           return 0;
       register size_t hash = 1315423911;
       while (size_t ch = (size_t)*str++)
       {
           hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
       }
       return hash;
   }

   size_t operator()(const T& key)
   {
       return DEKHash(key.c_str());
   }
};

#endif//__COMMON__

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。