空間換算：

目前成都創(chuàng)新互聯(lián)已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬主機(jī)、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、珠海網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

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一般被稱為散列，它是以一種映射關(guān)系，即給定一個(gè)數(shù)據(jù)元素，其關(guān)鍵字為key，按一個(gè)確定的散列函數(shù)計(jì)算出hash(key)，把hash(key)作為關(guān)鍵字key對(duì)應(yīng)元素的存儲(chǔ)地址（或稱散列地址），再進(jìn)行數(shù)據(jù)元素的插入和檢索操作。簡而言之，散列函數(shù)就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

    散列表是具有固定大小的數(shù)組，其中，表長應(yīng)該為質(zhì)數(shù)。散列函數(shù)是用于關(guān)鍵字與存儲(chǔ)地址之間的一種映射關(guān)系，但是，不能保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因?yàn)闃O有可能出現(xiàn)對(duì)應(yīng)于不同的元素，卻計(jì)算出相同的函數(shù)值，這就是哈希沖突。

1.1 常用散列函數(shù)的構(gòu)建方法：

1.1.1 直接尋址法

    h(key) = key 或者 h(key) = a * key + b;

1.1.2 取模法

    h(key) = key mod p;

1.1.3 數(shù)字分析法

1.1.4 折疊法

1.1.5 平方取中法

1.1.6 保留余數(shù)法

    h(key) = key % p;

1.1.7 隨機(jī)數(shù)法

    h(key) = random(key);

1.2 常用的解決沖突辦法

1.2.1 開放地址法

    當(dāng)發(fā)生地址沖突時(shí)，在散列表中再按照某種方法繼續(xù)探測其他的存儲(chǔ)地址，知道找到空閑的地址為止。

1.2.2 鏈地址法

1.2.3 再散列法

    當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)...散列函數(shù)計(jì)算地址，直到無沖突為止。時(shí)間消耗會(huì)增加。

1.2.4 建立一個(gè)公共溢出區(qū)

優(yōu)缺點(diǎn)：

    Hash主要是用來進(jìn)行“快速存取”，在O(1)時(shí)間復(fù)雜度里就可以查找到目標(biāo)元素，或者判斷其是否存在。Hash數(shù)據(jù)結(jié)構(gòu)里的數(shù)據(jù)對(duì)外是雜亂無序的，因此其具體存儲(chǔ)位置及各個(gè)存儲(chǔ)元素位置之間的相互關(guān)系是無法得知的，但是卻可以在常數(shù)時(shí)間里判斷元素位置及存在與否。在處理海量數(shù)據(jù)的過程中，使用Hash方法一般可以快速存取、統(tǒng)計(jì)某些數(shù)據(jù)，將大量數(shù)據(jù)進(jìn)行分類，例如提取某日訪問網(wǎng)站次數(shù)最多的IP地址等。

2. Bit-map法

    bit-map(位圖)法的基本原理是使用位數(shù)組來表示某些元素是否存在。

    bit-map法的結(jié)果是生成一個(gè)N位長的串，每位上以“1”或“0”表示需要的集合中的數(shù)。

例：對(duì)10億個(gè)IPV4的IP地址進(jìn)行排序，每個(gè)IP只會(huì)出現(xiàn)一次。

思路：可以通過簡單的規(guī)則將10億IP地址全部轉(zhuǎn)換成32位的無符號(hào)整數(shù)，將這10億整數(shù)排序后，然后再轉(zhuǎn)回IP地址即可；更優(yōu)的思路是申請(qǐng)長度為32位的bit類型的數(shù)組，然后將其對(duì)應(yīng)到相應(yīng)的位上，相比前一種方法，這個(gè)方法更節(jié)省空間。

4Byte * 10億 = 40 0000 0000Byte = 40 0000 0000 / 1024 /1024 /1024 GB = 3.725G

上圖計(jì)算得到的大小跟我算的不太一樣？

2^32 bit = 4 294 967 296bit = 4 294 967 296bit / 8 /1024/1024 M = 512M

3. Bloom Filter法

以一個(gè)例子來說Bloom Filter（布隆過濾器）；

最差情況下使用hash表或者數(shù)據(jù)表存儲(chǔ)，空間要求高：

64Byte*100億 = 6400 0000 0000 /1024/1024/1024G = 596.046G

當(dāng)遇到下面這幾種情況，可以使用布隆過濾器：

布隆過濾器的特定：

對(duì)于上面題目的解決方案：

1. 建立一個(gè)bitarray數(shù)組，長度為m；

2. 有k個(gè)hash函數(shù)，輸出域>=m，每個(gè)hash函數(shù)是優(yōu)秀的且相互獨(dú)立；

3. 對(duì)每個(gè)URL通過k個(gè)hash函數(shù)，計(jì)算求得k個(gè)hash值，對(duì)每個(gè)hash值對(duì)應(yīng)到bitarray上，進(jìn)行涂黑，如果已經(jīng)是黑色，則保持不變；

判斷某一個(gè)URL是不是黑名單里面的URL：

1. 將URL通過k個(gè)hash函數(shù)計(jì)算得到k個(gè)hash值；

2. 將k個(gè)hash值對(duì)應(yīng)到bitarray數(shù)組中，如果對(duì)應(yīng)的每個(gè)位都是黑色，則表示是黑名單URL；只要有一個(gè)位不是黑色，說明不是黑名單里面的URL；

當(dāng)輸入的URL過多，bitarray數(shù)組過小的時(shí)候，bitarray數(shù)組中大部分都被涂黑，很有可能會(huì)產(chǎn)生誤判：因?yàn)檫@樣會(huì)導(dǎo)致即使a不是黑名單里面的URL，也可能會(huì)出現(xiàn)對(duì)應(yīng)的每個(gè)bitarray數(shù)組位上都被涂黑。

如何確定bitarray大?。?/strong>

總結(jié)：

4. 數(shù)據(jù)庫優(yōu)化法

4.1 優(yōu)秀的數(shù)據(jù)庫管理工具

4.2 數(shù)據(jù)分區(qū)

4.3 索引

4.4 緩存機(jī)制

4.5 加大虛存

4.6 分批處理

4.7 使用臨時(shí)表和中間表

4.8 優(yōu)化查詢語句

4.9 使用視圖

4.10 使用存儲(chǔ)過程

4.11 使用排序來取代非順序存取

4.12 使用采樣數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘

5. 倒排索引

6. 外排序法

7. Trie樹

8. 堆

9. 雙層桶法

10. MapReduce法

Map-Reduce可以分為兩個(gè)階段：

1. Map階段：把大任務(wù)分成若干個(gè)子任務(wù)（通過hash函數(shù)），然后將任務(wù)分配到某個(gè)節(jié)點(diǎn)上去處理；

2. Reduce階段：子任務(wù)并發(fā)處理，然后合并結(jié)果；

Map-Reduce原理簡單，工程上處理困難：

例：統(tǒng)計(jì)一片文章中每個(gè)單詞出現(xiàn)的個(gè)數(shù)。

實(shí)例分析

常見海量處理題目解題關(guān)鍵

1.分而治之。通過哈希函數(shù)將大任務(wù)分流到機(jī)器，或分流成小文件。

2.常用的hashMap或bitmap。

難點(diǎn)：通訊、時(shí)間和空間的估算。

1. top K 問題（《Java程序員面試寶典》例題，在面試中與經(jīng)常遇見）

    例如在搜索引擎中搜索最熱門的10個(gè)搜索詞；在歌曲庫中下載最熱門的前10首歌曲。

提示：可以結(jié)合Map-Reduce和Hadoop解決。

2.找個(gè)某個(gè)范圍內(nèi)漏掉的數(shù)字（某某跳動(dòng)公司面試題）

    給定一個(gè)數(shù)組，數(shù)據(jù)的的范圍是-2^32 ~ 2^32，現(xiàn)給定一個(gè)無序不重復(fù)數(shù)組，里面有幾億個(gè)數(shù)字，范圍在給定的范圍內(nèi)，要求任意給出一個(gè)，數(shù)組中漏掉的數(shù)字（即這個(gè)數(shù)字不在數(shù)組中，但在-2^32 ~ 2^32）。同時(shí)對(duì)時(shí)間空間要求都比較苛刻，需要折中。

提示：二分法；最大最小值。

 2.1 這道題目是在?？鸵曨l學(xué)習(xí)遇見，跟上面題目一樣

    32位無符號(hào)整數(shù)的范圍是0~4294967295.現(xiàn)在有一個(gè)正好包含40億個(gè)無符號(hào)整數(shù)的文件，所以在整個(gè)范圍中必然有沒出現(xiàn)過的數(shù)?？梢允褂米疃?0M的內(nèi)存，只用找到一個(gè)沒出現(xiàn)過的數(shù)即可，該如何找？

分析：如果用哈希表來記錄所有的數(shù)，最差情況下，將出現(xiàn)40億個(gè)不同的數(shù)。每一條記錄占有4字節(jié)，大約需要16G內(nèi)存。

解法一：使用bitarray

解法二：分流

總結(jié)：

3.對(duì)10億人的年齡進(jìn)行排序

4.排序問題（《Java程序員面試寶典》例題）

5. 找出出現(xiàn)次數(shù)最多的數(shù)

    有一個(gè)包含20億個(gè)全是32位整數(shù)的大文件，在其中找到出現(xiàn)次數(shù)最多的數(shù)。但是內(nèi)存限制只有2G。

解法一：

解法二：

6. 找出每天最熱的100詞

    某搜索公司一天的用戶搜索詞匯是海量的，假設(shè)有百億的數(shù)據(jù)量，請(qǐng)?jiān)O(shè)計(jì)一種求出每天最熱100詞的可行方法。

7.在集群中實(shí)現(xiàn)緩存

    工程師常用服務(wù)器集群來設(shè)計(jì)和實(shí)現(xiàn)數(shù)據(jù)緩存，以下是常見的策略。

    01.無論是添加、刪除還是查詢數(shù)據(jù)，都先將數(shù)據(jù)id通過哈希函數(shù)轉(zhuǎn)換成一個(gè)哈希值，記為key。

    02.如果目前機(jī)器有N臺(tái)，則計(jì)算key%N的值，這個(gè)值就是該數(shù)據(jù)所屬的機(jī)器編號(hào)，無論是添加、刪除還是查詢操作，都只在這臺(tái)機(jī)器上進(jìn)行。請(qǐng)分析這種緩存策略可能帶來的問題，并提出改進(jìn)的方案。

可能帶來的問題：

解決方案：使用一致性哈希算法

    設(shè)定一個(gè)范圍內(nèi)的數(shù)據(jù)，然后收尾相連，形成一個(gè)環(huán)。根據(jù)機(jī)器id由hash函數(shù)計(jì)算得到機(jī)器在環(huán)上的位置。

    如何確定一條數(shù)據(jù)歸屬哪臺(tái)機(jī)器：該數(shù)據(jù)的id用hash函數(shù)算出hash值，并映射到環(huán)中相應(yīng)的位置，順時(shí)針找到距離此位置最近的一臺(tái)機(jī)器，那么這臺(tái)機(jī)器就存放該數(shù)據(jù)。

   當(dāng)添加節(jié)點(diǎn)應(yīng)該怎么辦：比如m3機(jī)器加入其中，則將data1中的數(shù)據(jù)復(fù)制到m3機(jī)器上，這樣代價(jià)更小一點(diǎn)。

    當(dāng)刪除機(jī)器怎么辦：只要將刪除機(jī)器的數(shù)據(jù)全部復(fù)制到順時(shí)針的下一臺(tái)機(jī)器上即可。

部分理論參考《Java程序員面試寶典》，大多實(shí)例是我自己總結(jié)而來！

書籍分享：https://pan.baidu.com/s/1lh7xnfQvm9KaRC4P_3wyHg