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

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

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

前言

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

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

基本方法

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

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

1.1 哈希算法

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

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

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

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

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

1.2 位圖法

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

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

1.3 Bloom Filter

檢測一個(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ò)誤。