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

成都創新互聯專注于北屯企業網站建設,響應式網站,成都商城網站開發。北屯網站建設公司,為北屯等地區提供建站服務。全流程定制設計，專業設計，全程項目跟蹤，成都創新互聯專業和態度為您提供的服務

【位圖方法】：

位圖（BitMap）

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

相當于把數組分成很多塊的空間，每一塊是32個比特位。

原來32個比特位放一個數據，現在一個位就可以放一個數據。16GB/32=0.5GB=512MB。

#ifndef __BITMAP_H__
#define __BITMAP_H__
#include<iostream>
using namespace std;

#include<vector>

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<size_t> _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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文標題：位圖與布隆過濾器-創新互聯
文章位置：http://vcdvsql.cn/article28/jiijp.html

成都網站建設公司_創新互聯，為您提供網站營銷、服務器托管、品牌網站建設、靜態網站、外貿網站建設、云服務器

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯