給40億個不重復(fù)的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中。這個問題怎么解決呢？

成都創(chuàng)新互聯(lián)專注于北屯企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站,成都商城網(wǎng)站開發(fā)。北屯網(wǎng)站建設(shè)公司,為北屯等地區(qū)提供建站服務(wù)。全流程定制設(shè)計，專業(yè)設(shè)計，全程項目跟蹤，成都創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

【位圖方法】：

位圖（BitMap）

是用一個數(shù)組中的每個數(shù)據(jù)的每個二進制位表示一個數(shù)是否存在。1表示存在，0表示不存在。

相當(dāng)于把數(shù)組分成很多塊的空間，每一塊是32個比特位。

原來32個比特位放一個數(shù)據(jù)，現(xiàn)在一個位就可以放一個數(shù)據(jù)。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__

【布隆過濾器】（仿函數(shù)實現(xiàn)，選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__

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章題目：位圖與布隆過濾器-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://weahome.cn/article/jiijp.html