位圖
1. 位圖概念
位圖（Bitset）是一種數(shù)據(jù)結(jié)構(gòu)，用于表示一組布爾值，其中每個元素通常對應(yīng)于一個位或一個二進(jìn)制值，可以存儲0或1。位圖在計算機(jī)科學(xué)和計算機(jī)工程中經(jīng)常用于各種應(yīng)用，特別是在位級別的標(biāo)志、掩碼和快速查找中。以下是位圖的一些關(guān)鍵特點：
- 二進(jìn)制表示：位圖中的每個元素都只能存儲兩個值，通常是0和1。這使得位圖非常高效，因為每個位只需要一個二進(jìn)制位來表示。
- 位操作：位圖支持各種位操作，包括設(shè)置位、清除位、翻轉(zhuǎn)位和查詢特定位的操作。
- 空間效率：位圖在表示大量布爾值時非常節(jié)省內(nèi)存，因為每個位只需要一個二進(jìn)制位。這使得位圖在大規(guī)模數(shù)據(jù)處理中非常有用。
- 快速查找：位圖用于快速查找元素的存在或不存在。通過檢查位的值，可以快速確定元素是否在集合中。
- 位運(yùn)算：位圖支持位級別的位運(yùn)算，如與、或、異或等，這些運(yùn)算可用于合并和操作多個位圖。
應(yīng)用領(lǐng)域包括：
- 位掩碼：用于將一組標(biāo)志或選項組合在一起，并進(jìn)行快速檢查和設(shè)置。
- 布爾向量：用于高效存儲和操作布爾值集合。
- 集合操作：用于執(zhí)行集合操作，如并集、交集和差集。
- 壓縮和編碼：用于壓縮數(shù)據(jù)，如運(yùn)行長度編碼（Run-Length Encoding）等。
2. 位圖在實際中的應(yīng)用
某大廠給過這樣一道面試題，具體如下：
給40億個不重復(fù)的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中
你可能最開始想遍歷？那肯定是不行的，因為40億個無符號數(shù)占用將近15G內(nèi)存。
那使用散列表呢？那這里使用的空間能在內(nèi)存上嗎？顯然不可以，就算可以
- 散列表需要大量內(nèi)存，因為需要為40億個整數(shù)維護(hù)哈希表。
- 哈希沖突可能會導(dǎo)致性能下降，需要解決沖突。
- 需要選擇合適的哈希函數(shù)以避免碰撞。
又會遇到各種各樣的問題
那么這里就可以用到我們上面提到的位圖概念
位圖（Bitset）方法：
- 創(chuàng)建位圖：首先，創(chuàng)建一個足夠大的位圖，以能夠表示您的整數(shù)范圍。例如，如果整數(shù)范圍在0到4,000,000,000之間，可以創(chuàng)建一個長度為4,000,000,001的位圖。
- 插入數(shù)據(jù)：將這40億個無符號整數(shù)中的每個整數(shù)映射到位圖的相應(yīng)位置，并將對應(yīng)的位設(shè)置為1。
- 查詢數(shù)據(jù)：當(dāng)需要判斷一個數(shù)是否在這40億個數(shù)中時，只需查看位圖中相應(yīng)位置的位。如果該位為1，表示該整數(shù)在集合中；如果該位為0，表示不在集合中。
優(yōu)點：
- 位圖非常節(jié)省內(nèi)存，因為每個整數(shù)只需要一個位。
- 不需要哈希函數(shù)，也不需要解決哈希沖突。
這里我們只需要不到500M就很好的解決了這個問題，聽起來挺理想的，那么應(yīng)該如何來實現(xiàn)它呢？
代碼如下：
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N/8+1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
模板的作用就是用來傳需要查詢數(shù)的范圍，比如我們這里有40億怎么傳值呢？
因為是無符號數(shù)，而無符號數(shù)范圍是0-42億左右，那我們不妨傳入最大值，即-1
bitset<-1> bs1;
你可能會有疑問，多了兩億不會多很多內(nèi)存嗎？
答案是不會，占滿其實也就512M，具體我們看下面的實現(xiàn)
我們先看成員變量的建立，由于在編程語言中，我們沒有按位存儲的存儲類型（至少C/C++是沒有的）
所以這里我們采用最小存儲類型char，char占1個字節(jié)，可是我們需要的是1bit，那么我們該如何做呢？
接下來我們看位圖的構(gòu)造函數(shù)，我們用模板參數(shù)/8，初始化每個字節(jié)為全0，多+1是由于數(shù)組的索引從0開始，所以需要額外的一個元素來確保能夠容納最高索引 N-1 的位，這樣我們的空間開辟完畢，也初始化完畢
接下來我們看set函數(shù)（此函數(shù)用于入位圖）
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
用于將指定索引 x 處的位設(shè)置為1：
-
size_t i = x / 8;：這一行代碼計算索引x對應(yīng)的字節(jié)（byte）索引。因為_bits是一個vector<char>，每個元素代表一個字節(jié)（8位），所以我們用索引x除以8來得到字節(jié)索引。 -
size_t j = x % 8;：這一行代碼計算索引x對應(yīng)的位在字節(jié)中的位置。它使用取模運(yùn)算來獲得余數(shù)，表示在字節(jié)中的位偏移。 -
_bits[i] |= (1 << j);：這一行代碼使用位操作將位圖中索引x處的位設(shè)置為1。具體來說：-
(1 << j)會創(chuàng)建一個只有第j位為1的整數(shù)。例如，如果j是3，那么(1 << 3)將得到二進(jìn)制00001000。 -
_bits[i] |= (1 << j)利用位或運(yùn)算符將_bits[i]中對應(yīng)的位和上面的整數(shù)進(jìn)行“或”操作，將指定位設(shè)置為1。
-
這個函數(shù)的目的是在位圖中設(shè)置指定索引 x 處的位為1，從而表示該位置存在某種標(biāo)記或狀態(tài)。
reset函數(shù)（此函數(shù)用于出位圖）
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
用于將指定索引 x 處的位重置為0：
-
size_t i = x / 8;：這一行代碼計算索引x對應(yīng)的字節(jié)（byte）索引，以確定所在的字節(jié)。 -
size_t j = x % 8;：這一行代碼計算索引x對應(yīng)的位在字節(jié)中的位置，以確定位的偏移。 -
_bits[i] &= ~(1 << j);：這一行代碼使用位操作將位圖中索引x處的位重置為0。具體來說：-
(1 << j)會創(chuàng)建一個只有第j位為1的整數(shù)。例如，如果j是3，那么(1 << 3)將得到二進(jìn)制00001000。 -
~(1 << j)會創(chuàng)建一個只有第j位為0、其余位為1的整數(shù)，以便將第j位重置為0。 -
_bits[i] &= ~(1 << j)利用位與運(yùn)算符將_bits[i]中對應(yīng)的位和上面的整數(shù)進(jìn)行“與”操作，將指定位設(shè)置為0。
-
這個函數(shù)的目的是在位圖中重置指定索引 x 處的位為0，從而表示該位置不存在某種標(biāo)記或狀態(tài)。
test函數(shù)（此函數(shù)用于查詢數(shù)是否在位圖中）
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
用于檢查指定索引 x 處的位是否為1：
-
size_t i = x / 8;：這一行代碼計算索引x對應(yīng)的字節(jié)（byte）索引，以確定所在的字節(jié)。 -
size_t j = x % 8;：這一行代碼計算索引x對應(yīng)的位在字節(jié)中的位置，以確定位的偏移。 -
_bits[i] & (1 << j)：這一行代碼使用位操作檢查位圖中索引x處的位是否為1。具體來說：-
(1 << j)會創(chuàng)建一個只有第j位為1的整數(shù)。例如，如果j是3，那么(1 << 3)將得到二進(jìn)制00001000。 -
_bits[i] & (1 << j)利用位與運(yùn)算符將_bits[i]中對應(yīng)的位和上面的整數(shù)進(jìn)行“與”操作，以檢查該位是否為1。如果結(jié)果為0，表示該位為0；如果結(jié)果為非0，表示該位為1。
-
這個函數(shù)的目的是檢查位圖中指定索引 x 處的位是否為1，以判斷某種標(biāo)記或狀態(tài)是否存在。如果該位為1，函數(shù)返回true，表示存在；如果該位為0，函數(shù)返回false，表示不存在。
實際上在C++中是加入了位圖這個容器的，名稱和我這一樣，這里我們模擬實現(xiàn)是為了更好的理解這個概念
庫中的bitset功能更多，但主要函數(shù)也是這幾個
3. 位圖相似應(yīng)用
給定100億個整數(shù)，如何找到只出現(xiàn)一次的整數(shù)？
其實這種問題和我們上面的示例的題目類似，解決方式只需略作改動。
我們可以使用兩個位圖分別標(biāo)記存在次數(shù)，也就類似key value型，這里我們只需要標(biāo)記3種情況
代碼如下：
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
bool inset1 = _bs1.test(x);
bool inset2 = _bs2.test(x);
// 00
if (inset1 == false && inset2 == false)
{
// -> 01
_bs2.set(x);
}
else if (inset1 == false && inset2 == true)
{
// ->10
_bs1.set(x);
_bs2.reset(x);
}
else if (inset1 == true && inset2 == false)
{
// ->11
_bs1.set(x);
_bs2.set(x);
}
}
void print_once_num()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs1.test(i) == false && _bs2.test(i) == true)
{
cout << i << endl;
}
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
這里我們需要實現(xiàn)一個雙位圖（Two-Bitset）數(shù)據(jù)結(jié)構(gòu)。雙位圖是一種在每個索引上存儲兩個位的數(shù)據(jù)結(jié)構(gòu)，通常用于表示每個索引的兩種狀態(tài)。代碼解析如下：
-
set(size_t x)函數(shù)：- 首先，它檢查
_bs1和_bs2位圖中索引x處的狀態(tài)。 - 如果
_bs1中索引x處的位為0，而_bs2中索引x處的位也為0（00狀態(tài)），則將_bs2中索引x處的位設(shè)置為1，將其狀態(tài)變?yōu)?1。 - 如果
_bs1中索引x處的位為0，而_bs2中索引x處的位為1（01狀態(tài)），則將_bs1中索引x處的位設(shè)置為1，將_bs2中索引x處的位重置為0，將其狀態(tài)變?yōu)?0。 - 如果
_bs1中索引x處的位為1，而_bs2中索引x處的位為0（10狀態(tài)），則將_bs1和_bs2中索引x處的位都設(shè)置為1，將其狀態(tài)變?yōu)?1。
- 首先，它檢查
-
print_once_num()函數(shù)：- 這個函數(shù)用于打印那些狀態(tài)為10（01狀態(tài)的相反）的索引。這表示只在
_bs2中為1而在_bs1中為0的索引。這些索引被認(rèn)為在雙位圖中只出現(xiàn)一次。
- 這個函數(shù)用于打印那些狀態(tài)為10（01狀態(tài)的相反）的索引。這表示只在
1個文件100億int，1G內(nèi)存，如何找到不超過2次的所有整數(shù)
兩個題目其實相似，無非就是多一種狀態(tài)，原理同上
布隆過濾器
在上面我們用位圖很好的解決了多重整數(shù)高效查詢的問題，那么我們在面對字符串時，該如何解決呢？
1. 布隆過濾器的提出
布隆過濾器（Bloom Filter）是由布隆在1970年提出的，它是一種空間效率高、查詢速度快的數(shù)據(jù)結(jié)構(gòu)，主要用于判斷一個元素是否屬于一個集合。布隆過濾器的提出解決了在大規(guī)模數(shù)據(jù)集中進(jìn)行高效查找的問題，特別是當(dāng)內(nèi)存或存儲有限的情況下。
以下是布隆過濾器的提出背景和主要原理：
提出背景： 在計算機(jī)科學(xué)中，一些常見的問題包括查找元素是否在某個集合中，如單詞拼寫檢查、垃圾郵件過濾、URL檢測等。傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)如散列表或樹結(jié)構(gòu)可以解決這些問題，但它們在存儲和查詢效率上存在一些限制，特別是在面對大規(guī)模數(shù)據(jù)集時。因此，布隆過濾器的提出是為了解決這些限制。
原理： 布隆過濾器的核心思想是使用一個位數(shù)組（Bit Array）和多個哈希函數(shù)。其主要工作步驟如下：
- 初始化：創(chuàng)建一個位數(shù)組，初始所有位為0，以及選擇多個不同的哈希函數(shù)。
- 插入元素：當(dāng)需要插入一個元素時，將該元素經(jīng)過多個哈希函數(shù)的映射，得到多個不同的位，然后將這些位設(shè)置為1。
- 查詢元素：當(dāng)需要查詢一個元素是否在集合中時，將該元素經(jīng)過多個哈希函數(shù)的映射，得到多個位的位置，然后檢查這些位是否都為1。如果所有位都為1，則認(rèn)為元素可能存在于集合中；如果任何一個位為0，則可以確定元素不存在于集合中。
特點：
- 布隆過濾器具有高效的查詢速度，因為它不需要實際存儲元素本身，而只需要檢查位數(shù)組中的位。
- 布隆過濾器可能會出現(xiàn)誤判，即元素被判斷為存在于集合中，但實際上并不在，但不會有漏判，即如果元素不在集合中，布隆過濾器不會將其判斷為存在。
- 布隆過濾器的空間效率很高，因為它可以存儲大量元素而占用很少的內(nèi)存。
2. 布隆過濾器的插入
布隆過濾器的插入過程是其核心操作之一，用于將元素添加到布隆過濾器中，以便后續(xù)查詢該元素是否存在于集合中。下面是布隆過濾器的插入過程的詳細(xì)解釋：
- 初始化：首先，創(chuàng)建一個布隆過濾器，它包括一個位數(shù)組（Bit Array）和多個哈希函數(shù)。位數(shù)組中的每個位都初始化為0。
-
插入元素：要將一個元素插入布隆過濾器，執(zhí)行以下步驟：
- 哈希函數(shù)：使用預(yù)先選擇的多個哈希函數(shù)，將要插入的元素映射為多個不同的位索引。每個哈希函數(shù)都會生成一個位索引，通常使用不同的種子值來確保生成不同的位索引。
- 設(shè)置位：對于每個哈希函數(shù)生成的位索引，將相應(yīng)的位數(shù)組中的位設(shè)置為1。這表示元素已經(jīng)存在于布隆過濾器中。
- 完成插入：一旦對元素執(zhí)行了上述步驟，插入過程就完成了。元素已被記錄在位數(shù)組中，以后可以查詢該元素是否存在于集合中。
注意事項：
- 布隆過濾器不存儲實際元素本身，只存儲元素的哈希值或映射后的位索引。因此，插入操作是基于哈希值的，而不是實際元素。
- 哈希函數(shù)的數(shù)量和質(zhì)量對布隆過濾器的性能至關(guān)重要。更多的哈希函數(shù)通常意味著更低的誤判率，但也需要更多的計算資源。選擇哈希函數(shù)時應(yīng)考慮平衡性能和內(nèi)存占用。
- 插入操作通常是快速的，因為它涉及位數(shù)組的直接設(shè)置，而不需要大量內(nèi)存操作。這是布隆過濾器高效的一個原因之一。
插入過程使布隆過濾器記錄了元素的存在，使后續(xù)的查詢操作成為可能。查詢操作會利用相同的哈希函數(shù)，檢查位數(shù)組中的位來確定元素是否在集合中。這使得布隆過濾器在查找元素是否存在時非常高效，尤其適用于大規(guī)模數(shù)據(jù)集和資源有限的環(huán)境。
還需要注意的是，哈希參數(shù)當(dāng)然是越多誤判率越低，但是面臨的問題就是內(nèi)存也會越來越大，所以我們需要找到最合適的哈希函數(shù)個數(shù)，關(guān)于這一點，我們可以參考知乎大佬的一篇文章
知乎大佬文章鏈接
具體總結(jié)為
3. 布隆過濾器的查找
布隆過濾器的思想是將一個元素用多個哈希函數(shù)映射到一個位圖中，因此被映射到的位置的比特位一定為1。所以可以按照以下方式進(jìn)行查找：分別計算每個哈希值對應(yīng)的比特位置存儲的是否為零，只要有一個為零，代表該元素一定不在哈希表中，否則可能在哈希表中
注意：布隆過濾器如果說某個元素不存在時，該元素一定不存在，如果該元素存在時，該元素可能存在，因為有些哈希函數(shù)存在一定的誤判
比如：在布隆過濾器中查找"alibaba"時，假設(shè)3個哈希函數(shù)計算的哈希值為：1、3、7，剛好和其他元素的比特位重疊，此時布隆過濾器告訴該元素存在，但實該元素是不存在的，存在可能存在誤判，但是不存在不會存在誤判
4. 布隆過濾器的刪除
布隆過濾器不能直接支持刪除工作，因為在刪除一個元素時，可能會影響其他元素
比如：刪除其中一個元素，如果直接將該元素所對應(yīng)的二進(jìn)制比特位置0，另一元素也被刪除了，因為這兩個元素在多個哈希函數(shù)計算出的比特位上剛好有重疊
一種支持刪除的方法：將布隆過濾器中的每個比特位擴(kuò)展成一個小的計數(shù)器，插入元素時給k個計數(shù)器(k個哈希函數(shù)計算出的哈希地址)加一，刪除元素時，給k個計數(shù)器減一，通過多占用幾倍存儲空間的代價來增加刪除操作
5. 布隆過濾器的實現(xiàn)
在這里我們先實現(xiàn)3個哈希函數(shù)
struct HashBKDR
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
struct HashAP
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashDJB
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
-
BKDR哈希函數(shù) (Bentley and Sedgewick, 1997)：
- BKDR哈希函數(shù)使用一個常數(shù)因子131，以及遍歷字符串中的字符。
- 對于每個字符，它將當(dāng)前哈希值乘以131，然后加上字符的ASCII碼值。
- 最終，它返回計算得到的哈希值。
-
AP哈希函數(shù) (Arjen Lenstra and Endre Szemerédi’s hash function)：
- AP哈希函數(shù)使用一系列位運(yùn)算和異或操作來處理字符串中的字符。
- 對于每個字符，它會根據(jù)字符的位置（奇數(shù)或偶數(shù)）應(yīng)用不同的位運(yùn)算操作。
- 最終，它返回計算得到的哈希值。
-
DJB哈希函數(shù) (Daniel J. Bernstein, 1991)：
- DJB哈希函數(shù)使用一個初始哈希值5381，以及遍歷字符串中的字符。
- 對于每個字符，它將當(dāng)前哈希值左移5位，然后加上字符的ASCII碼值。
- 最終，它返回計算得到的哈希值。
布隆過濾器代碼
// N表示準(zhǔn)備要映射N個值
template<size_t N,
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;
_bits->set(hash1);
size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;
_bits->set(hash2);
size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;
_bits->set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;
if (!_bits->test(hash1))
return false; // 準(zhǔn)確的
size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;
if (!_bits->test(hash2))
return false; // 準(zhǔn)確的
size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;
if (!_bits->test(hash3))
return false; // 準(zhǔn)確的
return true; // 可能存在誤判
}
private:
const static size_t _ratio = 5;
std::bitset<_ratio*N>* _bits = new std::bitset<_ratio*N>;
};
-
Set(const K& key)：
-
Set方法用于將元素插入布隆過濾器中。 - 它分別使用三個哈希函數(shù)將元素映射到位數(shù)組中的三個位置，然后將這三個位置的位設(shè)置為1。
- 這樣，插入操作將三次設(shè)置位操作，將元素標(biāo)記為存在于布隆過濾器中。
-
-
Test(const K& key)：
-
Test方法用于測試元素是否存在于布隆過濾器中。 - 與插入相似，它使用三個哈希函數(shù)將元素映射到三個位數(shù)組位置，并檢查這三個位置的位是否都為1。
- 如果有一個位置的位為0，說明元素不在布隆過濾器中，返回
false。 - 如果三個位置的位都為1，可能存在誤判，返回
true。
-
這個布隆過濾器可以用于在快速查找集合中的元素是否存在，但需要注意，它存在誤判的可能性，即可能會將不在集合中的元素判斷為存在。_ratio 在這個布隆過濾器實現(xiàn)中是一個倍數(shù)，它決定了位數(shù)組的大小。位數(shù)組的大小是 _ratio * N，其中 N 表示準(zhǔn)備要映射的值的數(shù)量。具體來說，這個倍數(shù) _ratio 用于控制位數(shù)組的大小以平衡誤判率和內(nèi)存使用。增加 _ratio 會增加位數(shù)組的大小，從而減小誤判率，但也會增加內(nèi)存占用。減小 _ratio 會減小位數(shù)組的大小，降低內(nèi)存占用，但也會增加誤判率。
6. 布隆過濾器優(yōu)點
- 增加和查詢元素的時間復(fù)雜度為:O(K), (K為哈希函數(shù)的個數(shù)，一般比較小)，與數(shù)據(jù)量大小無關(guān)
- 哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運(yùn)算
- 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴(yán)格的場合有很大優(yōu)勢
- 在能夠承受一定的誤判時，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢
- 數(shù)據(jù)量很大時，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能
- 使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運(yùn)算
7. 布隆過濾器缺陷
- 有誤判率，即存在假陽性(False Position)，即不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法：再建立一個白名單，存儲可能會誤判的數(shù)據(jù))
- 不能獲取元素本身
- 一般情況下不能從布隆過濾器中刪除元素
- 如果采用計數(shù)方式刪除，可能會存在計數(shù)回繞問題
8. 布隆過濾器的應(yīng)用
給一個超過100G大小的log file, log中存著IP地址, 設(shè)計算法找到出現(xiàn)次數(shù)最多的IP地址？與上題條件相同，如何找到top K的IP？如何直接用Linux系統(tǒng)命令實現(xiàn)？
使用布隆過濾器和哈希切割
- 建立布隆過濾器：首先，創(chuàng)建一個合適大小的布隆過濾器。布隆過濾器的位數(shù)組大小需要足夠大，以容納所有可能的IP地址。
- 遍歷日志文件：逐行遍歷日志文件，提取每行中的IP地址。
-
哈希切割：對每個提取的IP地址應(yīng)用一種哈希函數(shù)來將其映射到布隆過濾器的位數(shù)組上。這可以使用布隆過濾器的
Set方法來實現(xiàn)。 - 統(tǒng)計次數(shù)：同時，維護(hù)一個哈希表，其中鍵是IP地址，值是出現(xiàn)的次數(shù)。在哈希切割過程中，檢查IP是否已存在于表中，如果存在，則增加其出現(xiàn)次數(shù)。
- 查詢次數(shù)最多的IP：在遍歷完整個日志文件后，您可以遍歷字典，找到出現(xiàn)次數(shù)最多的IP地址。
- 查詢top K的IP：要找到top K的IP地址，可以對字典按照出現(xiàn)次數(shù)進(jìn)行排序，然后選擇前K個IP地址。
使用Linux系統(tǒng)命令
Linux系統(tǒng)提供了一些強(qiáng)大的命令行工具來處理文本文件，可以使用這些工具來解決問題：
- 使用
awk命令或grep命令提取日志文件中的IP地址。- 使用
sort命令對提取的IP地址進(jìn)行排序。- 使用
uniq -c命令統(tǒng)計IP地址的出現(xiàn)次數(shù)。- 使用
sort -nr命令按出現(xiàn)次數(shù)對IP地址進(jìn)行逆序排序。- 使用
head命令來獲取top K的IP地址。
示例命令行操作：
cat log_file.log | grep -oE "\b([0-9]{1,3}\.){3}[0-9]{1,3}\b" | sort | uniq -c | sort -nr | head -n K
這將列出出現(xiàn)次數(shù)最多的top K個IP地址。
無論使用哪種方法，都需要根據(jù)實際需求和性能要求來選擇。使用布隆過濾器和哈希切割的方法可能需要編寫自定義代碼，但可以處理非常大的數(shù)據(jù)集。使用Linux系統(tǒng)命令則更加簡單，但可能受限于系統(tǒng)資源和性能。
給兩個文件，分別有100億個query，我們只有1G內(nèi)存，如何找到兩個文件交集？分別給出精確算法和近似算法
在這種情況下，由于內(nèi)存有限，需要使用外部排序（external sorting）技術(shù)來處理這兩個大型文件并找到它們的交集。外部排序是一種適用于大規(guī)模數(shù)據(jù)集的算法，其中數(shù)據(jù)無法完全加載到內(nèi)存中。
精確算法：
- 分別對兩個文件進(jìn)行外部排序：首先，將兩個文件分別劃分為多個小文件塊，每個小文件塊可以適應(yīng)內(nèi)存的大小。然后，對每個小文件塊進(jìn)行內(nèi)部排序，以確保每個塊內(nèi)的數(shù)據(jù)是有序的。
- 合并排序的塊：對于每個文件，使用歸并排序等合并算法，逐個合并排序后的小塊，以創(chuàng)建一個完全有序的大文件。
- 查找交集：一旦兩個文件都有序，可以使用合并算法來查找它們的交集。比較兩個文件中的元素，將相同的元素輸出到結(jié)果文件中。
這是一個精確的算法，它可以找到確切的交集，但需要大量的磁盤I/O和計算時間，因為數(shù)據(jù)需要多次讀取和寫入磁盤。
近似算法： 在內(nèi)存有限的情況下，使用布隆過濾器可以實現(xiàn)近似的交集查找。以下是近似算法的步驟：
- 構(gòu)建兩個布隆過濾器：對于每個文件，構(gòu)建一個布隆過濾器。這需要一小部分內(nèi)存。在構(gòu)建布隆過濾器時，需要選擇合適的哈希函數(shù)和位數(shù)組大小，以平衡內(nèi)存使用和誤判率。
- 查詢交集：對于第一個文件的每個查詢，檢查是否在第二個布隆過濾器中。如果布隆過濾器中存在該查詢，將其添加到結(jié)果集中。
- 結(jié)果集：結(jié)果集中包含兩個文件的近似交集。
近似算法的主要優(yōu)點是節(jié)省了內(nèi)存，但它會引入誤判。如果某個查詢在第一個布隆過濾器中存在，但實際上不存在于第二個文件中，它仍然會出現(xiàn)在結(jié)果集中。誤判率取決于布隆過濾器的參數(shù)選擇。
無論使用哪種算法，都需要在性能和準(zhǔn)確性之間做權(quán)衡。精確算法提供準(zhǔn)確的結(jié)果，但需要更多的時間和資源。近似算法可以在有限內(nèi)存下快速處理，但可能會引入一定程度的誤判。
如何擴(kuò)展BloomFilter使得它支持刪除元素的操作
Bloom過濾器是一種概率數(shù)據(jù)結(jié)構(gòu)，通常不支持元素的刪除操作。要擴(kuò)展Bloom過濾器以支持元素的刪除，可以考慮使用一些額外的技巧。以下是一種可能的方法：
使用計數(shù)型Bloom過濾器
一種支持刪除操作的變體是計數(shù)型Bloom過濾器（Counting Bloom Filter）。與標(biāo)準(zhǔn)Bloom過濾器不同，計數(shù)型Bloom過濾器中的每個位不是簡單的0或1，而是一個計數(shù)器。計數(shù)器可以表示一個元素被插入的次數(shù)。
以下是如何擴(kuò)展Bloom過濾器以支持刪除元素的步驟：
- 初始化計數(shù)型Bloom過濾器：創(chuàng)建一個計數(shù)型Bloom過濾器，其中每個位都初始化為0。計數(shù)型Bloom過濾器的大小通常與標(biāo)準(zhǔn)Bloom過濾器相同。
- 插入元素：當(dāng)要插入元素時，不再將相應(yīng)的位設(shè)置為1，而是增加相應(yīng)的計數(shù)器。每次插入操作會增加計數(shù)器的值。
- 查詢元素：在查詢操作中，檢查計數(shù)器是否大于零。如果計數(shù)器大于零，則表示元素存在。這是因為每次插入操作都會增加計數(shù)器的值。
- 刪除元素：要刪除元素，可以遞減相應(yīng)的計數(shù)器。如果計數(shù)器變?yōu)榱?，元素就被?biāo)記為不存在。
注意：在計數(shù)型Bloom過濾器中，可能存在溢出問題。因此，在刪除元素時，需要小心確保計數(shù)器不會變?yōu)樨?fù)數(shù)。
這種方法允許支持刪除操作，但會占用更多的內(nèi)存。計數(shù)型Bloom過濾器在需要跟蹤元素出現(xiàn)次數(shù)的應(yīng)用中非常有用，但仍然需要注意誤判和溢出問題文章來源：http://www.zghlxwxcb.cn/news/detail-713252.html
另請注意，標(biāo)準(zhǔn)Bloom過濾器無法實現(xiàn)可靠的刪除操作，因為刪除一個元素可能會影響其他元素的位狀態(tài)，從而導(dǎo)致不可預(yù)測的行為。計數(shù)型Bloom過濾器是一種可以處理刪除操作的變體，但它需要更多的內(nèi)存和計算資源。
示一個元素被插入的次數(shù)。
以下是如何擴(kuò)展Bloom過濾器以支持刪除元素的步驟：
- 初始化計數(shù)型Bloom過濾器：創(chuàng)建一個計數(shù)型Bloom過濾器，其中每個位都初始化為0。計數(shù)型Bloom過濾器的大小通常與標(biāo)準(zhǔn)Bloom過濾器相同。
- 插入元素：當(dāng)要插入元素時，不再將相應(yīng)的位設(shè)置為1，而是增加相應(yīng)的計數(shù)器。每次插入操作會增加計數(shù)器的值。
- 查詢元素：在查詢操作中，檢查計數(shù)器是否大于零。如果計數(shù)器大于零，則表示元素存在。這是因為每次插入操作都會增加計數(shù)器的值。
- 刪除元素：要刪除元素，可以遞減相應(yīng)的計數(shù)器。如果計數(shù)器變?yōu)榱?，元素就被?biāo)記為不存在。
注意：在計數(shù)型Bloom過濾器中，可能存在溢出問題。因此，在刪除元素時，需要小心確保計數(shù)器不會變?yōu)樨?fù)數(shù)。
這種方法允許支持刪除操作，但會占用更多的內(nèi)存。計數(shù)型Bloom過濾器在需要跟蹤元素出現(xiàn)次數(shù)的應(yīng)用中非常有用，但仍然需要注意誤判和溢出問題
另請注意，標(biāo)準(zhǔn)Bloom過濾器無法實現(xiàn)可靠的刪除操作，因為刪除一個元素可能會影響其他元素的位狀態(tài)，從而導(dǎo)致不可預(yù)測的行為。計數(shù)型Bloom過濾器是一種可以處理刪除操作的變體，但它需要更多的內(nèi)存和計算資源。文章來源地址http://www.zghlxwxcb.cn/news/detail-713252.html
到了這里，關(guān)于哈希的應(yīng)用--位圖和布隆過濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]哈希應(yīng)用之位圖&布隆過濾器](https://imgs.yssmx.com/Uploads/2024/04/852662-1.gif)
