溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
空間換算：
1 Byte = 8 Bits 1 KB = 1024 Bytes 1 MB = 1024 KB 1 GB = 1024 MB
2^2 = 4;
2^4 = 16;
2^8 = 256;
2^10 = 1024;
2^16 = 65 536
2^20 = 1 048 576
2^32 = 4 294 967 296
基本方法
1. hash法
Hash一般被稱為散列，它是以一種映射關系，即給定一個數據元素，其關鍵字為key，按一個確定的散列函數計算出hash(key)，把hash(key)作為關鍵字key對應元素的存儲地址（或稱散列地址），再進行數據元素的插入和檢索操作。簡而言之，散列函數就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
散列表是具有固定大小的數組，其中，表長應該為質數。散列函數是用于關鍵字與存儲地址之間的一種映射關系，但是，不能保證每個元素的關鍵字與函數值是一一對應的，因為極有可能出現對應于不同的元素，卻計算出相同的函數值，這就是哈希沖突。
1.1 常用散列函數的構建方法：
1.1.1 直接尋址法
h(key) = key 或者 h(key) = a * key + b;
1.1.2 取模法
h(key) = key mod p;
1.1.3 數字分析法
1.1.4 折疊法
1.1.5 平方取中法
1.1.6 保留余數法
h(key) = key % p;
1.1.7 隨機數法
h(key) = random(key);
1.2 常用的解決沖突辦法
1.2.1 開放地址法
當發生地址沖突時，在散列表中再按照某種方法繼續探測其他的存儲地址，知道找到空閑的地址為止。
1.2.2 鏈地址法
1.2.3 再散列法
當發生沖突時，使用第二個、第三個...散列函數計算地址，直到無沖突為止。時間消耗會增加。
1.2.4 建立一個公共溢出區
優缺點：
Hash主要是用來進行“快速存取”，在O(1)時間復雜度里就可以查找到目標元素，或者判斷其是否存在。Hash數據結構里的數據對外是雜亂無序的，因此其具體存儲位置及各個存儲元素位置之間的相互關系是無法得知的，但是卻可以在常數時間里判斷元素位置及存在與否。在處理海量數據的過程中，使用Hash方法一般可以快速存取、統計某些數據，將大量數據進行分類，例如提取某日訪問網站次數最多的IP地址等。
2. Bit-map法
bit-map(位圖)法的基本原理是使用位數組來表示某些元素是否存在。
bit-map法的結果是生成一個N位長的串，每位上以“1”或“0”表示需要的集合中的數。
例：對10億個IPV4的IP地址進行排序，每個IP只會出現一次。
思路：可以通過簡單的規則將10億IP地址全部轉換成32位的無符號整數，將這10億整數排序后，然后再轉回IP地址即可；更優的思路是申請長度為32位的bit類型的數組，然后將其對應到相應的位上，相比前一種方法，這個方法更節省空間。
4Byte * 10億 = 40 0000 0000Byte = 40 0000 0000 / 1024 /1024 /1024 GB = 3.725G
上圖計算得到的大小跟我算的不太一樣？
2^32 bit = 4 294 967 296bit = 4 294 967 296bit / 8 /1024/1024 M = 512M
3. Bloom Filter法
以一個例子來說Bloom Filter（布隆過濾器）；
最差情況下使用hash表或者數據表存儲，空間要求高：
64Byte*100億 = 6400 0000 0000 /1024/1024/1024G = 596.046G
當遇到下面這幾種情況，可以使用布隆過濾器：
布隆過濾器的特定：
對于上面題目的解決方案：
建立一個bitarray數組，長度為m；
有k個hash函數，輸出域>=m，每個hash函數是優秀的且相互獨立；
對每個URL通過k個hash函數，計算求得k個hash值，對每個hash值對應到bitarray上，進行涂黑，如果已經是黑色，則保持不變；
判斷某一個URL是不是黑名單里面的URL：
將URL通過k個hash函數計算得到k個hash值；
將k個hash值對應到bitarray數組中，如果對應的每個位都是黑色，則表示是黑名單URL；只要有一個位不是黑色，說明不是黑名單里面的URL；
當輸入的URL過多，bitarray數組過小的時候，bitarray數組中大部分都被涂黑，很有可能會產生誤判：因為這樣會導致即使a不是黑名單里面的URL，也可能會出現對應的每個bitarray數組位上都被涂黑。
如何確定bitarray大小：
總結：
4. 數據庫優化法
4.1 優秀的數據庫管理工具
4.2 數據分區
4.3 索引
4.4 緩存機制
4.5 加大虛存
4.6 分批處理
4.7 使用臨時表和中間表
4.8 優化查詢語句
4.9 使用視圖
4.10 使用存儲過程
4.11 使用排序來取代非順序存取
4.12 使用采樣數據進行數據挖掘
5. 倒排索引
6. 外排序法
7. Trie樹
8. 堆
9. 雙層桶法
10. MapReduce法
Map-Reduce可以分為兩個階段：
Map階段：把大任務分成若干個子任務（通過hash函數），然后將任務分配到某個節點上去處理；
Reduce階段：子任務并發處理，然后合并結果；
Map-Reduce原理簡單，工程上處理困難：
例：統計一片文章中每個單詞出現的個數。
實例分析
常見海量處理題目解題關鍵
1.分而治之。通過哈希函數將大任務分流到機器，或分流成小文件。
2.常用的hashMap或bitmap。
難點：通訊、時間和空間的估算。
1. top K 問題（《Java程序員面試寶典》例題，在面試中與經常遇見）
例如在搜索引擎中搜索最熱門的10個搜索詞；在歌曲庫中下載最熱門的前10首歌曲。
提示：可以結合Map-Reduce和Hadoop解決。
2.找個某個范圍內漏掉的數字（某某跳動公司面試題）
給定一個數組，數據的的范圍是-2^32 ~ 2^32，現給定一個無序不重復數組，里面有幾億個數字，范圍在給定的范圍內，要求任意給出一個，數組中漏掉的數字（即這個數字不在數組中，但在-2^32 ~ 2^32）。同時對時間空間要求都比較苛刻，需要折中。
提示：二分法；最大最小值。
2.1 這道題目是在牛客視頻學習遇見，跟上面題目一樣
32位無符號整數的范圍是0~4294967295.現在有一個正好包含40億個無符號整數的文件，所以在整個范圍中必然有沒出現過的數。可以使用最多10M的內存，只用找到一個沒出現過的數即可，該如何找？
分析：如果用哈希表來記錄所有的數，最差情況下，將出現40億個不同的數。每一條記錄占有4字節，大約需要16G內存。
解法一：使用bitarray
解法二：分流
總結：
3.對10億人的年齡進行排序
4.排序問題（《Java程序員面試寶典》例題）
5. 找出出現次數最多的數
有一個包含20億個全是32位整數的大文件，在其中找到出現次數最多的數。但是內存限制只有2G。
解法一：
解法二：
6. 找出每天最熱的100詞
某搜索公司一天的用戶搜索詞匯是海量的，假設有百億的數據量，請設計一種求出每天最熱100詞的可行方法。
7.在集群中實現緩存
工程師常用服務器集群來設計和實現數據緩存，以下是常見的策略。
01.無論是添加、刪除還是查詢數據，都先將數據id通過哈希函數轉換成一個哈希值，記為key。
02.如果目前機器有N臺，則計算key%N的值，這個值就是該數據所屬的機器編號，無論是添加、刪除還是查詢操作，都只在這臺機器上進行。請分析這種緩存策略可能帶來的問題，并提出改進的方案。
可能帶來的問題：
解決方案：使用一致性哈希算法
設定一個范圍內的數據，然后收尾相連，形成一個環。根據機器id由hash函數計算得到機器在環上的位置。
如何確定一條數據歸屬哪臺機器：該數據的id用hash函數算出hash值，并映射到環中相應的位置，順時針找到距離此位置最近的一臺機器，那么這臺機器就存放該數據。
當添加節點應該怎么辦：比如m3機器加入其中，則將data1中的數據復制到m3機器上，這樣代價更小一點。
當刪除機器怎么辦：只要將刪除機器的數據全部復制到順時針的下一臺機器上即可。
部分理論參考《Java程序員面試寶典》，大多實例是我自己總結而來！
書籍分享：https://pan.baidu.com/s/1lh7xnfQvm9KaRC4P_3wyHg
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
