Java 程序員面試寶典 筆記

• Hash 法
• Bit-map 法
• Bloom filter 法
• 數(shù)據(jù)庫(kù)優(yōu)化法
• 倒排索引法
• 外排序法
• Trie 樹(shù)
• 堆
• 雙層桶法
• MapReduce 法

Hash 法

散列

• hash 函數(shù)盡可能簡(jiǎn)單
• 函數(shù)的值域必須在散列表的范圍內(nèi)
• 盡可能減少?zèng)_突

Bit-map 法

位圖 法的基本原理是使用位數(shù)組成來(lái)表示某些元素是否存在. 本方法適用于海量數(shù)據(jù)的快速查找/判重/刪除等等.
與其說(shuō)是算法, 不如說(shuō)是一種緊湊的數(shù)據(jù)結(jié)構(gòu).

Bloom filter 法 (重點(diǎn))

引入了 K (K>1)個(gè)相互獨(dú)立的哈希函數(shù), 保證在給定的空間, 誤判率下, 完成元素判定重復(fù)的過(guò)程. 圖是 k = 3 時(shí)的 bloom filter.

bloom filter k = 3

x, y, z 經(jīng)由哈希函數(shù)映射將各自在 bitmap 中的三個(gè)位置置為 1, 當(dāng) w 出現(xiàn)時(shí),僅當(dāng) 3 個(gè)標(biāo)志位都為 1 時(shí), 才表示 w 在集合中. 圖中的情況會(huì)判定為 w 不在集合中.

bloom filter 的誤差

假設(shè)所有哈希函數(shù)散列足夠均勻, 散列后落到 bitmap 每個(gè)位置的 概率均等. bitmap 的大小為 m, 原始數(shù)集大小為 n, 哈希函數(shù)個(gè)數(shù)為 k:

1. 1 個(gè)散列函數(shù)時(shí), 接受一個(gè)元素時(shí) bitmap 中某一位置為 0 的概率為:
   1 - 1/m

2. k 個(gè)相互獨(dú)立的散列函數(shù), 接受一個(gè)元素時(shí) bitmap 中某一位置為 0 的概率為:
   (1 - 1/m)^2

3. 假設(shè)原始集合中, 所有元素都不相等 (最嚴(yán)格的情況), 講所有元素都輸入 bloom filter, 此時(shí)某一位置仍為 0 的概率為:
   ( 1 - 1/m ) ^ {nk}
   某一位置為 1 的概率為
   1-(1-1/m)^{nk}

4. 當(dāng)我們對(duì)某個(gè)元素進(jìn)行判重時(shí), 誤判即這個(gè)元素對(duì)應(yīng)的 k 個(gè)標(biāo)志位不全為 1, 但所有 k 個(gè)標(biāo)志位都被置為 1, 誤判率 \epsilon 約為:
   \epsilon \approx [1-(1-1/m)^{nk} ]^k
   這個(gè)誤判率比實(shí)際比值大, 因?yàn)橹v判斷正確的情況也算進(jìn)去了. 根據(jù)極限 {\lim_{n \to \infty}}(1+1/n)^n = e 可以得到:
   \epsilon \approx [1-e^{-{nk}/m} ]^k
   \epsilon得到最優(yōu)解,當(dāng)且僅當(dāng)
   k={m/n}In2 \approx 0.7* {m/n}
   此時(shí), 誤判率 \epsilon 與數(shù)集大小和
   \epsilon \approx (1-e^{-In2})^{-In2* m/n}=0.5^{In2*m/n} = 0.5^k

同時(shí), 由于硬盤(pán)空間時(shí)限制死的, 集合元素個(gè)數(shù) n 的大小反而與單個(gè)數(shù)據(jù)的比特?cái)?shù)成反比, 數(shù)據(jù)長(zhǎng)度為 64 bit 時(shí),
n= 5TB/64bit = 5 * 2^{40} Byte / 8 Byte \approx 2^{34}

若以 m = 16n 計(jì)算, bitmap 集合的大小為
2^{38}Bit = 2^{35} Byte = 32 GB, 此時(shí)的 \epsilon \approx 0.0005, 這是誤差的上限.

bloom filter 通過(guò)引入一定的錯(cuò)誤率, 使得海量數(shù)據(jù)判重在可以接受的內(nèi)存代價(jià)中得以實(shí)現(xiàn), 從上述公式可以看出, 隨著集合中的元素不斷輸入過(guò)濾器中(n增大), 誤差將越來(lái)越大. 但是, 當(dāng) bitmap 的大小 m (指 bit 數(shù))足夠大時(shí), 比如比 所有可能出現(xiàn)的不重復(fù)元素個(gè)數(shù) 還要大 10 倍以上時(shí), 錯(cuò)誤概率時(shí)可以接受的.

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.HashSet;
import java.util.Random;

public class testBloomFilter {

    static int sizeOfNumberSet = Integer.MAX_VALUE >> 4;

    static Random generator = new Random();

    public static void main(String[] args) {

        int error = 0;
        HashSet<Integer> hashSet = new HashSet<Integer>();
        BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), sizeOfNumberSet);

        for(int i = 0; i < sizeOfNumberSet; i++) {
            int number = generator.nextInt();
            if(filter.mightContain(number) != hashSet.contains(number)) {
                error++;
            }
            filter.put(number);
            hashSet.add(number);
        }

        System.out.println("Error count: " + error + ", error rate = " + String.format("%f", (float)error/(float)sizeOfNumberSet));
    }
}

參考: https://blog.csdn.net/zdxiq000/article/details/57626464

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

通過(guò)選擇合適的數(shù)據(jù)庫(kù)系統(tǒng)來(lái)優(yōu)化數(shù)據(jù)處理

倒排索引法

外排序法

Trie 法

堆

雙層桶法

MapReduce 法