前言

硬件擴容是難滿足海量數(shù)據(jù)處理需要的，如何利用現(xiàn)有條件進行海量信息處理

海量信息處理日益成為當(dāng)前程序員筆試面試中一個新的亮點

基本方法

通過查詢網(wǎng)上的方方面面知識點，以及閱讀一些相關(guān)書籍

常見的方法有Hash法、Bit - map法、Bloom filter法、數(shù)據(jù)庫優(yōu)化法、倒排索引法、外排序法、Trie樹、堆、雙層桶法以及 MapRe-duce法等

1.1 哈希算法

也被叫做散列（映射關(guān)系）。數(shù)據(jù)元素中的關(guān)鍵字為key，按散列函數(shù)計算出hash ( key)，也就是計算出它的存儲地址，從而對數(shù)據(jù)進行一些操作

沖突指的就是兩個關(guān)鍵字對應(yīng)同一個函數(shù)值，也就是映射相同的地址

為了減少沖突，散列函數(shù)也很有講究。盡量簡單，函數(shù)值域要在其范圍內(nèi)，也要減少其沖突

在數(shù)據(jù)結(jié)構(gòu)這本書中也有提及

• 常用的構(gòu)造散列函數(shù)的方法主要有：直接尋址法（按照關(guān)鍵字的線性關(guān)系）、取模法、數(shù)字分析法、平方取中法等
• 常見的解決沖突的方法主要有：開放地址法（遇到?jīng)_突的時候按照某種方法進行探測）、鏈地址法等等

1.2 位圖法

B使用位數(shù)組來表示某些元素是否存在（可用于查重，也可用于判斷某個數(shù)據(jù)是否存在）適用于海量數(shù)據(jù)的快速查找、判重、刪除等。

具體的操作是生成N位字符，如果有數(shù)字標(biāo)為1，沒數(shù)字標(biāo)為0。（用空間來換取時間，其排序的時間復(fù)雜度為 O（n））

1.3 Bloom Filter

檢測一個元素是否屬于一個集合。犧牲正確率換取空間效率與時間效率的提高。

基本原理是位數(shù)組與Hash函數(shù)的結(jié)合，包含m位數(shù)組（初始化為0），定義k個不同的hash函數(shù)（每個函數(shù)映射到位數(shù)組的k個位置）聯(lián)合使用。向集合插入元素時，根據(jù)k個Hash函數(shù)可以得到位數(shù)組中的k個位（設(shè)置為1），查詢查詢某個元素是否屬于集合，k個為1（存在），k個位不為1（不存在）。在插人其他元素時，可能會將其他位置為1，產(chǎn)生了錯誤。

1.4 數(shù)據(jù)庫優(yōu)化

可以通過數(shù)據(jù)庫的工具、數(shù)據(jù)分區(qū)、索引、緩存機制、優(yōu)化查詢、排序等

1.5 倒排索引法

根據(jù)關(guān)鍵字的某些值進行排序從而建立索引

存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射，它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)
有兩種不同的反向索引形式:

• 第一種形式是一條記錄的水平反向索引(或者反向檔案索引)包含每個引用單詞的文檔的列表;
• 第二種形式是一個單詞的水平反向索引(或者完全反向索引)又包含每個單詞在一個文檔中的位置。
• 第二種形式提供了更多的兼容性（例如短語搜索)，但是需要更多的時間和空間來創(chuàng)建。

一般情況下可以采用矩陣的方式存儲來存儲，但會浪費大量的空間

1.6 外排序法

定義：在內(nèi)存中不能一次處理過多的對象，須以文件形式外放。排序需一步步調(diào)入內(nèi)存處理（相對大文件，無法一次裝入內(nèi)存中，需多次交換數(shù)據(jù)）

可采用歸并排序或者二路歸并排序的手法

適用于大數(shù)據(jù)的排序和查重，但是效率比較低，因為要用到io的操作

1.7 字典樹

利用字符串的公共前綴來減少時空開銷（空間換時間）。用于快速字符串檢索的多叉樹結(jié)構(gòu)

統(tǒng)計和排序大量的字符串(但不僅限于字符串)，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。

優(yōu)點是:最大限度地減少無謂的字符串比較，查詢效率比散列表高。

Trie樹一般具有3個基本特性:

• 根結(jié)點不包含字符,除根結(jié)點外每一個結(jié)點都只包含一個字符。
• 從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字符連接起來，為該結(jié)點對應(yīng)的字符串。
• 每個結(jié)點的所有子結(jié)點包含的字符都不相同。

2. 經(jīng)典問題分析

2.1 top k問題

頻率最高的k個數(shù)或者找出最大的k個數(shù)等，目前比較好的方法是分治+Trie樹/hash +小頂堆。

• hash方法分解成多個小數(shù)據(jù)集（如果有重復(fù)的數(shù)字的話，通過去重減少很多的數(shù)據(jù)集）
• Trie樹或者hash統(tǒng)計每個小數(shù)據(jù)集中的query詞頻
• 小頂堆求出每個數(shù)據(jù)集中出頻率最高的前K個數(shù)
• 最后在所有top K中求出最終的top K

在實際應(yīng)用中，可能有足夠大的內(nèi)存，那么直接將數(shù)據(jù)扔到內(nèi)存中一次性處理即可，也可能機器有多個核，這樣可以采用多線程處理整個數(shù)據(jù)集。

2.2 重復(fù)問題

該問題可通過位圖法進行，此方法最優(yōu)

具體的執(zhí)行代碼可看書籍中的展示，此為該書籍的展示代碼

2.3 排序問題

數(shù)據(jù)庫排序（要求數(shù)據(jù)庫的規(guī)格比較好）

分治法（雖然縮小內(nèi)存，但是編碼復(fù)雜，速度變慢）

位圖法

到此這篇關(guān)于Java高頻面試題之海量數(shù)據(jù)處理分析的文章就介紹到這了,更多相關(guān)Java海量數(shù)據(jù)處理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論