先思考用壹個大的HashMap的情況。 key是某個整數，value是該整數出現的次數，這樣可以統計詞頻，然後得出TOP10詞頻。計算此時使用的內存，4字節無符號整數範圍是0到42億多（如果是有符號整數範圍是-21億多到21億多），範圍是比40億大的。最差情況下如果40億個數都不同，此時HashMap使用的空間為40億條記錄，每條記錄中key（無符號整數）是4字節，value（詞頻）也是4字節（int類型），總***8字節，總計320億字節，即32G（10億字節可估算為1G），哈希表爆掉了。
這裏先補充壹下哈希函數的特征：
特征1.輸入域無窮大，輸出域相對有限。
特征2.沒有任何隨機的成分，是確定規則的函數。輸入相同那麽輸出壹定相同；不同的輸入可能會有相同輸出（哈希碰撞）。
特征3. 輸入哪怕很接近，最終的計算結果也很離散，和輸入規律沒有關系。這壹點也是最關鍵的特征。
特征4.輸出再模上壹個數，取模的結果也是離散的
反推1G內存的HashMap可以有多少條記錄，保守點1億條，意味著該HashMap處理的包含數的種類（不是個數）不要超過1億種，怎麽處理？40億個整數的大文件，每個數字用哈希函數處理完再取模100，只會是0到99。根據哈希函數特征3，不同輸入會均勻分布到0到99上，40億個數如果擁有的不同數的種類是K種的話，這樣處理完後，每個小文件裏幾乎有100/k這麽多種數，這樣每個小文件裏就不到1億種了。再用HashMap壹個壹個文件去處理詞頻，搞出100個文件各自的TOP10，哈希函數相同輸入則相同輸出，所以不會出現壹個數字落到不同文件裏的情況。對文件的TOP10合並，就得到全局TOP10。
上面取模取40其實就可以了，40億個數種類數K小於等於40億，所以K/40小於等於1億，符合上面要求的1G內存，但取的是100而不是40是為了更保險。
使用位圖，用某個bit表示某個數出現過還是沒出現過。如果是哈希表，表示壹個數出現與否需要用壹個鍵值對，鍵和值都占4字節，那麽壹條記錄所占的空間就是64bit（8字節）。用位圖的話，1bit表示1個數，數範圍多大就用多少位bit；42億多bit/8 = 5億多byte = 500多M（10億byte=1G）；在1G空間內拿下。
用兩個bit位表示某個數字出現的頻率。00表示出現0次；01表示出現1次；10表示出現2次；11表示出現3次，如果出現次數更多大於3次，11不變。這樣最後統計下來就可以知道所有出現2次的數字，與原來相比就多了壹倍空間，1G空間拿下。
位圖不能用了，3KB空間太小了。先計算3KB能做多長的無符號數組，壹個無符號數大小為4B，3KB/4B=750，然後750距離2的某次方哪個最近，512，那就申請壹個長度為512的無符號整型數組arr（arr占用空間大小顯然不超過3KB）。題目中數字範圍是0到2的32次方減壹（壹***有2的32次方這麽多個數），因為和512壹樣都是2的某次方，所以2的32次方壹定可以均分成512份（每壹份大小是8388608）；arr[0]表示512份裏的第0份（範圍0~8388607），表示這壹份上的詞頻統計；而且因為壹***只有40億個數，那麽arr[0]統計的數字壹定不會溢出（40億 2的32次方減壹 = 42億多，壹無符號數是32位）；如果統計所有數出現的頻率到對應範圍的份上，壹定有某壹份詞頻不夠83888608；假設不足的那壹份是第a份，那麽下次把3KB在第a份這個範圍上再分512份，最終往下分，總能找到哪個數字沒出現。
總體時間復雜度：以 512 為底的 2的32次方 的對數。這是個很小的數。且按行讀文件占用內存是很少的，讀文件並不是壹次性把所有文件都load到內存裏去，而是在硬盤文件裏用偏移量找到某壹行數據，讀下壹行的時候前壹行的空間就可以被釋放了；所以維持壹個句柄句尾還有偏移量就可以按行讀文件了。
整個範圍是0到2的32次方減壹。計算出中點Mid並統計0到Mid範圍出現多少個數記為a，統計Mid+1到結尾範圍出現多少數記為b個；a和b中壹定有壹個不滿，不滿的那個再二分，最終壹定能定位到某個數字沒出現，遍歷次數以 2 為底 2的32次方 對數次，即32次
面對空間限制類題目，從範圍數據狀況入手，分區間統計的思想。
用哈希函數把URL分配到很多機器上去，每臺機器上的文件再用哈希函數分成小文件，每個小文件分區間統計之後，找到重復的URL
利用堆、外排序來做多個處理單元的結果合並
通過1G內存分流文件，這1G用於存儲哈希表。哈希函數特性是同樣的URL會進到壹個文件裏去，文件大小為分流到1G可以統計下為止，從而把100億個URL的大文件分流成小文件。哈希表的key是64字節（URL大小），value是long類型（因為是100億個，無符號整數不夠用）8字節。然後算1G內存最多可以放多少條這種記錄，就可以知道小文件容忍的的不同的URL最多有多少條；從而反推出假設100億個URL都是不同的，需要多少個小文件保證1G不超。
計算：64+8=72字節，哈希表內部可能有索引空間的占用，可以算的富裕壹點，算作壹條記錄要100字節；1G=10億字節，得出哈希表最多放1千萬條記錄，即記錄1千萬種不同的URL；最壞情況100億個URL都不同，100億/1千萬得需要1千個小文件，那麽原來的URL大文件用哈希函數算完再模上1千，分到對應的小文件裏（根據哈希函數的性質，每個小文件裏種類差不多是均分的，而且每個文件裏記錄數差不多1千萬左右，不會超出多少）。然後在這1G空間裏統計每個小文件裏詞頻的TOP100，1千個文件有1千個TOP100，然後在每個文件裏建立用詞頻作為排序的大根堆。
把每個堆的堆頂再組成壹個大根堆，構成堆上堆，二維堆（即上圖中的二叉樹結構）；例如上圖裏包含甲、乙、丙；a、b、c；α、β、θ三個堆，現在堆頂元素甲、a、α構成大根堆
如上圖所示，假如調整完發現α是最大的，那麽α與a交換時是α這壹串與a這壹串交換，就輸出了α作為整個詞頻中TOP1。
如上圖所示，α輸出後β頂上來，但β未必是全局最大值，所以堆頂元素組成的大根堆開始heapify；假如甲此時是全局最大值，那麽甲這壹串與β那壹串交換......如此循環往復，每次堆上堆輸出壹個最大值，下面的元素頂上來，然後堆上堆再調整，整個串交換；二維堆每次輸出壹個，輸出100次就是TOP100。
如果是遍歷，時間代價O(100)；用堆結構可以加速到O(log100)。從這裏可以看出外排每次決定壹個東西是遍歷壹遍每個堆堆頂並比較大小。
假設給的空間限制為3KB，和前面壹樣分成512份且每壹份都能統計下詞頻，第壹份假設這些數出現a個，第二份假設這些數出現b個，第三份假設這些數出現c個，所有段的詞頻都有，然後把a、b、c……加起來，看在哪個範圍上剛超20億或剛好20億，就把第20億定位在這個範圍上了。
舉例假如第 i 份加完是19億個，第 i + 1份加完是21億個，那麽20億就在第 i + 1份上且是第 i + 1份上的第1億個，接下來在第 i + 1份上再分512份去詞頻統計，看哪壹份是剛超1億或剛好到1億，如此下去，總有統計出來的時候。