❶ 大數據和空間限制
網頁黑名單系統、垃圾郵件過濾系統、爬蟲網址判重系統，且系統容忍一定程度的失誤率，但是對空間要求比較嚴格，這種問題一般考慮 布隆過濾器 。布隆過濾器想做到完全正確是不可能的，其優勢在於使用很少的空間可以將准確度做到很高的程度。
哈希函數（散列函數） ：輸入域可以是非常大的范圍，但是輸出域是固定的范圍。性質如下：1.無限輸入域；2.傳入相同輸入值時，返回值一樣；3.傳入不同輸入值時，返回值可能一樣也可能不一樣。4.返回值均勻分布
第四點性質是評價哈希函數優劣的關鍵，不同的輸入值所得到的返回值均勻地分布在輸出域上，哈希函數就越優秀，並且這種均勻分布與輸入值出現的規律無關。
布隆過濾器 ：一個長為m的bit數組，每個位置只佔一個bit，假設一共有k個哈希函數，這些函數的輸出域都大於等於m。對一個輸入對象，經過k個哈希函數算出結果，每個結果對m取余，然後在bit array上把相應的位置塗黑。檢查一個對象是否是之前的某一個輸入對象，就檢查相應位置是否是黑的，如果有一個不是黑的，則該輸入一定不在集合里。如果都是黑的，說明在集合中，但是可能誤判。如果bit map的大小m相比輸入對象的個數n過小，失誤率會變大。假設輸入個數為n，失誤率為p，則bit map的大小由以下公式確定：
哈希函數的個數由以下公式決定：
因為在確定布隆過濾器大小的過程中選擇了上下取整，所以還要用如下公式確定布隆過濾器真實失誤率：
【題目】有一個包含 20億個全是32位整數的大文件，在其中找到出現次數最多的數
【要求】內存限制為2GB
【解答】想要在很多整數中找到出現次數最多的數，通常的做法是使用哈希表對出現的每一個數做詞頻統計。但是一次性用哈希表統計20億個數的辦法很可能導致內存不夠。解決辦法是把包含20億個數的大文件用哈希函數分成16個小文件，根據哈希函數的性質，同一種數不可能被散列到不同的小文件上，同時每個小文件中不同的數一定不回大於2億種。對每一個小文件用哈希表來統計其中每種數出現的次數，就得到了16個小文件種各自出現次數最多的數，還有各自的次數統計，接下來比較他們就好了。
把一個大的集合通過哈希函數分配到多台機器中，或者分配到多個文件里，這種技巧是處理大數據面試題最常用的技巧之一。
【題目】32位無符號整數的范圍是0~4294967295，現在有一個正好包含40億個無符號整數的文件，可以使用最多1GB的內存，找出所有未出現過的數。
【解答】如果用哈希表的話需要佔用很多空間，所以申請一個長度為4294976295的bitarray，遍歷這40億個數，把對應位置塗黑，然後再遍歷bitarr，哪個位置不是黑的就沒出現
【進階】內存限制為10MB，但是只用找到一個沒出現過的數即可
【解答】先將0~4294967295分為64個區間，遍歷一次分別統計每個區間內的個數，找到某個區間個數少於67108864，這個區間一定有沒出現過的數，再遍歷一次，利用長度為67108864的bit arr，這佔用大約8MB的空間，然後按照上面的方法即可。
【題目】有一個包含100億個URL的大文件，假設每個URL佔用64B，請找出其中所有重復的URL。
【解答】把大文件通過哈希函數分配到機器，或者通過哈希函數把大文件拆成小文件，一直進行這種劃分，直到劃分的結果滿足資源限制的要求。
【補充問題】某搜索公司一天的用戶搜索詞彙是海量的（百億數據量），請設計一種求出每天熱門top100詞彙的可行辦法
【解答】還是用哈希分流的思路來處理，把包含百億數據量的詞彙文件分流到不同的機器上，處理每一個小文件的時候，通過哈希表統計每種詞及其詞頻，哈希表記錄建立完成後，再遍歷哈希表，遍歷哈希表的過程中使用大小為100的小根堆來選出每一個小文件的top100，然後把各個維簡排序後的top100進行外排序或者繼續利用小根堆，就可以選出每台機器上的top100，然後繼續。。。
【題目】32位無符號整數的范圍是0~4294967295，現在有40億個無符號整數，可以使用最多1GB的內存，找出所有出現了兩次的數。
【解答】用bitarr的方式來表示數出現的情況，即申請一個長度為4294967295*2的數組，用兩個位置表示一個數出現的詞頻，第一次設為01，第二次設為10，第三次及以上設為11，然後統計10的個數
【補充問題】可以使用最多10MB的內存，怎麼找到這40億個整數的中位數
【解答】用分區間的方式處理，長度為2M的無符號整型數組佔用的空間為8MB，向上取整2148個區間，累加每個區間的出現次數，就可以找到40億個數的中位數到底落在哪個區間上
如果用伺服器集群來設計和實現數據緩存時，一種方法是，先將id通過哈希函數轉換成一個哈希值，記為key，如果機器有N台，則計算key%N的值，這個值就是該數據所屬的機器編號。這種方法的潛在問題是如果增刪機器，即N變化，代價會很高，所有數據都不得不根據id重新計算一遍哈希值，將哈希值對新的機器數進行取模操作，然後進行大規模的數據遷移。
為了解決這一為題，引入 一致性哈希演算法 。數據id通過哈希函數轉換成的哈希值頭尾相連，想像成一個閉合的環形，一個數據id在計算出哈希值後認為對應到環中的一個位置。然後將每台機器根據機器id算出來的哈希值確定機器在環中的位置。如何確定一條數據歸屬哪條機器？把數據id用哈希函數算出哈希值，映射到環中相應的位置，順時針找到離這個位置最近的機器，那台機器就是數據的歸屬。這樣增刪機器時的代價就較小。
為解決機器負載不均的問題，引入虛擬節點機制，即對每一台機器通過不同的哈希函數計算出多個哈希值，對多個位置都放置一個服務節點，稱為虛擬節點。具體做法可以在機器ip地址或主機名的後面增加編號或埠號來實現。