Java高頻面試題之海量數(shù)據(jù)處理分析

更新時(shí)間：2022年10月14日 08:42:12 作者：碼農(nóng)研究僧

海量信息處理日益成為當(dāng)前程序員筆試面試中一個(gè)新的亮點(diǎn)。硬件擴(kuò)容是難滿足海量數(shù)據(jù)處理需要的，如何利用現(xiàn)有條件進(jìn)行海量信息處理？本文就來(lái)為大家解答一下

前言

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

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

基本方法

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

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

1.1 哈希算法

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

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

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

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

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

1.2 位圖法

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

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

1.3 Bloom Filter

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

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

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

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

1.5 倒排索引法

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

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

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

一般情況下可以采用矩陣的方式存儲(chǔ)來(lái)存儲(chǔ)，但會(huì)浪費(fèi)大量的空間

1.6 外排序法

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

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

適用于大數(shù)據(jù)的排序和查重，但是效率比較低，因?yàn)橐玫絠o的操作

1.7 字典樹(shù)

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

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

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

Trie樹(shù)一般具有3個(gè)基本特性:

根結(jié)點(diǎn)不包含字符,除根結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都只包含一個(gè)字符。
從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該結(jié)點(diǎn)對(duì)應(yīng)的字符串。
每個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)包含的字符都不相同。