O(n)

常用數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度

1 一致性算法

一致性的分類

• 強(qiáng)一致性
  • 說明：保證系統(tǒng)改變提交以后立即改變集群的狀態(tài)。
  • 模型：
    • Paxos：角色過多持寄，實(shí)現(xiàn)復(fù)雜
    • Raft（muti-paxos）
    • ZAB（muti-paxos）
• 弱一致性
  • 說明：也叫最終一致性，系統(tǒng)不保證改變提交以后立即改變集群的狀態(tài)究抓，但是隨著時(shí)間的推移最終狀態(tài)是一致的斋竞。
  • 模型：
    • DNS系統(tǒng)
    • Gossip協(xié)議

一致性算法實(shí)現(xiàn)舉例

• Google的Chubby分布式鎖服務(wù)，采用了Paxos算法
• etcd分布式鍵值數(shù)據(jù)庫(kù)佳遣，采用了Raft算法
• ZooKeeper分布式應(yīng)用協(xié)調(diào)服務(wù)，Google Chubby的開源實(shí)現(xiàn)凡伊，采用ZAB算法

1.1 Paxos

分布式系統(tǒng)對(duì)某個(gè)決議達(dá)成一致零渐。大于n/2

3種角色

• Proposer
• Acceptor
• Learner

兩個(gè)階段

• 準(zhǔn)leader選舉
• leader確認(rèn)

1.2 ZAB

• ZooKeeper Atomic Broadcast，原子消息廣播協(xié)議系忙。大于n/2原則诵盼。
  • 崩潰恢復(fù)階段
  • 數(shù)據(jù)同步階段
  • 消息廣播階段
• ZAB算法大部分跟Raft算法相同，僅有如下地方不同：
  • ZAB的zxid=epoch+index银还，Raft用term+index
  • ZAB的Follower投票前必須與leader的日志一致风宁，Raft是誰term高投誰
  • ZAB的心跳是Follower到Leader，Raft相反

1.3 Raft

動(dòng)畫演示Raft：http://thesecretlivesofdata.com/raft/

三種角色

• Leader
• Follower
• Candidate

兩個(gè)階段

• Leader選舉
• 狀態(tài)復(fù)制

Raft與ZAB區(qū)別

• 相同點(diǎn)
  • 都是leader負(fù)責(zé)寫
  • 都是心跳檢測(cè)探活
  • leader選舉都是先到先得
  • 都要求大于n/2
• 不同點(diǎn)
  • ZAB的zxid=epoch+index蛹疯，Raft用term+index
  • ZAB的Follower投票前必須與leader的日志一致戒财，Raft是誰term高投誰
  • ZAB的心跳是Follower到Leader，Raft相反

1.4 NWR

• N捺弦，N份備份數(shù)據(jù)
• W饮寞，W份寫入成功
• R，R份讀取成功
• W + R > N列吼，強(qiáng)一致性
• W + R <= N幽崩，無法強(qiáng)一致性

1.5 Gossip

• Gossip算法稱為反熵(Anti-Entropy)，熵寞钥，代表雜亂無章歉铝；
• 反熵，在雜亂無章中尋找一致性凑耻；
• 所有節(jié)點(diǎn)都是平等的太示，沒有中心節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)收到數(shù)據(jù)更新都將其廣播給其他節(jié)點(diǎn)香浩，直到更新消息傳遍整個(gè)集群类缤。

1.6 一致性hash算法

• 一致性hash可以解決傳統(tǒng)取模操作無法應(yīng)對(duì)Server增刪的問題，常用于負(fù)載均衡邻吭。
• 一致性hash好處
  • 平衡性：哈希結(jié)果均勻分布
  • 單調(diào)性：新來的到新空間餐弱，不影響舊空間
  • 平滑性
• 一致性hash原理
  • 0~2^32-1，環(huán)形hash空間
  • hash算法映射到環(huán)形空間
  • 增刪節(jié)點(diǎn)只影響逆時(shí)針到下一個(gè)節(jié)點(diǎn)中間環(huán)形范圍
  • 虛擬節(jié)點(diǎn)囱晴，提高h(yuǎn)ash節(jié)點(diǎn)過少導(dǎo)致的平衡性問題

2 加密算法

• 哈希算法/散列算法

  • MD5：MD5輸出128bit
  • SHA1：SHA1輸出160bit膏蚓，SHA256輸出256bit
  • HMAC
  • CRC：常用的CRC32 只輸出32bit

• 對(duì)稱加密算法：安全性較非對(duì)稱加密算法低，加密速度相對(duì)較快畸写，秘鑰難于管理驮瞧，一般用于內(nèi)部系統(tǒng)，適用于大數(shù)據(jù)量的加解密處理枯芬。

  • DES
  • 3DES
  • AES

• 非對(duì)稱加密算法：安全性較高论笔，加密速度較慢，適合小數(shù)據(jù)量加解密處理千所。

  • RSA
  • ECC

加密算法對(duì)比

2.1 MD5

MD5 用的是 哈希函數(shù)狂魔，它的典型應(yīng)用是對(duì)一段信息產(chǎn)生 信息摘要，以 防止被篡改淫痰。嚴(yán)格來說最楷，MD5 不是一種 加密算法 而是 摘要算法。無論是多長(zhǎng)的輸入待错，MD5 都會(huì)輸出長(zhǎng)度為 128bits 的一個(gè)串 (通常用 16 進(jìn)制 表示為 32 個(gè)字符)籽孙。

2.2 SHA1

SHA1 是和 MD5 一樣流行的 消息摘要算法，然而 SHA1 比 MD5 的 安全性更強(qiáng)朗鸠。對(duì)于長(zhǎng)度小于 2 ^ 64 位的消息蚯撩，SHA1 會(huì)產(chǎn)生一個(gè) 160 位的 消息摘要≈蛘迹基于 MD5胎挎、SHA1 的信息摘要特性以及 不可逆 (一般而言)，可以被應(yīng)用在檢查 文件完整性 以及 數(shù)字簽名 等場(chǎng)景忆家。

2.3 HMAC

HMAC 是密鑰相關(guān)的 哈希運(yùn)算消息認(rèn)證碼（Hash-based Message Authentication Code）犹菇，HMAC 運(yùn)算利用 哈希算法 (MD5、SHA1 等)芽卿，以 一個(gè)密鑰 和 一個(gè)消息 為輸入揭芍，生成一個(gè) 消息摘要 作為 輸出。

HMAC 發(fā)送方 和 接收方 都有的 key 進(jìn)行計(jì)算卸例，而沒有這把 key 的第三方称杨，則是 無法計(jì)算 出正確的 散列值的肌毅，這樣就可以 防止數(shù)據(jù)被篡改。

2.4 CRC

CRC姑原，Cyclic Redundancy Check悬而，循環(huán)冗余校驗(yàn)，利用網(wǎng)絡(luò)數(shù)據(jù)包或電腦文件產(chǎn)生固定位數(shù)的校驗(yàn)碼的散列函數(shù)锭汛，利用除法及余數(shù)的原理來做錯(cuò)誤偵測(cè)笨奠。

2.5 DES

DES 加密算法是一種 分組密碼，以 64 位為 分組對(duì)數(shù)據(jù) 加密唤殴，它的 密鑰長(zhǎng)度 是 56 位般婆，加密解密 用 同一算法。

DES 加密算法是對(duì) 密鑰 進(jìn)行保密朵逝，而 公開算法蔚袍，包括加密和解密算法。這樣廉侧，只有掌握了和發(fā)送方 相同密鑰 的人才能解讀由 DES加密算法加密的密文數(shù)據(jù)页响。因此，破譯 DES 加密算法實(shí)際上就是 搜索密鑰的編碼段誊。對(duì)于 56 位長(zhǎng)度的 密鑰 來說闰蚕，如果用 窮舉法 來進(jìn)行搜索的話，其運(yùn)算次數(shù)為 2 ^ 56 次连舍。

2.6 3DES

是基于 DES 的 對(duì)稱算法没陡，對(duì) 一塊數(shù)據(jù) 用 三個(gè)不同的密鑰 進(jìn)行 三次加密，強(qiáng)度更高索赏。

2.7 AES

AES盼玄，Advanced Encryption Standard，高級(jí)加密標(biāo)準(zhǔn)潜腻，對(duì)稱加密算法埃儿。AES 加密算法是密碼學(xué)中的 高級(jí)加密標(biāo)準(zhǔn)，該加密算法采用 對(duì)稱分組密碼體制融涣，密鑰長(zhǎng)度的最少支持為 128 位童番、 192 位、256 位威鹿，分組長(zhǎng)度 128 位剃斧，算法應(yīng)易于各種硬件和軟件實(shí)現(xiàn)。這種加密算法是美國(guó)聯(lián)邦政府采用的 區(qū)塊加密標(biāo)準(zhǔn)忽你。

AES 本身就是為了取代 DES 的幼东，AES 具有更好的 安全性、效率 和 靈活性。

AES

2.8 RSA

RSA根蟹，非對(duì)稱加密算法脓杉，公鑰加密、私鑰解密简逮，基于大質(zhì)數(shù)的因式分解丽已。RSA 加密算法是目前最有影響力的 公鑰加密算法，并且被普遍認(rèn)為是目前 最優(yōu)秀的公鑰方案 之一买决。RSA 是第一個(gè)能同時(shí)用于 加密 和 數(shù)字簽名 的算法，它能夠 抵抗 到目前為止已知的 所有密碼攻擊吼畏，已被 ISO 推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)督赤。

RSA 加密算法 基于一個(gè)十分簡(jiǎn)單的數(shù)論事實(shí)：將兩個(gè)大 素?cái)?shù) 相乘十分容易，但想要對(duì)其乘積進(jìn)行 因式分解 卻極其困難泻蚊，因此可以將 乘積 公開作為 加密密鑰躲舌。

非對(duì)稱加密算法流程

RSA加密過程

2.9 ECC

ECC 也是一種 非對(duì)稱加密算法，主要優(yōu)勢(shì)是在某些情況下性雄，它比其他的方法使用 更小的密鑰没卸，比如 RSA 加密算法，提供 相當(dāng)?shù)幕蚋叩燃?jí) 的安全級(jí)別秒旋。不過一個(gè)缺點(diǎn)是 加密和解密操作 的實(shí)現(xiàn)比其他機(jī)制 時(shí)間長(zhǎng) (相比 RSA 算法约计，該算法對(duì) CPU 消耗嚴(yán)重)。

為什么質(zhì)數(shù)能用于加密算法迁筛？

這個(gè)問題就要涉及到大數(shù)的質(zhì)因數(shù)分解煤蚌。如果把一個(gè)由較小的兩個(gè)質(zhì)數(shù)相乘得到一個(gè)合數(shù)，將其分解成兩個(gè)質(zhì)數(shù)（除了1和自身的組合之外）很容易细卧，例如尉桩，51的兩個(gè)質(zhì)因數(shù)為3和17。然而贪庙，如果兩個(gè)很大的質(zhì)數(shù)相乘之后得到一個(gè)非常大的合數(shù)蜘犁，想要逆過來把該數(shù)分解成兩個(gè)質(zhì)數(shù)非常困難。例如止邮，511883这橙，分解成兩個(gè)質(zhì)因數(shù)之后為557和919；2538952327（超過25億）农尖，分解成兩個(gè)質(zhì)因數(shù)之后為29179和87013析恋，這個(gè)難度明顯要比上一個(gè)數(shù)大得多。

截至2019.01盛卡，目前已知最大的質(zhì)數(shù)是2^825899331助隧，這個(gè)數(shù)擁有超過2486萬位。即便是超級(jí)計(jì)算機(jī)，也很難有效對(duì)兩個(gè)質(zhì)數(shù)相乘得到的合數(shù)進(jìn)行質(zhì)因數(shù)分解并村，所以這樣的原理可以用于加密算法巍实。

3 排序算法(10種)

排序算法的時(shí)間復(fù)雜度

3.1 選擇排序(SelectionSort)~O(n^2)不穩(wěn)定

基本思路：每次找出最小的放最左邊

1. 遍歷數(shù)組找出最小元素，移動(dòng)到數(shù)組a[0]位置哩牍；
2. 繼續(xù)遍歷數(shù)組找出最小元素棚潦，移動(dòng)到數(shù)組a[1]位置；
3. 依次遍歷直到從小到大將整個(gè)數(shù)組排好序膝昆。

優(yōu)缺點(diǎn)

1. 最簡(jiǎn)單丸边、最沒用的排序算法，效率低荚孵，時(shí)間復(fù)雜度O(n^2)妹窖，不穩(wěn)定。

改進(jìn)點(diǎn)

1. 外循環(huán)可以減少一次收叶，只需要執(zhí)行array.length-1次即可抒蚜；
2. 內(nèi)循環(huán)可以減少一半次數(shù)所意，每次遍歷可以找出最小值和最大值雌贱，最小值放數(shù)組左邊庄新，最大值放數(shù)組右邊。

代碼示例

3.2 冒泡排序(BubbleSort)~O(n^2)穩(wěn)定

基本思路：兩兩比較交換

1. 比較兩個(gè)相鄰元素澄峰，如果前一個(gè)比后一個(gè)大嫉沽，則交換這兩個(gè)元素，每次循環(huán)找出最大元素放到數(shù)組右邊摊阀，依次循環(huán)耻蛇，直到從小到大排好序。

優(yōu)缺點(diǎn)

1. 思路簡(jiǎn)單胞此，效率低臣咖，時(shí)間復(fù)雜度O(n^2)，穩(wěn)定漱牵。

代碼示例

public static void bubbleSort1(int [] a, int n){
        int i, j;
        
        for(i=0; i<n; i++){//表示n 次排序過程夺蛇。
            for(j=1; j<n-i; j++){
                if(a[j-1] > a[j]){//前面的數(shù)字大于后面的數(shù)字就交換
                    //交換a[j-1]和a[j]
                    int temp;
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j]=temp;
                }
            }
        }
    }

3.3 插入排序(InsertSort)~O(n^2)穩(wěn)定

基本思路：每次插入與前面比較交換

1. 每插入一個(gè)元素跟前一個(gè)元素比較，如果a[j]<a[j-1]就交換酣胀，依次比較交換刁赦，直到從小到大排好序；
2. 對(duì)基本有序的數(shù)組最有用闻镶。

優(yōu)缺點(diǎn)

1. 思路簡(jiǎn)單甚脉，效率低，時(shí)間復(fù)雜度O(n^2)铆农，穩(wěn)定牺氨。

代碼示例

public void sort(int arr[]) {
        for(int i =1; i<arr.length;i++) {
            //插入的數(shù)
            int insertVal = arr[i];
            //被插入的位置(準(zhǔn)備和前一個(gè)數(shù)比較)
            int index = i-1;
            //如果插入的數(shù)比被插入的數(shù)小
            while(index>=0&&insertVal<arr[index]) {
                //將把a(bǔ)rr[index] 向后移動(dòng)
                arr[index+1]=arr[index];
                //讓index 向前移動(dòng)
                index--;
            }
            //把插入的數(shù)放入合適位置
            arr[index+1]=insertVal;
        }
    }

3.4 希爾排序(ShellSort)~O(n^1.3)不穩(wěn)定

基本思路：按照縮進(jìn)的間隔序列排序

1. 希爾排序是改進(jìn)的插入排序，比插入排序效率高，時(shí)間復(fù)雜度O(n^1.3)猴凹，不穩(wěn)定夷狰；
2. 每次按照一定間隔排序，間隔從大到小郊霎，最后要按照間隔為1排序沼头。

優(yōu)缺點(diǎn)

1. 間隔大的時(shí)候移動(dòng)次數(shù)少，間隔小的時(shí)候移動(dòng)距離短书劝，不穩(wěn)定进倍。

希爾排序間隔序列

• Knuth序列
  • h=3h+1,h=1

代碼示例

private void shellSort(int[] a) {
        int dk = a.length/2;
        while( dk >= 1 ){
            ShellInsertSort(a, dk);
            dk = dk/2;
        }
    }
    
    private void ShellInsertSort(int[] a, int dk) {
        //類似插入排序，只是插入排序增量是1购对，這里增量是dk,把1 換成dk 就可以了
        for(int i=dk;i<a.length;i++){
            if(a[i]<a[i-dk]){
                int j;
                int x=a[i];//x 為待插入元素
                a[i]=a[i-dk];
                for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                    //通過循環(huán)背捌，逐個(gè)后移一位找到要插入的位置。
                    a[j+dk]=a[j];
                }
                a[j+dk]=x;//插入
            }
        }
    }

3.5 歸并排序(MergeSort)~O(nlogn)穩(wěn)定

基本思路：不停合并排好序的子序列

1. 待排序列按照兩個(gè)或兩個(gè)以上元素分為若干子序列洞斯，在各自子序列排好序；
2. 繼續(xù)擴(kuò)大子序列繼續(xù)排坑赡，直到整體有序

public class MergeSortTest {
    public static void main(String[] args) {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        print(data);
        mergeSort(data);
        System.out.println("排序后的數(shù)組：");
        print(data);
    }
    public static void mergeSort(int[] data) {
        sort(data, 0, data.length - 1);
    }
    public static void sort(int[] data, int left, int right) {
        if (left >= right)
            return;
// 找出中間索引
        int center = (left + right) / 2;
// 對(duì)左邊數(shù)組進(jìn)行遞歸
        sort(data, left, center);
// 對(duì)右邊數(shù)組進(jìn)行遞歸
        sort(data, center + 1, right);
// 合并
        merge(data, left, center, right);
        print(data);
    }
    /**
     * 將兩個(gè)數(shù)組進(jìn)行歸并烙如，歸并前面2 個(gè)數(shù)組已有序，歸并后依然有序
     *
     * @param data
     * 數(shù)組對(duì)象
     * @param left
     * 左數(shù)組的第一個(gè)元素的索引
     * @param center
     * 左數(shù)組的最后一個(gè)元素的索引毅否，center+1 是右數(shù)組第一個(gè)元素的索引
     * @param right
     * 右數(shù)組最后一個(gè)元素的索引
     */
    public static void merge(int[] data, int left, int center, int right) {
// 臨時(shí)數(shù)組
        int[] tmpArr = new int[data.length];
// 右數(shù)組第一個(gè)元素索引
        int mid = center + 1;
// third 記錄臨時(shí)數(shù)組的索引
        int third = left;
// 緩存左數(shù)組第一個(gè)元素的索引
        int tmp = left;
        while (left <= center && mid <= right) {
// 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
// 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while 只會(huì)執(zhí)行其中一個(gè)）
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
// 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
// （原left-right 范圍的內(nèi)容被復(fù)制回原數(shù)組）
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }
}

3.6 堆排序(HeapSort)~O(nlogn)不穩(wěn)定

3.7 快速排序(QuickSort)~O(nlogn)不穩(wěn)定

基本思路：小于基準(zhǔn)值的放左邊亚铁，大于基準(zhǔn)值的放右邊

快速排序最差情況會(huì)退化為冒泡排序，最壞情況下的時(shí)間復(fù)雜度為O(n^2)

快速排序思路

3.8 桶排序(BucketSort)~O(n+k)穩(wěn)定

待排序列劃分為n個(gè)大小相同的區(qū)間螟加，區(qū)間叫做桶徘溢，每個(gè)桶內(nèi)各自排序，最后合并捆探。

1. 找出待排序數(shù)組中的最大值max然爆、最小值min
2. 我們使用 動(dòng)態(tài)數(shù)組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲(chǔ)黍图。桶的數(shù)量為(maxmin)/
   arr.length+1
3. 遍歷數(shù)組 arr曾雕，計(jì)算每個(gè)元素 arr[i] 放的桶
4. 每個(gè)桶各自排序

public static void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            13/04/2018 Page 241 of 283
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
//創(chuàng)建桶
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
//將每個(gè)元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
//對(duì)每個(gè)桶進(jìn)行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
    }

3.9 計(jì)數(shù)排序(CountingSort)~O(n+k)穩(wěn)定

計(jì)數(shù)排序是桶排序的特殊情況，計(jì)數(shù)排序的每個(gè)桶里面只有一個(gè)元素助被。

3.10 基數(shù)排序(RadixSort)~O(n*k)穩(wěn)定

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度剖张，數(shù)位較短的數(shù)前面補(bǔ)零。然后揩环，從最低位開始搔弄，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個(gè)有序序列丰滑。

public class radixSort {
        inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2
            5,53,51};
        public radixSort(){
            sort(a);
            for(inti=0;i<a.length;i++){
                System.out.println(a[i]);
            }
        }
        public void sort(int[] array){
//首先確定排序的趟數(shù);
            int max=array[0];
            for(inti=1;i<array.length;i++){
                if(array[i]>max){
                    13/04/2018 Page 242 of 283
                    max=array[i];
                }
            }
            int time=0;
//判斷位數(shù);
            while(max>0){
                max/=10;
                time++;
            }
//建立10 個(gè)隊(duì)列;
            List<ArrayList> queue=newArrayList<ArrayList>();
            for(int i=0;i<10;i++){
                ArrayList<Integer>queue1=new ArrayList<Integer>();
                queue.add(queue1);
            }
//進(jìn)行time 次分配和收集;
            for(int i=0;i<time;i++){
//分配數(shù)組元素;
                for(intj=0;j<array.length;j++){
//得到數(shù)字的第time+1 位數(shù);
                    int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
                    ArrayList<Integer>queue2=queue.get(x);
                    queue2.add(array[j]);
                    queue.set(x, queue2);
                }
                int count=0;//元素計(jì)數(shù)器;
//收集隊(duì)列元素;
                for(int k=0;k<10;k++){
                    while(queue.get(k).size()>0){
                        ArrayList<Integer>queue3=queue.get(k);
                        array[count]=queue3.get(0);
                        queue3.remove(0);
                        count++;
                    }
                }
            }
        }
    }

4 查找算法

查找算法的時(shí)間復(fù)雜度

• 查找算法分類

  • 靜態(tài)查找和動(dòng)態(tài)查找顾犹，查找表中有刪除和插入操作的是動(dòng)態(tài)查找
  • 無序查找和有序查找，有序查找要求待查找序列必須是有序的，無序查找沒有這個(gè)要求

• 平均查找長(zhǎng)度(ASL蹦渣，Average Search Length)：查找算法在查找成功時(shí)的平均查找長(zhǎng)度哄芜。
  　　對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為：ASL = Pi*Ci的和柬唯。
  　　Pi：查找表中第i個(gè)數(shù)據(jù)元素的概率认臊。
  　　Ci：找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過的次數(shù)。

4.1 順序查找/線性查找~O(n)

無序查找的一種锄奢，適合于存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)或鏈接存儲(chǔ)的線性表失晴，ASL=n(n+1)/2，時(shí)間復(fù)雜度為O(n)拘央。

4.2 二分查找/折半查找~O(logn)

有序查找算法的一種涂屁，待查找序列如果不是有序的，先要進(jìn)行排序操作灰伟。查找時(shí)候先和中間值比較拆又，小則往左邊比較，大則往右邊比較栏账。

4.3 插值查找~O(loglogn)

有序查找算法的一種帖族，在二分查找/折半查找基礎(chǔ)上改進(jìn)的，查找點(diǎn)不是1/2開始挡爵，而是自適應(yīng)的竖般，插值查找的查找點(diǎn)mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

4.4 斐波那契查找~O(logn)

有序查找算法的一種，基于二分查找/折半查找改進(jìn)的茶鹃，查找基準(zhǔn)點(diǎn)不是中間元素涣雕，而是斐波那契數(shù)-1。

4.5 樹表查找~O(logn)

• 二叉樹查找算法
• 2-3查找樹
• 紅黑樹
• B樹闭翩、B+樹

4.6 分塊查找~O(logn)

分塊查找挣郭，又稱為索引順序查找，是順序查找的一種改進(jìn)方法疗韵。

4.7 哈希查找~O(1)

哈希散列查找丈屹，時(shí)間和空間的折中。

5 TopK問題

5.1 TopK業(yè)務(wù)場(chǎng)景

常見TopK問題

1. 有10000000個(gè)記錄伶棒，這些查詢串的重復(fù)度比較高旺垒，如果除去重復(fù)后，不超過3000000個(gè)肤无。一個(gè)查詢串的重復(fù)度越高先蒋，說明查詢它的用戶越多，也就是越熱門宛渐。請(qǐng)統(tǒng)計(jì)最熱門的10個(gè)查詢串竞漾，要求使用的內(nèi)存不能超過1GB眯搭。
2. 有10個(gè)文件，每個(gè)文件1GB业岁，每個(gè)文件的每一行存放的都是用戶的query鳞仙，每個(gè)文件的query都可能重復(fù)。按照query的頻度排序笔时。
3. 有一個(gè)1GB大小的文件棍好，里面的每一行是一個(gè)詞，詞的大小不超過16個(gè)字節(jié)允耿，內(nèi)存限制大小是1MB借笙。返回頻數(shù)最高的100個(gè)詞。
4. 提取某日訪問網(wǎng)站次數(shù)最多的那個(gè)IP较锡。
5. 10億個(gè)整數(shù)找出重復(fù)次數(shù)最多的100個(gè)整數(shù)业稼。
6. 搜索的輸入信息是一個(gè)字符串，統(tǒng)計(jì)300萬條輸入信息中最熱門的前10條蚂蕴，每次輸入的一個(gè)字符串為不超過255B低散，內(nèi)存使用只有1GB。
7. 有1000萬個(gè)身份證號(hào)以及他們對(duì)應(yīng)的數(shù)據(jù)骡楼，身份證號(hào)可能重復(fù)谦纱，找出出現(xiàn)次數(shù)最多的身份證號(hào)。

問題抽象

• 海量數(shù)據(jù)中找出最大的前K個(gè)數(shù)
• 海量數(shù)據(jù)中找出出現(xiàn)頻率最高的前K個(gè)數(shù)

5.2 TopK解決方案

• 全排序君编。最常見思路，性能最低川慌。

  • 最快的排序算法時(shí)間復(fù)雜度為O(nlogn)吃嘿，比如說快速排序。
  • 要考慮海量數(shù)據(jù)是否能一次裝入內(nèi)存梦重，比如說在32位的機(jī)器上兑燥，每個(gè)float類型占4個(gè)字節(jié)，1億個(gè)浮點(diǎn)數(shù)就要占用400MB的存儲(chǔ)空間琴拧，對(duì)于一些可用內(nèi)存小于400M的計(jì)算機(jī)而言降瞳，很顯然是不能一次將全部數(shù)據(jù)讀入內(nèi)存進(jìn)行排序的。
  • 其實(shí)即使內(nèi)存能夠滿足要求（我機(jī)器內(nèi)存都是8GB）蚓胸，該方法也并不高效挣饥，因?yàn)轭}目的目的是尋找出最大的10000個(gè)數(shù)即可，而排序卻是將所有的元素都排序了沛膳，做了很多的無用功扔枫。

• 局部淘汰法。

  • 該方法與排序方法類似锹安，用一個(gè)容器保存前10000個(gè)數(shù)短荐，然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比倚舀，如果所有后續(xù)的元素都比容器內(nèi)的10000個(gè)數(shù)還小，那么容器內(nèi)這個(gè)10000個(gè)數(shù)就是最大10000個(gè)數(shù)忍宋。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大痕貌，則刪掉容器內(nèi)最小元素，并將該元素插入容器糠排，最后遍歷完這1億個(gè)數(shù)舵稠，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了。此時(shí)的時(shí)間復(fù)雜度為O（n+m^2）乳讥，其中m為容器的大小柱查，即10000。

• 分治法云石。

  • 將1億個(gè)數(shù)據(jù)分成100份唉工，每份100萬個(gè)數(shù)據(jù)，找到每份數(shù)據(jù)中最大的10000個(gè)汹忠，最后在剩下的10010000個(gè)數(shù)據(jù)里面找出最大的10000個(gè)淋硝。如果100萬數(shù)據(jù)選擇足夠理想，那么可以過濾掉1億數(shù)據(jù)里面99%的數(shù)據(jù)宽菜。100萬個(gè)數(shù)據(jù)里面查找最大的10000個(gè)數(shù)據(jù)的方法如下：用快速排序的方法谣膳，將數(shù)據(jù)分為2堆，如果大的那堆個(gè)數(shù)N大于10000個(gè)铅乡，繼續(xù)對(duì)大堆快速排序一次分成2堆继谚，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對(duì)大堆快速排序一次分成2堆阵幸，如果大堆個(gè)數(shù)N小于10000個(gè)花履，就在小的那堆里面快速排序一次，找第10000-n大的數(shù)字挚赊；遞歸以上過程诡壁，就可以找到第1w大的數(shù)。參考上面的找出第1w大數(shù)字荠割，就可以類似的方法找到前10000大數(shù)字了妹卿。此種方法需要每次的內(nèi)存空間為10^64=4MB，一共需要101次這樣的比較蔑鹦。

• Hash法夺克。

  • 如果這1億個(gè)書里面有很多重復(fù)的數(shù)，先通過Hash法嚎朽，把這1億個(gè)數(shù)字去重復(fù)懊直，這樣如果重復(fù)率很高的話，會(huì)減少很大的內(nèi)存用量火鼻，從而縮小運(yùn)算空間室囊，然后通過分治法或最小堆法查找最大的10000個(gè)數(shù)雕崩。

• 最小堆。

  • 首先讀入前10000個(gè)數(shù)來創(chuàng)建大小為10000的最小堆融撞，建堆的時(shí)間復(fù)雜度為O（mlogm）（m為數(shù)組的大小即為10000）盼铁，然后遍歷后續(xù)的數(shù)字，并于堆頂（最谐①恕）數(shù)字進(jìn)行比較饶火。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字致扯；如果比堆頂數(shù)字大肤寝，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過程直至1億個(gè)數(shù)全部遍歷完為止抖僵。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字鲤看。該算法的時(shí)間復(fù)雜度為O（nmlogm），空間復(fù)雜度是10000（常數(shù)）耍群。

• MapReduce

  • 首先根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(MD5)后的值按照范圍劃分到不同的機(jī)器上义桂，最好可以讓數(shù)據(jù)劃分后一次讀入內(nèi)存，這樣不同的機(jī)器負(fù)責(zé)處理不同的數(shù)值范圍蹈垢，實(shí)際上就是Map慷吊。得到結(jié)果后，各個(gè)機(jī)器只需拿出各自出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)曹抬，然后匯總溉瓶，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，這實(shí)際上就是Reduce過程谤民。對(duì)于Map函數(shù)堰酿，采用Hash算法，將Hash值相同的數(shù)據(jù)交給同一個(gè)Reduce task赖临；對(duì)于第一個(gè)Reduce函數(shù)，采用HashMap統(tǒng)計(jì)出每個(gè)詞出現(xiàn)的頻率灾锯，對(duì)于第二個(gè)Reduce 函數(shù)兢榨，統(tǒng)計(jì)所有Reduce task，輸出數(shù)據(jù)中的top K即可顺饮。 直接將數(shù)據(jù)均分到不同的機(jī)器上進(jìn)行處理是無法得到正確的結(jié)果的吵聪。因?yàn)橐粋€(gè)數(shù)據(jù)可能被均分到不同的機(jī)器上，而另一個(gè)則可能完全聚集到一個(gè)機(jī)器上兼雄，同時(shí)還可能存在具有相同數(shù)目的數(shù)據(jù)吟逝。

5.3 TopK實(shí)際業(yè)務(wù)場(chǎng)景解決方案

• 單機(jī)+單核+足夠大內(nèi)存
  • 排序法
• 單機(jī)+多核+足夠大內(nèi)存
  • 多線程+排序法
• 單機(jī)+單核+受限內(nèi)存
  • hash分割+內(nèi)存排序
• 多機(jī)+受限內(nèi)存
  • hash分片到多臺(tái)機(jī)器+每臺(tái)按照(單機(jī)+單核+受限內(nèi)存)處理

5.4 重復(fù)問題

在海量數(shù)據(jù)中查找出重復(fù)出現(xiàn)的元素或者去除重復(fù)出現(xiàn)的元素也是常考的問題赦肋。針對(duì)此類問題块攒，一般可以通過位圖法實(shí)現(xiàn)励稳。例如，已知某個(gè)文件內(nèi)包含一些電話號(hào)碼囱井，每個(gè)號(hào)碼為8位數(shù)字驹尼，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。 本題最好的解決方法是通過使用位圖法來實(shí)現(xiàn)庞呕。8位整數(shù)可以表示的最大十進(jìn)制數(shù)值為99999999新翎。如果每個(gè)數(shù)字對(duì)應(yīng)于位圖中一個(gè)bit位，那么存儲(chǔ)8位整數(shù)大約需要99MB住练。因?yàn)?B=8bit地啰，所以99Mbit折合成內(nèi)存為99/8=12.375MB的內(nèi)存，即可以只用12.375MB的內(nèi)存表示所有的8位數(shù)電話號(hào)碼的內(nèi)容讲逛。

6 常用算法