【什么是雙層桶】
事實上，與其說雙層桶劃分是一種數據結構，不如說它是一種算法設計思想。面對一堆大量的數據我們無法處理的時候，我們可以將其分成一個個小的單元，然后根據一定的策略來處理這些小單元，從而達到目的。
【適用范圍】
第k大，中位數，不重復或重復的數字
【基本原理及要點】
因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。
【擴展】
當有時候需要用一個小范圍的數據來構造一個大數據，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。
【問題實例】
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。 當然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~
2).5億個int找它們的中位數。
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾 大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
3).現在有一個0-30000的隨機數生成器。請根據這個隨機數生成器，設計一個抽獎范圍是0-350000彩票中獎號碼列表，其中要包含20000個中獎號碼。
這個題剛好和上面兩個思想相反，一個0到3萬的隨機數生成器要生成一個0到35萬的隨機數。那么我們完全可以將0-35萬的區間分成35/3=12個區間，然后每個區間的長度都小于等于3萬，這樣我們就可以用題目給的隨機數生成器來生成了，然后再加上該區間的基數。那么要每個區間生成多少個隨機數呢？計算公式就是：區間長度*隨機數密度，在本題目中就是30000*（20000/350000）。最后要注意一點，該題目是有隱含條件的：彩票，這意味著你生成的隨機數里面不能有重復，這也是我為什么用雙層桶劃分思想的另外一個原因。
做人好厚道，轉載請注明出處：http://diducoder.com/mass-data-topic-6-multi-dividing.html