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

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

【位圖方法】：

位圖（BitMap）

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

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

原來32個(gè)比特位放一個(gè)數(shù)據(jù)，現(xiàn)在一個(gè)位就可以放一個(gè)數(shù)據(jù)。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開辟多一個(gè)空間，如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))表示該二進(jìn)制位不存在，則該位二進(jìn)制置成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;

       //該位存在則將該位二進(jìn)制置為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__

【布隆過濾器】（仿函數(shù)實(shí)現(xiàn)，選5個(gè)位圖）

#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__

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

本文標(biāo)題：位圖與布隆過濾器-創(chuàng)新互聯(lián)
文章位置：http://jinyejixie.com/article28/jiijp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、服務(wù)器托管、品牌網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)