海量信息即大規模數據，隨着互聯網技術的發展，互聯網上的信息越來越多，如何從海量信息中提取有用信息成為當前互聯網技術發展必須面對的問題。
在海量數據中提取信息，不同於常規量級數據中提取信息，在海量信息中提取有用數據，會存在以下幾個方面的問題：
（1）數據量過大，數據中什麼情況都可能存在，如果信息數量只有20條，人工可以逐條進行查找、比對，可是當數據規模擴展到上百條、數千條、數億條，甚至更多時，僅僅只通過手工已經無法解決存在的問題，必須通過工具或者程序進行處理。
（2）對海量數據信息處理，還需要有良好的軟硬件配置，合理使用工具，合理分配系統資源。通常情況下，如果需要處理的數據量非常大，超過了TB級，小型機、大型工作站是要考慮的，普通計算機如果有好的方法也可以考慮，如通過聯機做成工作集羣。
（3）對海量信息處理時，要求很高的處理方法和技巧，如何進行數據挖掘算法的設計以及如何進行數據的存儲訪問等都是研究的難點。
針對海量數據的處理，可以使用的方法非常多，常見的方法有Hash法、Bit-map法、Bloom filter法、數據庫優化法、倒排索引法、外排序法、Trie樹、堆、雙層桶法以及MapReduce法。
Hash法
Hash 一般被翻譯為哈希，也被稱為散列，它是一種映射關係，即給定一個數據元素，其關鍵字為key，按一個確定的哈希函數Hash計算出hash（key），把hash（key）作為關鍵字key對應元素的存儲地址（或稱哈希地址），再進行數據元素的插入和檢索操作。簡而言之，哈希函數就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
哈希表是具有固定大小的數組，其中，表長（即數組的大小）應該為質數。哈希函數是用於關鍵字與存儲地址之間的一種映射關係，但是不能保證每個元素的關鍵字與函數值是一一對應的，因為極有可能出現對應於不同的元素，卻計算出了相同的函數值。衝突是指兩個關鍵字映射到同一個存儲地址的情況，即對不同的關鍵字可能得到同一散列地址，即key1！=key2，而 f(key1) = f(key2)
哈希函數的特點
哈希函數一般應具備以下幾個方面的特點：
（1）運算應該儘可能簡單
（2）函數的值域必須在散列表的範圍內
（3）儘可能的減少衝突
哈希函數的構建方法
哈希函數的構建方法一般有以下幾種：
（1）直接尋址法
取關鍵字或關鍵字的某個線性函數值為散列地址。即h(key)=key或h(key)=a*key+b,其中a和b均為整型常數，這種散列函數叫做自身函數。例如，有一個人口數字統計表，人的年齡取值範圍為1~100歲，其中，年齡作為關鍵字，哈希函數取關鍵字自身，但這種方法效率比較低，時間複雜度O(1)，空間複雜度為O(n)，n為關鍵字的個數。
直接尋址法不會產生衝突，但由於它沒有壓縮映像，因此當關鍵字集合很大時，使用這種Hash函數是不可能實現地址編碼的散列的。
（2）取模法
選擇一個合適的正整數p，令hash（Key） = key mod p。p如果選擇的是比較大的素數，則效果比較好，一般選取p為TableSize，即哈希表的長度。
（3）數字分析法
設關鍵字是d位的以r為基的數（如以10為基的十進制數），且共有n個關鍵字。則關鍵字的每個位可能有r個不同的數符出現（即0,1,2，。。。，9），但這r個數符在各個位上出現的頻率不一定相同，可能在某些位上分佈比較均勻，即每個數符出現的次數接近於n/r，而在另一些位上分佈不均勻。因此可選取其中分佈較均勻的，重新組成新的數，用其作為哈希地址。
這種方法簡單、直觀，但是需要預先知道每個關鍵字的情況，這就限制了它的使用範圍。
（4）摺疊法
將關鍵字分成位數為t的幾個部分（最後一部分的位數可能小於t），然後把各部分按位對齊進行相加，將所得的和捨棄進位，留下t位作為哈希地址。當關鍵字位數很多，而且關鍵字中每位上數字分佈比較均勻時，採用摺疊法比較合適。
（5）平方取中法
這是一種較常用的方法，將關鍵字進行平方運算，然後從結果的中間取出若干位（位數與散列地址的位數相同），將其作為散列地址，具體取幾位由哈希表的表長決定。
（6）除留餘數法
除留餘數法是一種比較常用的哈希函數，它的主要原理是取關鍵字除以某個數p（p不大於哈希表的長度TableSize）的餘數作為哈希地址，即Hash（key）=key%p
使用除留餘數法時，選取合適的p值很重要，一般要求p<=TableSize，且接近TableSize，p一般選取質數，也可以是不包含小於20質因子的合數
（7）隨機數法
選擇一個隨機函數，然後用關鍵字key的隨機函數值作為哈希地址，即Hash（key）=random（key）
解決衝突的方法
解決衝突的主要途徑是當一個關鍵字映射到哈希表中的某一個地址且該地址上已有關鍵字時，再為該關鍵字尋找新的存儲地址。
（1）開放地址法
基本思想是當發生地址衝突時，在哈希表中再按照某種方法繼續探測其他的存儲地址，直到找到空閒的地址為止
?
|
1 |
|
其中H(key)為關鍵字key的直接哈希地址，m為哈希表的長度，di為每次再探測時的地址增量。
採用這種方法時，首先計算出關鍵字的直接哈希地址，即H（key），如果該直接哈希地址上已有其他的關鍵字，則繼續查看地址為[H(key)+di]的存儲地址，判斷其是否為空。如此反覆直至找到空閒的存儲地址為止，然後將關鍵字key存放到該地址。
（2）鏈地址法
鏈地址法解決衝突的主要思想是：如果哈希表空間為[0,m-1]，則設置一個由m個指針組成的一維數組CH[m]，然後在尋找關鍵字哈希地址的過程中，所有哈希地址為i的數據元素都插入到頭指針為CH[i]的鏈表中。這種方法比較適合於衝突比較嚴重的情況下使用<喎�"/kf/ware/vc/" target="_blank" >vcD4NCjxwPqOoM6Op1NnJosHQt6g8YnIgLz4NCrWxt6LJ+rPlzbvKsaOsyrnTw7Xatv649qGitdrI/bj2uf7Po7qvyv28xsvjtdjWt6Os1rG1vc7es+XNu8qxoaO1q9Xi1ta3vbeotcTIsbXjyse8xsvjyrG85LvhtPO3+dT2vNOhozwvcD4NCjxwPqOoNKOpvajBotK7uPa5q7my0uez9sf4oaM8YnIgLz4NCrzZyei5/s+juq/K/bXE1rXT8s6qWzAsbS0xXaOs1PLJ6M/ywb9IYXNoVGFibGVbMCwmaGVsbGlwOyxtLTFdzqq7+bG+se2jrMHtzeLJ6MGitOa0or/VvOTP8sG/T3ZlclRhYmxlWzAsJmhlbGxpcDssdl3Tw9LUtOa0oreiyfqz5c27tcS8x8K8oaM8L3A+DQo8cD5IYXNo1vfSqtPDwLS9+NDQJmxkcXVvO7/sy9m05sihJnJkcXVvO6Os1NpPKDEpyrG85Li01NO2yMDvvs2/ydLUsunV0rW9xL+x6tSqy9ijrLvy1d/F0LbPxuTKx7fxtObU2qGjSGFzaMr9vt294bm5wO+1xMr9vt221M3iysfU08LSzt7Q8rXEo6zO3reotcPWqsbkvt/M5bTmtKLOu9bDo6zSsrK71qq1wLj3uPa05rSi1KrL2M671sPWrrzktcTP4LuludjPtaOstavKx8i0v8nS1NTas6PK/cqxvOTA78XQts/UqsvYzrvWw7ywtObU2tPrt/GhozwvcD4NCjxwPtTauqPBv8r9vt20psDt1tCjrMq508NoYXNot723qNK7sOO/ydLUv+zL2bTmyKGhos2zvMbEs9Cpyv2+3aOsvau088G/yv2+3b340NC31sDgoaPA/cjno6zM4cihxLPI1bfDzsrN+NW+tM7K/dfutuC1xElQtdjWt7XIoaM8L3A+DQo8aDEgaWQ9"bit-map法">Bit-map法
Bit-map（位圖）法的基本原理是使用位數組來表示某些元素是否存在，如8位電話號碼中查重複號碼，它適用於海量數據的快速查找、判重、刪除等。
如，1101001011 表示的集合為{ 1,2,4,7,9,10 }
位圖排序的時間複雜度是O(n)的，比一般的排序都快，但它以空間換時間（需要一個N位別的串）的，而且有些限制，即數據狀態不是很多。例如，排序前集合大小最好已知，而且集合中元素的最大重複次數必須已知，最好是惆集數據（不然空間浪費很大）
位圖法適用於判斷數據是否重複，也使用位圖法判斷某個數據是否存在。（需要兩次遍歷數據）
Bloom filter法
遇到問題：程序中判斷一個元素是否在一個集合中
最直接解決方法是將集合中全部的元素都存儲在計算機中，每當遇到一個新元素時，就將它和集合中的元素直接進行比較即可。這種做法雖然能夠準確無誤地完成任務，但是比較次數太多，效率比較低下。
Bloom filter正是解決這一問題的有效方法，它是一種空間效率和時間效率很高的隨機數據結構，它用來檢測一個元素是否屬於一個集合。但是它犧牲了正確率，Bloom filter以犧牲正確率為前提，來換取空間效率與時間效率的提高。當它判斷某元素不屬於這個集合時，該元素一定不屬於這個集合；當它判斷某元素屬於這個集合時，該元素不一定屬於這個集合。具體而言，查詢結果由兩種可能，即“不屬於這個集合（絕對正確）”和”屬於這個集合（可能錯誤）“。所以，Bloom filter適合應用在對於低錯誤率可以容忍的場合。
So，使用Bloom filter的難點是如何根據輸入元素個數n，來確定位數組m的大小以及hash函數。當hash函數個數 k=(ln2)*(m/n)時錯誤率最小，在錯誤率不大於E的情況下，m至少要等於n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證位數組裏至少一半為0，則m應該>=nlg(1/E)*lge,大概就是nlg(1/E)的1.44倍（lg表示以2為底的對數）。
例如，假設E為0.01，即錯誤率為0.01，則此時m應該大約為n的13倍。這樣k大約是8個（注意，m與n的單位不同，m的單位是bit，而n則是以元素個數為單位）。通常單個元素的長度都是有很多bit的，所以使用bloom filter內存上通常都是節省的。
Bloom filter的優點是具有很好的空間效率和時間效率。它的插入和查詢時間都是常數，另外它不保存元素本身，具有良好的安全性。然而，這些優點都是以犧牲正確率為代價的。當插入的元素越多，錯判“元素屬於這個集合”的概率就越大。另外，Bloom filter只能插入元素，卻不能刪除元素，因為多個元素的哈希結果可能共用了Bloom filter結構中的同一個位，如果刪除元素，就可能會影響多個元素的檢測。所以，Bloom filter可以用來實現數據字典、進行數據的判重或者集合求交集。
CBF與SBF是BF的擴展，Counting Bloom Filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其餘集合元素的出現次數關聯，SBF採用counter中的最小值來近似表示元素的出現頻率。
數據庫優化法
互聯網上的數據一般都被存儲在數據庫中，很多情況下，人們並非對這些海量數據本身感興趣，而是需要從這些海量數據中提取出對自己有用的信息。例如，從數據中獲取訪問最多的頁面信息等，這就涉及數據的查詢技術等相關內容。
數據庫管理軟件選擇是否合理、表結構涉及是否規範、索引創建是否恰當都是影響數據庫性能的重要因素。所以，對數據庫進行優化，是實現海量數據高效處理的有效方法之一。常見的數據庫優化方法有以下幾種：
（1）優秀的數據庫管理工具
選擇一款優秀的數據庫管理工具非常重要。現在的數據庫一般使用Oracle、DB2、MySQL等。
（2）數據分區
進行海量數據的查詢優化，一種重要方式就是如何有效地存儲並降低需要處理的數據規模，所以可以對海量數據進行分區操作提高效率。例如，針對按年份存取的數據，可以按年進行分區，不同的數據庫有不同的分區方式，不過處理機制卻大體相同。例如，SQL Server的數據庫分區是將不同的數據存於不同的文件組下，而不同的文件組存於不同的磁盤分區下，這樣將數據分散開，減小磁盤I/O，減小了系統負荷，而且還可以將日誌、索引等放於不同的分區下。
（3）索引
索引一般可以加速數據的檢索速度，加速表與表之間的鏈接，提高性能，所以在對海量數據進行處理時，考慮到信息量比較大，應該對錶建立索引，包括在主鍵上建立聚簇索引，將聚合索引建立在日期列上等。
索引優點很多，但是對於索引的建立，還需要考慮到實際情況，而不是對每一個列建立一個索引。例如，針對大表的分組、排序等字段，都要建立相應的索引，同時還應該考慮建立複合索引。增加索引同時也有很多不利的方面：
創建索引和維護索引要耗費時間，這種時間隨着數據量的增加而增加 索引需要佔物理空間，除了數據表佔數據空間之外，每一個索引還要佔一定的物理空間。如果要建立聚簇索引，那麼需要的空間就會更大。 當對錶中的數據進行增加、刪除和修改的時候，索引也要動態地維護，這樣就降低了數據的維護速度。
所以索引要用到好的時機，索引的填充因子和聚集、非聚集索引都要考慮。
（4）緩存機制
當數據量增加時，一般的處理工具都要考慮到緩存問題。緩存大小設置的好差也關係到數據處理的成敗。例如，在處理2億條數據聚合操作時，緩存設置為10萬條/Buffer可行。
（5）加大虛存
由於系統資源有限，而需要處理的數據量非常大，所以當內存不足時，可以通過增加虛擬內存來解決
（6）分批處理
由於需要處理的信息量巨大，可以對海量數據進行分批處理（類似於雲計算中的MapReduce思想），然後再對處理後的數據進行合併操作，分而治之，有利於小數據量的處理，不至於面對大數據量帶來的問題。
（7）使用臨時表和中間表
數據量增加時，處理中要考慮提前彙總。這樣做的目的是化整為零，大表變小表，分塊處理完成後，再利用一定的規則進行合併，處理過程中的臨時表的使用和中間結果的保存都非常重要。如果對於超海量的數據，大表處理不了，只能拆分為多個小表。如果處理過程中需要多步彙總操作，可按彙總步驟一步步來。
（8）優化查詢語句
查詢語句的性能對查詢效率的影響是非常大的。編寫高效優良的SQL腳本和存儲過程是數據庫工作人員的職責，也是檢驗數據庫工作人員水平的一個標準。
（9）使用視圖
視圖中的數據來源於基本表，對海量數據的處理，可以將數據按一定的規則分散到各個基本表中，查詢或處理過程中可以基於視圖進行。
（10）使用存儲過程
在存儲過程中儘量使用SQL自帶的返回參數，而非自定義的返回參數，減少不必要的參數，避免數據冗餘。
（11）用排序來取代非順序存取
磁盤存取臂的來回移動使得非順序磁盤存取變成了最慢的操作，但是在SQL語句中這個現象被隱藏了，這樣就使得查詢中進行了大量的非順序頁查詢，降低了查詢速度。
（12）使用採樣數據進行數據挖掘
基於海量數據的數據挖掘正在逐步興起，面對着超海量的數據，一般的挖掘軟件或算法往往採用數據抽樣的方式進行處理，這樣的誤差不會很高，大大提高了處理效率和處理的成功率。一般採樣時要注意數據的完整性，防止過大的偏差。
倒排索引法
倒排索引是目前搜素引擎公司對搜索引擎最常用的存儲方式，也是搜索引擎的核心內容。在搜索引擎實際的引用之中，有時需要按照關鍵字的某些值查找記錄，所以是按照關鍵字建立索引，這個索引就被稱為倒排索引。
倒排索引也常被稱為反向索引、置入檔案或反向檔案，它本質上是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構，有兩種不同的反向索引形式：
（1）一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表
（2）一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
第二種形式提供了更多的兼容性（如短語搜索），但是需要更多的時間和空間來創建。
一般情況下可以採用矩陣的方式來存儲，但會浪費大量的空間。例如，對於如下的內容，
D1:The GDP increased.
D2:The text is this.
D3:My name is.
如果採用矩陣的方式存儲，見表14-1.其中，行表示關鍵字，列表示所有的文件。
通過比較發現，採用倒排索引比採用矩陣的方式節省很多的空間。
正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證查詢。在正向索引中，文檔佔據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是説，文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關係。而與正向索引相比，倒排索引的優點是在處理複雜的多關鍵字查詢時，可在倒排表中先完成查詢的並、交等邏輯運算，得到結果後再對記錄進行存取，這樣不必對每個記錄隨機存取，把對記錄的查詢轉換為地址集合的運算，從而提高查找速度。所以，倒排索引一般被應用於文檔檢索系統，查詢哪些文件包含了某個單詞，比如常見的學術論文的關鍵字搜索
外排序法
外排序，即當待排序的對象數目特別多時，在內存中不能一次處理，必須把它們以文件的形式存放於外存，排序時再把它們一部分一部分調入內存進行處理。
外排序是相對內排序而言的，它是大文件的排序，待排序的記錄存儲在外存儲器上，待排序的文件無法一次裝入內存，需要在內存和外部存儲器之間進行多次數據交換，以達到排序整個文件的目的。一般採用歸併排序等方式實現外排序，主要分為兩個步驟
（1）生成若干初始歸併段（順串），也被稱為文件預處理，把含有n個記錄的文件，按內存大小劃分為若干長度為L的子文件，然後分別將子文件調入內存，採用有效的內排序方法排序後送回外存
（2）進行多路歸併，即對這些初始歸併段進行歸併，使得有序的歸併段逐漸擴大，最後再外存上形成整個文件的單一歸併段，此時就完成了文件的外排序。
外排序的適用範圍是大數據的排序以及去重複。但外排序也存在着很大的缺陷，就是它會消耗大量的IO，效率不會很高。
Trie樹
Trie 這個單詞來自於“retrieve”，Trie樹又稱字典樹或鍵樹。是一種用於快速字符串檢索的多叉樹結構，其原理是利用字符串的公共前綴來降低時空開銷，即以空間換時間，從而達到提高程序效率的目的。Trie樹的典型應用是用於統計和排序大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
Trie樹一般具有以下3個基本特性：
（1）根結點不包含字符，除根結點外每一個結點都只包含一個字符
（2）從根結點到某一結點，路徑上經過的字符連接起來，為該結點對應的字符串
（3）每個結點的所有子結點包含的字符都不相同。
Trie樹可以利用字符串的公共前綴來節約存儲空間。 如圖14-4所示，該Trie樹用10個結點保存了5個字符串 amy、aan、em、rob、rg
在該Trie樹中，字符串“amy”和“aan”有公共前綴“a”。當然，如果系統中存在大量字符串且這些字符串基本沒有公共前綴，則相應的Trie樹將非常消耗內存，這也是Trie樹的一個缺點。
給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那麼稱b是a的兄弟單詞。例如，單詞army和mary互為兄弟單詞。現在要給出一種解決方案，對於用户輸入的單詞，根據給定的字典找出輸入單詞有哪些兄弟單詞。
一般情況下，Trie樹的結構都是採用26叉樹進行組織的，每個結點對應一個字母，查找的時候，就是一個字母一個字母地進行匹配，算法的時間複雜度就是單詞的長度n，效率很高。本例子可以定義一個Trie樹作為數據結構來查詢，此時就轉化為在一棵Trie樹中查找兄弟單詞，只要在Trie樹中的前綴中再存儲一個vector結構的容器，就可以大大降低時間複雜度。
上例中，Trie樹的構建是在預處理階段完成的，首先根據字典中的單詞來建立字典樹，當建立完字典樹後，查詢兄弟單詞的效率就會提高很多，比hash法效率還要高。
Trie樹適用數據量大、重複多，但是數據種類小可以放入內存的情況。例如，已知n（n很大）個由小寫字母構成的平均長度為10的單詞，判斷其中是否存在某個字符串是另一個字符串的前綴子串。針對這種問題，一般可以採用以下3種方法。
（1）迭代法
對於每一個單詞，都要去查找它前面的單詞中是否包含它，看每個字符串是否為字符串集中某個字符串的前綴，由於需要不停地進行迭代比較，所以此時的時間複雜度為O(n^2)
（2）Hash法
使用Hash方法存儲所有字符串的所有前綴子串。而建立存有子串Hash的時間複雜度為O(n*len)，查詢的複雜度為O(n)*O(1)=O(n)
（3）Trie樹
假設要查詢的單詞是abcd，那麼在它前面的單詞中，以b、c、d、f之類開頭的單詞則不必考慮，而只要找以a開頭的單詞中是否存在abcd就可以了。同樣，在以a開頭的單詞中，只要考慮以b作為第二個字母的單詞即可，所以建立Trie樹的複雜度為O(n*len)，而建立操作與查詢操作在trie樹中是可以同時執行的。所以，總的時間複雜度為O(n*len)，實際查詢的複雜度只是O(len)。
例如，有串911,911456輸入，如果要同時執行建立與查詢，過程如下：首先查詢911，沒有；然後存入9、91、911，再查詢911456，沒有；然後存入9114、91145、911456，而程序沒有記憶功能，並不知道911在輸入數據中出現過，所以使用Hash必須先存入所有子串，然後for循環查詢。而trie樹則可以，存入911後，已經記錄911為出現的字符串，在存入911456的過程中就能發現而輸出答案。反過來也可以，縣存入911456，再存入911時，當指針指向最後一個1時，程序會發現這個1已經存在，説明911必定是某個字符串的前綴
堆
堆是一種樹形數據結構，每個結點都有一個值，而通常所説的堆，一般是指二叉堆。在堆中，以大頂堆為例，堆的根結點的值最大，且根結點的兩個子樹也是一個大頂堆，基於以上特點，堆適用於海量數據求前N大（用小頂堆）或者前N小（用大頂堆）數問題，其中N一般比較小。例如，當求海量數據前N小的數據時，使用大頂堆，比較當前元素與大頂堆的最大元素（即堆頂元素），如果該元素小於最大元素，則應該替換該最大元素，並調整堆的結構。當求海量數據前N大的數據時，思路一樣。由於採用堆，只需要掃描一遍即可得到所有的前n元素，所以在海量信息處理中，效率非常高。
雙層桶法
雙層桶不是一種數據結構，而是一種算法思想，類似於分治思想。因為元素範圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定範圍，最後在一個可以接受的範圍內進行。
本文以桶排序進行分析，桶排序的基本思想是把[ 0,1）劃分為n個大小相同的子區間，每一子區間是一個桶，然後將n個記錄分配到各個桶中。因為關鍵字序列是均勻分佈在 [ 0,1）上的，所以必須採用關鍵字比較的排序方法（通常用插入排序）對各個桶進行排序，然後依次將各非空桶中的記錄連接（收集）起來即可。這種排序思想的前提是假設輸入的n個關鍵字序列隨機分佈在區間 [ 0,1）之上，若關鍵字序列的取值範圍不是該區間，只要其取值均非負，總能將所有關鍵字除以某一合適的數，將關鍵字映射到該區間上，但要保證映射後的關鍵字是均勻分佈在 [ 0,1）上的。
桶排序的平均時間複雜度是O(n)，最壞情況仍有可能是O(n^2)，一般只適用於關鍵字取值範圍較小的情況，否則所需桶的數目m太多導致浪費存儲空間和計算時間。例如，n=10，被排序的記錄關鍵字ki取值範圍是0~99之間的整數（36,5,16,98,95,47,32,36,48）時，要用100個箱子來做一趟排序。
桶排序一般適用於尋找第k大的數、尋找中位數、尋找不重複或重複的數字等情況。例如：
（1）在一個文件中有10億個整數，亂序排列，要求找出中位數，內存限制2GB
（2）現在有一個0~30000的隨機數生成器。請根據這個隨機數生成器，設計一個抽獎範圍是0~350000彩票中獎號碼列表，其中要包含20000箇中獎號碼。
MapReduce
MapReduce是雲計算的核心技術之一，是一種簡化並行計算的分佈式編程模型。它為並行系統的數據處理提供了一個簡單、高效的解決方案，其主要目的是為了大型集羣的系統能在大數據集上進行並行工作，並用於大規模數據的並行運算。
MapReduce適用於大規模數據集（通常大於1TB）的並行運算，它的核心操作是Map和Reduce，即MapReduce拆開為 “Map（映射）”和“Reduce（化簡）”。其中，Map函數獨立地對每個元素進行操作，它用於把一組鍵值對映射成一組新的鍵值對，即先通過Map程序將數據切割成不相關的區塊，分配（調度）給大量計算機處理達到分佈計算的效果，然後通過指定併發的Reduce函數來將結果彙總，保證所有映射鍵值對中的每一個共享相同的鍵組。
簡而言之，一個映射函數就是對一些獨立元素組成的概念上的列表（如一個測試成績的列表）的每一個元素進行指定的操作（例如，有人發現所有學生的成績都被低估了一分，它可以定義一個“加1”的映射函數，用來修正這個錯誤）。而Map操作與Reduce操作都可以高度並行運行，Map是把一組數據一對一地映射為另外的一組數據，其映射的規則由一個函數來指定。例如，對 [ 1,2,4,8 ] 進行乘 2 的映射就變為 [ 2,4,8,16 ] ，Reduce是對一組數據進行規約，這個規約的規則是由另外一個函數指定的。例如，對 [ 1,2,4,8 ] 進行求和規約得到的結果是 15，而對它進行求積的規約是 64。
通過MapReduce，不會分佈式並行編程的程序員也能很容易地將自己的程序運行在分佈式系統上。同時，通過該模型，能夠充分高效地利用集羣中每個機器的資源，適合在集羣中處理大規模數據的計算任務，這些優點使得其已成為雲計算平台的主流編程模型。