數據結構與演算法：大數據1

在介紹Map-Reduce前先介紹一下哈希函數。

哈希函數：

哈希函數又叫做散列函數，哈希函數的輸入域可以是非常大的範圍，但是輸出域是固定範圍，假設為S。

哈希函數的性質：

1.典型的哈希函數都擁有無限的輸入值域。

2.輸入值相同時，返回值一樣。

3.輸入值不同時，返回值可能一樣，也可能不一樣。

4.不同輸入值得到的哈希值，雖然可能會有重複，但是會整體均勻的分布在輸出域s上

1-3是哈希函數的關鍵，4是判斷一個哈希函數的優劣的關鍵。

取余是一種常見的手段。

Map-Reduce

Map階段：把大任務分成子任務

Reduce階段：子任務並發處理，然後合併結果

聽上去感覺不是很難，其實難點不在於原理，難點在於工程上要注意的點。

具體的例子：

用Map-Reduce的方法去統記幾百篇文章中每個單詞出現的個數

1.對文章進行預處理。

2.Map階段

3.Reduce階段（因為每個子任務都是並發執行的，所以在處理大數據的時候速度回較快）

海量數據處理經典題型

解題關鍵：

1.分而治之。通過哈希函數將大任務分流到機器，或者分流成小文件

2.常用的hashMap或bitmap

難點：通訊、時間和空間的估算

請對10億個IPV4的ip地址進行排序，每個ip地址只會出現一次。

常規做法：

ip---->轉化為無符號整數

10億個ip---->轉化為10億個整數（每個int類型4個位元組） 佔用空間約為4GB

然後進行排序，然後在將整數依次轉化為ip地址輸出。

（這裡補充一下相互轉化的知識）

ip轉化為整數

假如ip=10.2.3.193 以點為分隔符，轉化為長度為4整型數組

a[3]=10,a[2]=2，a[1]=3,a[0]=193

int nResult=(a[3] << 24) + (a[2] << 16) + (a[1] << 8) + a[0]

整數轉化為IP

將整數先轉化成二進位，然後每隔8位分割，然後單獨將這8位二進位轉化為整型即可

更優的做法：

創建一個2^32的bit類型的數組，大小為512MB（8個比特等於1個位元組），然後將IP地址轉化為對應的整數，然後將對應的位置設置為1，最後在按順序依次輸出bit數組，將IP通過位置對應的值（數組有2^32個位置）進行還原。

這種方法不僅佔用空間少，而且還節約了排序的時間

對10億人的年齡進行排序

直接使用計數排序即可

推薦閱讀：