溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
我們先給出之前我看過的騰訊公司的一道筆試題，引出位圖BitMap。
給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。
這個問題怎么解決呢？
1）將40億數據保存起來（保存在數組、鏈表、樹中），再和該數判斷是否相等。
那我們思考一下需要多少內存：
2）借助位圖BitMap解決。
位圖（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__布隆過濾器（BloomFilter）
它是由一個很長的二進制向量和一系列隨機映射函數組成，布隆過濾器可以用于檢索一個元素是否在一個集合中。那我們可以利用哈希函數計算出它具體的存放位置。
它的優點是空間效率和查詢時間都遠遠超過一般的算法，將這40億的數據內存由16GB變成500MB,可見其強大。
缺點是有一定的誤識別率、不便于刪除。布隆過濾器會出現：檢測存在，而實際中卻不存在。而不會出現：實際中不存在，而檢測存在。
代碼實現（仿函數實現，選取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__布隆過濾器代碼實現（借助素數表獲取下一個素數，選取合適的容量--》hash函數）：：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include <string>
#include "Common.h"
#include "BitMap.h"
template<class T=string,
class HashFunc1 = __HashFunc1<T>,
class HashFunc2 = __HashFunc2<T>,
class HashFunc3 = __HashFunc3<T>,
class HashFunc4 = __HashFunc4<T>,
class HashFunc5 = __HashFunc5<T>>
class BloomFilter
{
public:
BloomFilter(size_t capacity =0)
{
_capacity = _GetnewSize(capacity);
_bm.Resize(capacity);
}
void Set(const T& key)
{
size_t index1 = HashFunc1()(key);
size_t index2 = HashFunc2()(key);
size_t index3 = HashFunc3()(key);
size_t index4 = HashFunc4()(key);
size_t index5 = HashFunc5()(key);
_bm.Set(index1%_capacity);
_bm.Set(index2%_capacity);
_bm.Set(index3%_capacity);
_bm.Set(index4%_capacity);
_bm.Set(index5%_capacity);
}
bool Test(const T& key)
{
size_t index1 = HashFunc1()(key);
if (!(_bm.Test(index1% _capacity)))
{
return false;
}
size_t index2 = HashFunc2()(key);
if (!(_bm.Test(index2% _capacity)))
{
return false;
}
size_t index3 = HashFunc3()(key);
if (!(_bm.Test(index3% _capacity)))
{
return false;
}
size_t index4 = HashFunc4()(key);
if (!(_bm.Test(index4% _capacity)))
{
return false;
}
size_t index5 = HashFunc5()(key);
if (!(_bm.Test(index5% _capacity)))
{
return false;
}
return true;
}
private:
BitMap _bm;
size_t _capacity;//布隆過濾器的容量
};
void TestBloomFilter()
{
BloomFilter<> bf(100);
bf.Set("Just Do IT!");
bf.Set("布隆過濾器");
bf.Set("https://mail.google.com/mail/#inbox");
cout << "Is exist? :" << bf.Test("測試工程師") << endl;
cout << "Is exist? :" << bf.Test("開發工程師") << endl;
cout << "Is exist? :" << bf.Test("IT") << endl;
cout << "Is exist? :" << bf.Test("布隆過濾器") << endl;
cout << "Is exist? :" << bf.Test("BloomFilter") << endl;
cout << "Is exist? :" << bf.Test("https://mail.google.com/mail/#inbox") << endl;
cout << "Is exist? :" << bf.Test("https://mail.google.com/mail/#inbox111111") << endl;
}
int main()
{
TestBloomFilter();
system("pause");
return 0;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
