數據結構之位圖和布隆過濾器

系列文章目錄

數據結構之ArrayList_arraylist o(1) o(n)-CSDN博客

數據結構之LinkedList-CSDN博客

數據結構之棧_棧有什么方法-CSDN博客

數據結構之隊列-CSDN博客

數據結構之二叉樹-CSDN博客

數據結構之優先級隊列-CSDN博客

常見的排序方法-CSDN博客

數據結構之Map和Set-CSDN博客

數據結構之二叉平衡樹-CSDN博客

系列文章目錄

前言

一、位圖

1. 位圖的概念

2. 位圖的模擬實現

3. 位圖的應用

二、布隆過濾器

1. 布隆過濾器的概念

2. 布隆過濾器的模擬實現

3. 布隆過濾器誤判

4. 布隆過濾器和哈希表對比

5. 布隆過濾器的應用

三、海量數據問題的解決思路

問題 1：

問題 2：

問題 3：

問題 4：?

問題 5：

問題 6：

四、一致性哈希

1. 普通的哈希算法

2. 一致性哈希算法

五、哈希與加密

前言

本文介紹了兩種高效處理海量數據的數據結構：位圖和布隆過濾器。位圖通過二進制位存儲狀態，適合整數查詢，40億數據僅需500M空間。布隆過濾器擴展到位圖存儲字符串，通過多個哈希函數減少沖突，但存在誤判可能。文章還討論了海量數據問題的解決思路，包括哈希切割、雙位圖統計等，并對比了一致性哈希與普通哈希的區別。最后區分了哈希算法（不可逆）與加密算法（可逆）的特性。這些數據結構和技術特別適用于需要高效查詢和節省內存的大數據場景。

一、位圖

1. 位圖的概念

位圖是利用某個位存放某種狀態的數據結構，例如可以用一個字節中的 8 個位，用來表示 0 ~ 7 這 8 個數字是否存在，如果第 i 位是 1，表示 i 存在，是 0 表示不存在；

2. 位圖的模擬實現

elem 定義一個 byte[] 數組，用來存放某個數字是否在位圖中存在；

usedSize 表示存放數字的個數；

MyBitSet() 構造方法，默認開辟的空間為 1 個字節；

set(int val): void 將 val 存放到位圖中；

思路：將位圖中的第 val 個位置 1;

定義 byteIndex 表示第幾個字節，bitIndex 表示第幾個位；例如存放數字 12 到位圖中，就需要將第 1 字節的第 4 位置 1；

存放數據是要注意是否存滿，滿了存放之前要擴容；存放完成后，usedSize++；

get(int val): boolean 表示 val 是否在位圖中存在，存在返回 true，不存在返回 false；

reset(int val): void 將 val 在位圖中刪除，刪除完成后 usedSize--；

getUsedSize()：返回存放元素的個數；

public class MyBitSet {public byte[] elem;private int usedSize;public MyBitSet(){this.elem = new byte[1];}public MyBitSet(int n){this.elem = new byte[n / 8 + 1];}public void set(int val){if(val < 0){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;if(byteIndex >= this.elem.length){this.elem = Arrays.copyOf(this.elem, byteIndex + 1);}this.elem[byteIndex] |= (1 << bitIndex);this.usedSize++;}public boolean get(int val){if(val < 0 || val / 8 >= this.elem.length){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;if(((this.elem[byteIndex] >> bitIndex) & 1) == 1){return true;}return false;}public void reset(int val){if(val < 0 || val / 8 >= this.elem.length){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;this.elem[byteIndex] &= ~(1 << bitIndex);this.usedSize--;}public int getUsedSize(){return this.usedSize;}
}

3. 位圖的應用

位圖適合海量數據的查詢：

假設有 40 億個不重復的整數，并且沒有進行過排序，如何判斷某個數是否在這 40 億個數中？

通常使用遍歷一遍進行查找的時間復雜度是 O(N)；使用排序加二分的查找方式，時間復雜度是 O(N*logN) + O(logN)；

如果使用位圖，將這 40 億個整數都放在位圖當中，查詢某個整數的時間復雜度只是 O(1)，因為只需要判斷該整數對應的位是否被置 1 即可；

位圖的優勢：存放 40 億個整數大于需要 16G，通常來說內存是存不下的，如果使用位圖，500M就能存下，因此位圖更適用于海量數據的查詢；

位圖的缺點：位圖只能存放整數，適用于數據無重復的場景；

二、布隆過濾器

1. 布隆過濾器的概念

布隆過濾器利用哈希函數，可以將字符串轉化為某個整數，再存放在位圖里，解決了位圖不能存放字符串的問題，更適合實際應用；它是一種緊湊的，概率型數據結構，可以進行高效的插入和查詢；

2. 布隆過濾器的模擬實現

DEFAULT_SIZE 默認開辟空間的大小；

bitSet 位圖，用于存放通過哈希函數生成的整數；

usedSize 存放元素的個數；

seeds 隨機種子，用于不同的哈希函數生成不同的哈希算法；

simpleHashes 簡單的哈希函數；

MyBloomFilter() 構造方法，定義一個布隆過濾器，開辟默認大小的空間，生成多個不同的哈希函數；

add(String val): void 在布隆過濾器中存放元素；

思路：針對同一個字符串，利用不同的哈希函數，生成多個不同的整數，都存放再位圖當中；

contains(String val): boolean 判斷布隆過濾器中是否包含 val，包含返回 true，不包含返回 false；

思路：對同一個字符串，利用不同的哈希函數，生成多個不同的整數，在位圖中檢查這些整數對應的位是否被置 1；

public class MyBloomFilter {public static final int DEFAULT_SIZE = 1 << 20;// 位圖public BitSet bitSet;public int usedSize;public static final int[] seeds = {5, 7, 11, 13, 27, 33};public SimpleHash[] simpleHashes;public MyBloomFilter(){bitSet = new BitSet(DEFAULT_SIZE);simpleHashes = new SimpleHash[seeds.length];for(int i = 0; i < seeds.length; i++){simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);}}public void add(String val){for(int i = 0; i < simpleHashes.length; i++){int index = simpleHashes[i].hash(val);bitSet.set(index);}this.usedSize++;}public boolean contains(String val){for(int i = 0; i < simpleHashes.length; i++){int index = simpleHashes[i].hash(val);if(!bitSet.get(index)) return false;}return true;}
}class SimpleHash{public int cap;public int seed;public SimpleHash(int cap, int seed){this.cap = cap;this.seed = seed;}public int hash(String key){int h;// (n - 1) & hashreturn (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));}
}

3. 布隆過濾器誤判

布隆過濾器中存在多個哈希函數，但仍然會有一定的概率多個哈希函數針對不同的字符串 s1 和 s2計算出了相同的哈希值，如果容器里面存放了 s1，進行查詢的時候就會誤以為也存了 s2；

因此布隆過濾器確定某個元素不存在時，該元素一定不存在；確定某個元素存在時，該元素只是可能存在，并不一定存在，因為會存在誤判的情況；

4. 布隆過濾器和哈希表對比

哈希表查詢速度很快，但是對空間的利用率并不高，通常只有 50%；當在海量數據的應用場景下，哈希表存儲效率的問題就會顯現出來；

而布隆過濾器使用哈希加位圖的思想，通過不同的哈希函數，計算出不同對象的哈希值，在位圖當中存儲，既解決了哈希表空間利用率低的問題，又保證了查詢效率，但是它會存在誤判的情況，在準確性方面是不如哈希表的。

5. 布隆過濾器的應用

布隆過濾器是在哈希和位圖的基礎上實現的，因此布隆過濾器也適用于海量數據的查詢，并且占用的內存較小；

布隆過濾器的優點：

查詢元素的時間復雜度為 O(k)，k 為哈希函數的個數；
哈希函數之間沒有關系，方便硬件并行運算；
布隆過濾器不需要存儲元素本身，在對保密要求比較嚴格的場合有很大優勢；
在能夠承受一定的誤判率時，布隆過濾器比其他的數據結構有很大的空間優勢；

布隆過濾器的缺點：

布隆過濾器會存在誤判的情況，因為哈希函數針對不同的字符串有可能計算出相同的哈希值，即哈希沖突；
布隆過濾器不能獲取元素本身；
一般情況不能從布隆過濾器中刪除元素；

google 的 guava 包中有對布隆過濾器的實現；

布隆過濾器可用于網頁爬蟲時，對 URL 進行去重，避免重復爬相同的 URL；

垃圾郵件過濾，可以從十幾億個垃圾郵件地址判斷某郵箱是否是垃圾郵箱；

三、海量數據問題的解決思路

問題 1：

假設有一個超過 100G 大小的 log file，log 中存放這 IP地址，如何找到出現次數最多的 IP 地址，及如何找到出現頻率前 k 的IP地址？?

解法一：哈希表

如果不考慮占用空間的大小，可以使用哈希表來統計每一個 IP 的數量，找到出現次數最多的即可；

解法二：哈希切割

但 100G 的數據是無法一次性加載到內存當中，需要將 100G 的數據分割成若干個小文件；分別統計每一個文件中出現次數最多的 IP 地址及次數,找出出現次數前 k 個 IP 地址即可；

注意：分割不能采用均分方式，因為一個小文件中出現最多次數的?IP 不一定是所有 IP 中出現次數最多的IP；

分割文件采用哈希切割的方式，即對不同的 IP 計算哈希值，哈希值相同的 IP 存放到一個文件當中，讀取每一個文件，統計每個 IP 出現的次數，找到前 k 個即可；

問題 2：

給定 100 億個整數，設計算法找到其中只出現一次的數字；

解法一：哈希切割

使用哈希切割的方式，分成若干個小文件，計算所有數字的哈希值，將具有相同哈希值的數字放到一個文件中，讀取每一個文件，找到只出現一次的數字；

解法二：兩個位圖

使用兩個位圖 bitSet1 和 bitSet2，遍歷 100 億整數：

出現一次就將 bitSet1 中的對應位置 1；

出現兩次則將 bitSet2 中的對應位置 1，bitSet1 中的對應位置 0；

出現三次或者三次以上，就將 bitSet1 和 bitSet2 中的對應位都置 1；

遍歷位圖，找到只出現一次的數字。

解法三：一個位圖

使用位圖中連續的兩個位來表示出現的次數，00 表示沒出現，01 表示出現一次，10 表示出現兩次，11 表示出現三次及三次以上；

遍歷位圖，找到出現一次的整數；

在位圖中存放時：

字節序號：byteIndex = val / 4；位序號：bitIndex = （val % 4）* 2；

問題 3：

給兩個文件，每個文件有 100 億個整數，只有 1G 內存，如何找到兩個文件的交集？

解法一：哈希切割

遍歷第一個文件，將所有的整數都通過哈希計算，具有相同哈希值的數字，都放到一個文件當中，形成若干個小文件，用 A[i] 表示；

遍歷第二個文件，將所有的整數都通過哈希計算，具有相同哈希值的數字，都放到一個文件當中，形成若干個小文件，用 B[i] 表示；

將 A[i] 和 B[i] 緩存到內存中，找到相同的數字，都存放到結果文件中；

最終遍歷完所有的小文件，得到的就是結果文件就是交集；?

解法二：位圖

創建一個位圖 bitSet，遍歷第一個文件，將第一個文件的整數都放到 bitSet 中；

遍歷第二個文件，并在 bitSet 中查找，找到的所有數據就是兩個文件的交集；

衍生問題：如果求上述問題中數據的并集和差集？

創建一個位圖 bitSet1，遍歷第一個文件，將第一個文件的所有的數字都放到 bitSet1 中；

創建一個位圖 bitSet2，遍歷第二個文件，將第二個文件的所有的數字都放到 bitSet2 中；

遍歷位圖，將第一個位圖和第二個位圖的每一位進行按位或操作，得到的新的位圖 bitSet3；

遍歷 bitSet3，將位圖中的數字都存到新的文件當中，新的文件就是并集；

如果進行按位與操作，得到的數據就是交集；

如果進行按位異或操作，得到的數據就是差集；

問題 4：?

一個文件有 100 億個整數，現有 1G 內存，設計算法找到出現不超過兩次的所有整數；

解法一：哈希切割

遍歷文件，將所有的整數都通過哈希計算，具有相同哈希值的數字，都放到一個文件當中，形成若干個小文件；

遍歷每一個小文件，統計所有數字的出現次數，找出出現次數不超過兩次的整數；

解法二：兩個位圖

創建兩個位圖 bitSet1 和 bitSet2：

出現一次就將 bitSet1 中的對應位置 1；

出現兩次則將 bitSet2 中的對應位置 1，bitSet1 中的對應位置 0；

出現三次或者三次以上，就將 bitSet1 和 bitSet2 中的對應位都置 1；

遍歷位圖，找到只出現一次和出現兩次的數字。

問題 5：

給兩個文件，分別有 100 億個?query，我們只有 1G 內存，如何找到兩個文件的交集，分別給出精確算法和近似算法；

精確算法：哈希切割

遍歷第一個文件，使用哈希函數計算每一個 query 對應的哈希值，相同哈希值的 query 放到同一個文件中，形成若干個小文件 A[i]；

遍歷第二個文件，使用哈希函數計算每一個 query 對應的哈希值，相同哈希值的 query 放到同一個文件中，形成若干個小文件 B[i]；

分別求 A[i] 和 B[i] 的交集，得到所有的交集的并集就是兩個大文件的交集；

近似算法：布隆過濾器

遍歷第一個文件，將所有的 query 都映射到布隆過濾器中，讀取第二個文件，去布隆過濾器中查找，得到的所有 query 就是交集，但有可能會出現誤判；

問題 6：

如何擴展布隆過濾器，使它能夠支持刪除操作？

將布隆過濾器的每個位都擴展成一個小的計數器，插入元素時給 k 個計數器加 1，刪除元素時給每個計數器減 1；

但是當哈希沖突多了，計數器有可能溢出；

四、一致性哈希

1. 普通的哈希算法

假設有一張圖片需要緩存到服務器上，如果有三臺服務器，通過哈希函數求到圖片對應的哈希值，哈希值 % 3 就找到了對應的服務器，將圖片緩存即可。“哈希值?% 服務器數量”的這種算法，就是普通的哈希算法；

普通哈希算法的缺陷：

如果新增服務器，或者某臺服務器損壞，服務器的數量就會發生改變；

如果哈希函數不變，同一張圖片算出來的哈希值就會改變，那么所有的緩存就會失效，造成緩存的雪崩；

應用獲取不到這些圖片，就會向后端發送請求，大量的請求會帶給服務器巨大的壓力，有可能導致服務器宕機。

2. 一致性哈希算法

一致性哈希算法：使用服務器的 IP 或者編號，主機名等?% 2^32；

一致性哈希算法將整個哈希值空間按照順時針方向組織成一個虛擬的圓環，稱為 Hash 環；

將各個主機使用哈希函數進行哈希，確定主機在哈希環上的位置；

將圖片使用同樣的哈希函數進行哈希，確定圖片在哈希環上的位置；因為圖片不一定正好和主機在同一個位置，因此需要將圖片存到它順時針旋轉遇到的第一臺服務器；

優點：即使出現服務器宕機，也會只有一部分圖片需要緩存到下一臺服務器，不會出現大量緩存雪崩；也不會向后端發送大量的請求，帶給服務器巨大壓力；

缺點：如果哈希環出現傾斜（服務器分布不均勻），大部分數據緩存在某一臺服務器上，可能導致這臺服務器宕機，之后所有圖片再緩存到下一臺服務器，再造成下一臺服務器宕機，最終會導致服務器集群宕機；

解決方法：使用服務器虛擬節點，每個服務器創建多個虛擬節點，均勻分布在哈希環上，這樣圖片緩存就會均勻分布在多態服務器上；

五、哈希與加密

哈希算法往往設計成輸出相同長度的哈希值，例如 MD5 算法，是不可逆的；

加密算法輸出的加密數據往往和輸入數據的長度成正比，不一定都是長度相同的，是可逆的；