分治法
- 總體思想是先根據(jù)Hash函數(shù)將一個(gè)內(nèi)存難以一次性讀取的大文件分散到若干小文件中（其中相同的數(shù)據(jù)會(huì)被hash到同一個(gè)小文件中）蔚叨，然后對(duì)每一個(gè)小文件的數(shù)據(jù)進(jìn)行處理棒厘，再進(jìn)行合并處理（例如外排序：對(duì)小文件進(jìn)行快排约计，然后對(duì)于有序的子序列，只需要很少的內(nèi)存就可以進(jìn)行歸并排序）
- 在處理海量數(shù)據(jù)中的最小k個(gè)數(shù)之類的問(wèn)題可以使用堆排序（時(shí)間復(fù)雜度為O(N*lgk)）
多層劃分
- 舉例：求取海量數(shù)據(jù)的中位數(shù)挣输。對(duì)于int32整數(shù)來(lái)說(shuō)刊驴，可以按照32個(gè)位的前n位進(jìn)行區(qū)域劃分，可以劃分2^n個(gè)區(qū)域胸墙，這些區(qū)域間是有序的我注。這樣就可以確定中位數(shù)再哪個(gè)區(qū)域的第幾大 數(shù)
bitmap
- 實(shí)質(zhì)為bit數(shù)組，每一位只能為0或1
- int32只需要512M的內(nèi)存就可以存儲(chǔ)全部的整數(shù)
- 可以用2bit來(lái)表示多種狀態(tài)迟隅，例如00表示無(wú)但骨，01表示出現(xiàn)1次，10表示出現(xiàn)多次
字典樹(shù)（Trie Tree）
- 只能用于字符串
- 在遍歷時(shí)構(gòu)建
- 相比于Hash表優(yōu)點(diǎn)在于空間開(kāi)銷(xiāo)小
bloom filter
- 一般用bit數(shù)組存儲(chǔ)智袭，用于在海量數(shù)據(jù)下判斷某元素時(shí)候存在于集合之中
- 使用k個(gè)Hash函數(shù)奔缠，將每一個(gè)數(shù)據(jù)都映射在bit數(shù)組中的k個(gè)位上（使用多個(gè)hash函數(shù)是為了減緩沖突問(wèn)題，但是仍不可避免沖突所以有誤差）
- 缺點(diǎn)是不能刪除元素补履，除非把bit數(shù)組換成int數(shù)組添坊，每一位表示一個(gè)計(jì)數(shù)器
倒排索引
- 用于文本檢索，對(duì)所有文檔建立倒排索引箫锤，可以查詢指定單詞出現(xiàn)在哪些文檔中
simhash
- 用于比較文本之間的相似度
- 思想是將高維的特征向量降維成低維的特征向量贬蛙，通過(guò)兩個(gè)向量的海明距離來(lái)判斷相似度
- 五個(gè)步驟：
- 分詞：將文本進(jìn)行分詞并對(duì)每個(gè)詞賦予一個(gè)權(quán)重，代表該詞在整個(gè)文本中的重要程度
- hash：通過(guò)hash函數(shù)將原詞映射為n位bit簽名谚攒，將字符串轉(zhuǎn)換為了向量
- 加權(quán)：給詞向量加權(quán)阳准，對(duì)于每一位，1則直接乘權(quán)重馏臭，0則乘負(fù)的權(quán)重
- 合并：將文本中的所有的詞向量加權(quán)結(jié)果進(jìn)行累加野蝇，變成一個(gè)向量
- 降維：根據(jù)合并結(jié)果讼稚，大于0則置為1，小于0則置為0绕沈。這樣就得到了一個(gè)n-bit的文本simhash簽名
- 根據(jù)經(jīng)驗(yàn)锐想，文本之間海明距離小于3則認(rèn)為相似度較高
