遞歸

簡而言之，就是自己調(diào)自己胳赌。

當滿足如下條件時疑苫，則可用遞歸來解決:

1. 一個問題的解可以分解為幾個子問題的解
2. 這個問題與分解之后的子問題捍掺，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
3. 存在遞歸終止條件

如何編寫遞歸代碼曲横？

遞歸方法禾嫉，必須 返回值能繼續(xù)當成入?yún)ⅲ?有條件終止調(diào)用夭织。
如果沒有條件中止調(diào)用，則會報出棧內(nèi)存溢出泥兰。

遞歸的核心思想其實還是循環(huán)調(diào)用题禀，是可以用for來替代的迈嘹，只是代碼利用了方法棧來進行循環(huán)秀仲，代碼看起來更加簡潔神僵。

排序

冒泡 O(n2)

冒泡排序只會操作相鄰的兩個數(shù)據(jù)保礼。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求目派。如果不滿足就讓它倆互換企蹭。一次冒泡會讓至少一個元素移動到它應該在的位置练对，重復 n 次螟凭，就完成了 n 個數(shù)據(jù)的排序工作螺男。

從另一個角度來看下隧，就是每一次對所有數(shù)據(jù)的交換淆院，就把數(shù)據(jù)總體的對應位數(shù)上的值確定了 ， 譬如第一次對所有數(shù)據(jù)進行遍歷交換支救，則確定了最后一個位置的值各墨。第二次再遍歷就不用遍歷最后一個位置了贬堵，第二次遍歷就確定了倒數(shù)第二位的值黎做。依次類推引几。
所以按照上述思路伟桅，我們實現(xiàn)則需要兩個for循環(huán)楣铁，內(nèi)循環(huán)進行數(shù)組遍歷交換更扁，外循環(huán)進行位置控制赫冬。 那么內(nèi)循環(huán)和外循環(huán)則可以互動劲厌，外循環(huán)+1之后 补鼻，內(nèi)循環(huán)便可以不用再處理相應的數(shù)據(jù)：

    for(int i=0;i<a.length-1;i++){
              for(int j=0;j<a.length-i-1;j++  ){
                    if(a[j]>a[j+1]){
                        a[j] =a[j]^a[j+1];
                        a[j+1] = a[j]^a[j+1];
                        a[j] = a[j]^a[j+1];
                    }
              }
          }

插入排序（Insertion Sort）O(n2)

首先风范，我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間硼婿，已排序區(qū)間和未排序區(qū)間寇漫。初始已排序區(qū)間只有一個元素猪腕，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素彻采，在已排序區(qū)間中找到合適的插入位置將其插入肛响，并保證已排序區(qū)間數(shù)據(jù)一直有序特笋。重復這個過程猎物，直到未排序區(qū)間中元素為空蔫磨，算法結束堤如。

換句話說搀罢，也就是把首元素看作原點榔至，依次遍歷數(shù)據(jù)洛退，遍歷一次都把之前的數(shù)據(jù)看成一個已經(jīng)排好序的數(shù)據(jù)群，把遍歷到的數(shù)據(jù)插入到前面舒數(shù)據(jù)群中以維持當前位置向前的數(shù)據(jù)均已排好序，然后繼續(xù)下一個元素驼仪。

  static void charu(int[] a){
        // 第一層for循環(huán)用于控制數(shù)據(jù)往后取
        for(int i=1;i<a.length;i++){
            int flag = a[i];
            int k;
          //第二層for循環(huán)用于比較和數(shù)據(jù)移位（從后往比較,大的就往后移）
            for( k=i;k>0 && a[k-1]>flag;k--){
                    a[k]=a[k-1];
            }
          //數(shù)據(jù)插入
            a[k] =flag;
        }
    }

【注： 這里雖然有三層for循環(huán)绪爸，但是第三層和之前兩層是由聯(lián)系的奠货，所以此處平均時間復雜度仍然為O(n2)】

選擇排序（Selection Sort） O(n2)

也就是選擇出一個最小的递惋，然后放到最前面萍虽。其實跟插入排序差不多。

static void xuanze(int[] a){
      //  最小值 和  最小值角標
       int x  ;
       int index ;
      //第一層遍歷代表外層  順序過去  一個坑一個坑的填
       for(int i =0 ;i<a.length;i++){
           index=i;
           x=a[i];
        //第二層循環(huán)用于選擇出 最小值 和其所在的角標
           for(int j=a.length-1 ; j>i;j--){
               if(a[j]<x){
                   x=a[j];
                   index=j;
               }
           }
      // 把最小值和當前順序遍歷的坑換位置
        a[index] = a[i];
        a[i] =x;
       }
    }

image.png

歸并排序O(logN)

利用遞歸思想形真，把大的分成兩份小的杉编，把小的排好序。再把排好序的小的組合成一個排好序的大的咆霜。依次遞歸 邓馒，則得到排好序的數(shù)據(jù)。

 static int[] guibing(int[] a){
        int[]  b;
        int[]  c=null;
        //循環(huán)終止條件裕便，不能再分了就中止
        if(a.length>1){
              b = new int[a.length/2];
              c =  new int[a.length-b.length];
            for(int x=0; x<a.length;x++){
                if(x<a.length/2){
                    b[x] =a[x];
                }else{
                    c[x-a.length/2] = a[x];
                }
            }
            //遞歸
           b= guibing(b);
           c= guibing(c);
        }else {
            b = new int[1];
            b[0]=a[0];

        }
        int[] d =new int[a.length];
        //組合
        merge(b,c,d);
        return d;
    }
    static int[] merge(int[] a,int[] b,int[] c){
        int aindex=0;
        int bindex=0;
        int cindex=0;
        // 處理只有一個的情況
        if(b==null){
            c[0]=a[0];
            return c;
        }
        //三個指針，三個數(shù)組偿衰。分散的數(shù)組進行組合
        while (aindex<a.length|| bindex<b.length){
                if(aindex ==a.length){
                     c[cindex++] =b[bindex++];
                     continue;
                }
                 if(bindex ==b.length){
                     c[cindex++] =a[aindex++];
                     continue;
                   }
                   if(a[aindex]<b[bindex]){
                        c[cindex++]= a[aindex++];
                   }else {
                       c[cindex++]= b[bindex++];
                   }
        }
        return c;
    } 

快速排序（Quicksort）O(logN)

一堆數(shù)據(jù)里挂疆，隨機拿一個數(shù)據(jù)作為標桿改览，比它大的放右邊，比它小的放左邊缤言。此時標桿把數(shù)據(jù)分為了兩堆宝当，再用上述思想進行遞歸，當最后一堆的數(shù)據(jù)為1個的時候胆萧，則表示已經(jīng)排好了庆揩。 快排核心思想就是分治和分區(qū)

 static void kuaisu(int[] a,int begin ,int end){
        if(begin>=end){
            return;
        }
        //取中間位置數(shù)據(jù)作為比較點
        int p =  (end-begin)/2+begin;
        for(int i =begin;i<=end;i++){
            //如果遍歷的數(shù)據(jù)比標桿數(shù)據(jù)大，并且位置在標桿的左邊
            if(a[i]>a[p] && i<p ){
                //把數(shù)據(jù)拿出來跌穗，在把整體向左移動订晌，把拿出來的數(shù)據(jù)放到最右邊
                //這樣就能保證大的數(shù)據(jù)在其右邊
                int f = a[i];
                for(int j=i; j<end;j++){
                    a[j] =a[j+1];
                }
                a[end] = f;
                //因為數(shù)據(jù)有移動，所以此處p的位置向左移動了一位蚌吸，且新數(shù)據(jù)還是在原來遍歷的位置
                p--;
                i--;
                continue;
            }
            //數(shù)據(jù)比標桿小锈拨，并且數(shù)據(jù)在標桿的右邊
            if(a[i]<a[p] && i>p){
                //與上同理
                int f = a[i];
                for(int k = i;k>begin;k--){
                    a[k] =a[k-1];
                }
                a[begin]=f;
                //這里不需要i++，因為原來數(shù)據(jù)的位置是被標桿替代了
                p++;
            }
        }
        kuaisu(a,begin,p-1);
        kuaisu(a,p+1,end);
    }

從上述例子可以看出羹唠，歸并排序和快速排序的思想都是分區(qū)分治奕枢。但是兩者的根本區(qū)別在于 歸并是從下往上排序，把子節(jié)點處理好佩微，組合成一個好的大節(jié)點缝彬。快速排序是從大節(jié)點粗粒度治理好哺眯，再分開兩份把小節(jié)點處理好谷浅。 歸并因為要組合，所以空間復雜度為O(n2)奶卓，快速排序可以在數(shù)據(jù)內(nèi)部進行位置交換壳贪，所以空間復雜度是O(1)。但是兩者的平均時間復雜都是O(logN)寝杖。 所以一般都是采取快速排序。

桶排序 O(n)

核心思想就是把數(shù)據(jù)分成小區(qū)間內(nèi)的互纯，且所有的小區(qū)間有序瑟幕，再讓每個小區(qū)間內(nèi)的數(shù)據(jù)有序，最后把有序的小區(qū)間合并留潦，就達到了排序的目的只盹。

桶排序，顧名思義兔院，會用到“桶”殖卑，核心思想是將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)再單獨進行排序坊萝。桶內(nèi)排完序之后孵稽，再把每個桶里的數(shù)據(jù)按照順序依次取出许起，組成的序列就是有序的了。

image.png

如果要排序的數(shù)據(jù)有 n 個菩鲜，我們把它們均勻地劃分到 m 個桶內(nèi)园细，每個桶里就有 k=n/m 個元素。每個桶內(nèi)部使用快速排序接校，時間復雜度為 O(k * logk)猛频。m 個桶排序的時間復雜度就是 O(m * k * logk)，因為 k=n/m蛛勉，所以整個桶排序的時間復雜度就是 O(n*log(n/m))鹿寻。當桶的個數(shù) m 接近數(shù)據(jù)個數(shù) n 時，log(n/m) 就是一個非常小的常量诽凌，這個時候桶排序的時間復雜度接近 O(n)毡熏。

桶排序看起來很優(yōu)秀，那它是不是可以替代我們之前講的排序算法呢皿淋？

答案當然是否定的招刹。為了讓你輕松理解桶排序的核心思想，我剛才做了很多假設窝趣。實際上疯暑，桶排序?qū)σ判驍?shù)據(jù)的要求是非常苛刻的哑舒。

首先妇拯，要排序的數(shù)據(jù)需要很容易就能劃分成 m 個桶，并且洗鸵，桶與桶之間有著天然的大小順序越锈。這樣每個桶內(nèi)的數(shù)據(jù)都排序完之后，桶與桶之間的數(shù)據(jù)不需要再進行排序膘滨。

其次甘凭，數(shù)據(jù)在各個桶之間的分布是比較均勻的。如果數(shù)據(jù)經(jīng)過桶的劃分之后火邓，有些桶里的數(shù)據(jù)非常多丹弱，有些非常少，很不平均铲咨，那桶內(nèi)數(shù)據(jù)排序的時間復雜度就不是常量級了躲胳。在極端情況下，如果數(shù)據(jù)都被劃分到一個桶里纤勒，那就退化為 O(nlogn) 的排序算法了坯苹。

桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲在外部磁盤中摇天，數(shù)據(jù)量比較大粹湃，內(nèi)存有限恐仑，無法將數(shù)據(jù)全部加載到內(nèi)存中。

比如說我們有 10GB 的訂單數(shù)據(jù)再芋，我們希望按訂單金額（假設金額都是正整數(shù)）進行排序菊霜，但是我們的內(nèi)存有限，只有幾百 MB济赎，沒辦法一次性把 10GB 的數(shù)據(jù)都加載到內(nèi)存中鉴逞。這個時候該怎么辦呢？

現(xiàn)在我來講一下司训，如何借助桶排序的處理思想來解決這個問題构捡。

我們可以先掃描一遍文件，看訂單金額所處的數(shù)據(jù)范圍壳猜。假設經(jīng)過掃描之后我們得到勾徽，訂單金額最小是 1 元，最大是 10 萬元统扳。我們將所有訂單根據(jù)金額劃分到 100 個桶里喘帚，第一個桶我們存儲金額在 1 元到 1000 元之內(nèi)的訂單，第二桶存儲金額在 1001 元到 2000 元之內(nèi)的訂單咒钟，以此類推吹由。每一個桶對應一個文件，并且按照金額范圍的大小順序編號命名（00朱嘴，01倾鲫，02…99）。

理想的情況下萍嬉，如果訂單金額在 1 到 10 萬之間均勻分布乌昔，那訂單會被均勻劃分到 100 個文件中，每個小文件中存儲大約 100MB 的訂單數(shù)據(jù)壤追，我們就可以將這 100 個小文件依次放到內(nèi)存中磕道，用快排來排序。等所有文件都排好序之后行冰，我們只需要按照文件編號捅厂，從小到大依次讀取每個小文件中的訂單數(shù)據(jù)，并將其寫入到一個文件中资柔，那這個文件中存儲的就是按照金額從小到大排序的訂單數(shù)據(jù)了。

不過撵割，你可能也發(fā)現(xiàn)了粉怕，訂單按照金額在 1 元到 10 萬元之間并不一定是均勻分布的 微猖，所以 10GB 訂單數(shù)據(jù)是無法均勻地被劃分到 100 個文件中的。有可能某個金額區(qū)間的數(shù)據(jù)特別多像街，劃分之后對應的文件就會很大，沒法一次性讀入內(nèi)存塔插。這又該怎么辦呢？

針對這些劃分之后還是比較大的文件，我們可以繼續(xù)劃分吃衅，比如，訂單金額在 1 元到 1000 元之間的比較多腾誉，我們就將這個區(qū)間繼續(xù)劃分為 10 個小區(qū)間徘层，1 元到 100 元，101 元到 200 元利职，201 元到 300 元…901 元到 1000 元趣效。如果劃分之后，101 元到 200 元之間的訂單還是太多猪贪，無法一次性讀入內(nèi)存跷敬，那就繼續(xù)再劃分，直到所有的文件都能讀入內(nèi)存為止热押。

計數(shù)排序（Counting sort） O(n)

計數(shù)排序其實是一種特殊的桶排序西傀，設置一個數(shù)組把桶的數(shù)據(jù)步長為1，然后一個曹對應一個桶桶癣，遍歷原來的數(shù)組拥褂，把每個桶應該放的數(shù)據(jù)量記錄下來，然后再遍歷桶數(shù)組鬼廓，把每個桶的值設置為前面所有的桶的和肿仑，那么每個桶記錄的就是當前值對應的數(shù)組角標位置。最后再遍歷原數(shù)組碎税，遍歷到的元素值所對應的桶的數(shù)據(jù)取出來作為角標存入新數(shù)組尤慰，如果沖突則往后移一位。這樣得到的新數(shù)組就是一個排好序的數(shù)組雷蹂。

基數(shù)排序（Radix sort） O(n)

我們再來看這樣一個排序問題伟端。假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序匪煌，你有什么比較快速的排序方法呢责蝠？
首先比較第一位，把順序排列好萎庭，再把第一位的數(shù)據(jù)看出一個桶霜医，把桶里的數(shù)據(jù)都進行排序，依此類推驳规，則把所有號碼都排序好了肴敛。

基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系医男，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大砸狞，那剩下的低位就不用比較了。除此之外镀梭，每一位的數(shù)據(jù)范圍不能太大刀森，要可以用線性排序算法來排序，否則报账，基數(shù)排序的時間復雜度就無法做到 O(n) 了研底。

總結

穩(wěn)定：相等的元素，其位置關系不會變笙什。
原地：不開辟新空間飘哨。

image.png

在算法的選擇中，要根據(jù)實際數(shù)據(jù)量的大小和特點琐凭，選擇合適的算法芽隆。譬如說，如果數(shù)據(jù)量比較小统屈，就可以選擇歸并排序胚吁，此時速度很快，雖然需要開辟一個空間來處理愁憔，但是由于數(shù)據(jù)量小腕扶，所以可以接受。當數(shù)據(jù)量大的時候就不可以選擇這種吨掌，快速排序會更好半抱。

如何優(yōu)化快速排序？
快排的最壞時間復雜度是O(n2) 膜宋，這種情況其實是標桿數(shù)取的不夠好窿侈，那么優(yōu)化快排其實就是如何取更合理的標桿。
最理想的分區(qū)點是：被分區(qū)點分開的兩個分區(qū)中秋茫，數(shù)據(jù)的數(shù)量差不多史简。

1. 三數(shù)取中：選頭、尾肛著、中三個數(shù)圆兵，選其中的中間數(shù)。
   2.隨機取數(shù)：每次都進行隨機取數(shù)枢贿，這樣每次取到極端數(shù)的概率將變得很小殉农。

二分查找O(logn)

二分查找的思想很簡單，每次都猜中間數(shù)局荚，然后進行比較大小统抬。

那么，基于這樣的思想，其實現(xiàn)有哪些限制?

1.數(shù)據(jù)必須是有順序的聪建，也就是從大到小或者從小到大。

2.其數(shù)據(jù)結構必須是數(shù)組茫陆，因為數(shù)組的元素隨機訪問是O(1)金麸，如果是鏈表其隨機訪問是O(n)，所以簿盅，如果數(shù)據(jù)使用鏈表存儲挥下，二分查找的時間復雜就會變得很高O(n)。實際上如果是鏈表的話桨醋，二分還不如直接遍歷棚瘟，直接遍歷會更快。

3.數(shù)據(jù)量太小沒必要二分查找喜最。

4.數(shù)據(jù)量太大也不能二分查找偎蘸，因為二分對數(shù)據(jù)的要求是數(shù)組，數(shù)組則必須開辟連續(xù)的內(nèi)存瞬内，如果數(shù)據(jù)量太大迷雪，譬如1G，內(nèi)存里是很難開辟一個連續(xù)的1G內(nèi)存的虫蝶。大部分時候內(nèi)存都是零散的章咧。

哈希算法

將任意長度的二進制值串映射為固定長度的二進制值串，這個映射的規(guī)則就是哈希算法能真，而通過原始數(shù)據(jù)映射之后得到的二進制值串就是哈希值赁严。

哈希算法的常見運用：安全加密、唯一標識粉铐、數(shù)據(jù)校驗疼约、散列函數(shù)、負載均衡秦躯、數(shù)據(jù)分片忆谓、分布式存儲。

安全加密

最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm踱承，MD5 消息摘要算法）和SHA（Secure Hash Algorithm倡缠，安全散列算法）。
無法做到0沖突茎活，必定會有重復的數(shù)據(jù)昙沦，只是概率很低。

唯一標識

我先來舉一個例子载荔。如果要在海量的圖庫中盾饮，搜索一張圖是否存在，我們不能單純地用圖片的元信息（比如圖片名稱）來比對，因為有可能存在名稱相同但圖片內(nèi)容不同丘损，或者名稱不同圖片內(nèi)容相同的情況普办。那我們該如何搜索呢？

我們可以給每一個圖片取一個唯一標識徘钥，或者說信息摘要衔蹲。比如，我們可以從圖片的二進制碼串開頭取 100 個字節(jié)呈础，從中間取 100 個字節(jié)舆驶，從最后再取 100 個字節(jié)，然后將這 300 個字節(jié)放到一塊而钞，通過哈希算法（比如 MD5）沙廉，得到一個哈希字符串，用它作為圖片的唯一標識臼节。通過這個唯一標識來判定圖片是否在圖庫中撬陵，這樣就可以減少很多工作量。

數(shù)據(jù)校驗

對傳輸?shù)臄?shù)據(jù)先進行hash運算官疲，算出哈希值袱结，傳輸結束后把哈希值傳給對方，對方接受到數(shù)據(jù)后途凫，然后對數(shù)據(jù)哈希垢夹，算出的哈希值與之對比，如果一致维费，則表示數(shù)據(jù)完整果元。

散列函數(shù)

我們前兩節(jié)講到，散列函數(shù)是設計一個散列表的關鍵犀盟。它直接決定了散列沖突的概率和散列表的性能而晒。不過，相對哈希算法的其他應用阅畴，散列函數(shù)對于散列算法沖突的要求要低很多倡怎。即便出現(xiàn)個別散列沖突，只要不是過于嚴重贱枣，我們都可以通過開放尋址法或者鏈表法解決监署。

不僅如此，散列函數(shù)對于散列算法計算得到的值纽哥，是否能反向解密也并不關心钠乏。散列函數(shù)中用到的散列算法，更加關注散列后的值是否能平均分布春塌，也就是晓避，一組數(shù)據(jù)是否能均勻地散列在各個槽中簇捍。除此之外，散列函數(shù)執(zhí)行的快慢俏拱，也會影響散列表的性能暑塑，所以，散列函數(shù)用的散列算法一般都比較簡單锅必，比較追求效率梯投。

負載均衡

我們知道，負載均衡算法有很多况毅，比如輪詢、隨機尔艇、加權輪詢等尔许。那如何才能實現(xiàn)一個會話粘滯（session sticky）的負載均衡算法呢？也就是說终娃，我們需要在同一個客戶端上味廊，在一次會話中的所有請求都路由到同一個服務器上。

最直接的方法就是棠耕，維護一張映射關系表余佛，這張表的內(nèi)容是客戶端 IP 地址或者會話 ID 與服務器編號的映射關系∏嫌客戶端發(fā)出的每次請求辉巡，都要先在映射表中查找應該路由到的服務器編號，然后再請求編號對應的服務器蕊退。這種方法簡單直觀郊楣，但也有幾個弊端：

如果客戶端很多，映射表可能會很大瓤荔，比較浪費內(nèi)存空間净蚤；

客戶端下線、上線输硝，服務器擴容今瀑、縮容都會導致映射失效，這樣維護映射表的成本就會很大点把；

如果借助哈希算法橘荠，這些問題都可以非常完美地解決。我們可以通過哈希算法愉粤，對客戶端 IP 地址或者會話 ID 計算哈希值砾医，將取得的哈希值與服務器列表的大小進行取模運算，最終得到的值就是應該被路由到的服務器編號衣厘。 這樣如蚜，我們就可以把同一個 IP 過來的所有請求压恒，都路由到同一個后端服務器上。

數(shù)據(jù)分片

如何快速判斷圖片是否在圖庫中错邦？上一節(jié)我們講過這個例子探赫，不知道你還記得嗎？當時我介紹了一種方法撬呢，即給每個圖片取唯一標識（或者信息摘要）伦吠，然后構建散列表。

假設現(xiàn)在我們的圖庫中有 1 億張圖片魂拦，很顯然毛仪，在單臺機器上構建散列表是行不通的。因為單臺機器的內(nèi)存有限芯勘，而 1 億張圖片構建散列表顯然遠遠超過了單臺機器的內(nèi)存上限箱靴。

我們同樣可以對數(shù)據(jù)進行分片，然后采用多機處理荷愕。我們準備 n 臺機器衡怀，讓每臺機器只維護某一部分圖片對應的散列表。我們每次從圖庫中讀取一個圖片安疗，計算唯一標識抛杨，然后與機器個數(shù) n 求余取模，得到的值就對應要分配的機器編號荐类，然后將這個圖片的唯一標識和圖片路徑發(fā)往對應的機器構建散列表怖现。

當我們要判斷一個圖片是否在圖庫中的時候，我們通過同樣的哈希算法掉冶，計算這個圖片的唯一標識真竖，然后與機器個數(shù) n 求余取模。假設得到的值是 k厌小，那就去編號 k 的機器構建的散列表中查找恢共。

現(xiàn)在，我們來估算一下璧亚，給這 1 億張圖片構建散列表大約需要多少臺機器讨韭。

散列表中每個數(shù)據(jù)單元包含兩個信息，哈希值和圖片文件的路徑癣蟋。假設我們通過 MD5 來計算哈希值透硝，那長度就是 128 比特，也就是 16 字節(jié)疯搅。文件路徑長度的上限是 256 字節(jié)濒生，我們可以假設平均長度是 128 字節(jié)。如果我們用鏈表法來解決沖突幔欧，那還需要存儲指針罪治，指針只占用 8 字節(jié)丽声。所以，散列表中每個數(shù)據(jù)單元就占用 152 字節(jié)（這里只是估算觉义，并不準確）雁社。

假設一臺機器的內(nèi)存大小為 2GB，散列表的裝載因子為 0.75晒骇，那一臺機器可以給大約 1000 萬（2GB*0.75/152）張圖片構建散列表霉撵。所以，如果要對 1 億張圖片構建索引洪囤，需要大約十幾臺機器徒坡。在工程中，這種估算還是很重要的瘤缩，能讓我們事先對需要投入的資源崭参、資金有個大概的了解，能更好地評估解決方案的可行性款咖。

實際上，針對這種海量數(shù)據(jù)的處理問題奄喂，我們都可以采用多機分布式處理铐殃。借助這種分片的思路，可以突破單機內(nèi)存跨新、CPU 等資源的限制富腊。

分布式存儲

redis的集群。
現(xiàn)在互聯(lián)網(wǎng)面對的都是海量的數(shù)據(jù)域帐、海量的用戶赘被。我們?yōu)榱颂岣邤?shù)據(jù)的讀取、寫入能力肖揣，一般都采用分布式的方式來存儲數(shù)據(jù)民假，比如分布式緩存。我們有海量的數(shù)據(jù)需要緩存龙优，所以一個緩存機器肯定是不夠的羊异。于是，我們就需要將數(shù)據(jù)分布在多臺機器上彤断。

該如何決定將哪個數(shù)據(jù)放到哪個機器上呢野舶？我們可以借用前面數(shù)據(jù)分片的思想，即通過哈希算法對數(shù)據(jù)取哈希值宰衙，然后對機器個數(shù)取模平道，這個最終值就是應該存儲的緩存機器編號。

但是供炼，如果數(shù)據(jù)增多一屋，原來的 10 個機器已經(jīng)無法承受了窘疮，我們就需要擴容了，比如擴到 11 個機器陆淀，這時候麻煩就來了考余。因為，這里并不是簡單地加個機器就可以了轧苫。

原來的數(shù)據(jù)是通過與 10 來取模的楚堤。比如 13 這個數(shù)據(jù)，存儲在編號為 3 這臺機器上含懊。但是新加了一臺機器中身冬，我們對數(shù)據(jù)按照 11 取模，原來 13 這個數(shù)據(jù)就被分配到 2 號這臺機器上了岔乔。

image.jpeg

因此酥筝，所有的數(shù)據(jù)都要重新計算哈希值，然后重新搬移到正確的機器上雏门。這樣就相當于嘿歌，緩存中的數(shù)據(jù)一下子就都失效了。所有的數(shù)據(jù)請求都會穿透緩存茁影，直接去請求數(shù)據(jù)庫宙帝。這樣就可能發(fā)生雪崩效應，壓垮數(shù)據(jù)庫募闲。

所以步脓，我們需要一種方法，使得在新加入一個機器后浩螺，并不需要做大量的數(shù)據(jù)搬移靴患。這時候，一致性哈希算法就要登場了要出。

假設我們有 k 個機器鸳君，數(shù)據(jù)的哈希值的范圍是 [0, MAX]。我們將整個范圍劃分成 m 個小區(qū)間（m 遠大于 k）患蹂，每個機器負責 m/k 個小區(qū)間相嵌。當有新機器加入的時候，我們就將某幾個小區(qū)間的數(shù)據(jù)况脆，從原來的機器中搬移到新的機器中饭宾。這樣，既不用全部重新哈希格了、搬移數(shù)據(jù)看铆，也保持了各個機器上數(shù)據(jù)數(shù)量的均衡。

堆排序O(nlogn)

利用堆這種數(shù)據(jù)結構的排序叫堆排序盛末。原來就是每次都選出一個堆頂元素弹惦，然后把堆頂元素屏蔽再選堆頂元素否淤。這么看，堆排序就是原地排序棠隐。切時間復雜度為O(logN)

堆排序的過程大致分解成兩個大的步驟石抡，建堆和排序。
1.建堆O(n)
建堆的目的是找出堆根助泽，也就是找出最大或者最小的數(shù)啰扛。
那么，我們可以從后往前比較嗡贺，拿最后一個數(shù)隐解。
因為葉子節(jié)點往下堆化只能自己跟自己比較，所以我們直接從第一個非葉子節(jié)點開始诫睬，依次堆化就行了煞茫。

image.png

所以 堆排序的時間復雜度為O（nlogN）

在實際開發(fā)中，為什么快速排序要比堆排序性能好谷扣？

第一點，堆排序數(shù)據(jù)訪問的方式?jīng)]有快速排序友好捎琐。
對于快速排序來說会涎，數(shù)據(jù)是順序訪問的。而對于堆排序來說瑞凑，數(shù)據(jù)是跳著訪問的末秃。 比如，堆排序中籽御，最重要的一個操作就是數(shù)據(jù)的堆化练慕。比如下面這個例子，對堆頂節(jié)點進行堆化技掏，會依次訪問數(shù)組下標是 1铃将，2，4哑梳，8 的元素劲阎，而不是像快速排序那樣，局部順序訪問鸠真，所以悯仙，這樣對 CPU 緩存是不友好的龄毡。

第二點，對于同樣的數(shù)據(jù)锡垄，在排序過程中沦零，堆排序算法的數(shù)據(jù)交換次數(shù)要多于快速排序。
我們在講排序的時候货岭，提過兩個概念路操，有序度和逆序度。對于基于比較的排序算法來說茴她，整個排序過程就是由兩個基本的操作組成的寻拂，比較和交換（或移動）≌衫危快速排序數(shù)據(jù)交換的次數(shù)不會比逆序度多祭钉。
但是堆排序的第一步是建堆，建堆的過程會打亂數(shù)據(jù)原有的相對先后順序己沛，導致原數(shù)據(jù)的有序度降低慌核。比如，對于一組已經(jīng)有序的數(shù)據(jù)來說申尼，經(jīng)過建堆之后垮卓，數(shù)據(jù)反而變得更無序了。

深度和廣度優(yōu)先搜索

深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法都是基于“圖”這種數(shù)據(jù)結構的师幕。

廣度優(yōu)先搜索（BFS）

廣度優(yōu)先就是根據(jù)原頂點粟按，一層層搜索，先搜索所有的一度霹粥，再搜索所有的二度灭将，再搜索三度。后控。庙曙。
結合我們的鄰接表，這種搜索的實現(xiàn)就要考慮幾個方面的問題：
1.基于外面一層的數(shù)據(jù)的搜索時候浩淘，需要對內(nèi)層數(shù)據(jù)進行過濾捌朴。
2.遍歷第n層數(shù)據(jù)的時候，怎么再一次找到N＋1層张抄。

所以我們在設計代碼的時候砂蔽，需要設置三個中間變量。數(shù)組visited 署惯，queue隊列察皇，數(shù)組prev
visited是用來記錄已經(jīng)被訪問的頂點，用來避免頂點被重復訪問。如果頂點 q 被訪問什荣，那相應的 visited[q] 會被設置為 true矾缓。

queue是一個隊列，用來存儲已經(jīng)被訪問稻爬、但相連的頂點還沒有被訪問的頂點嗜闻。因為廣度優(yōu)先搜索是逐層訪問的，也就是說桅锄，我們只有把第 k 層的頂點都訪問完成之后琉雳，才能訪問第 k+1 層的頂點。當我們訪問到第 k 層的頂點的時候友瘤，我們需要把第 k 層的頂點記錄下來翠肘，稍后才能通過第 k 層的頂點來找第 k+1 層的頂點。所以辫秧，我們用這個隊列來實現(xiàn)記錄的功能束倍。

prev用來記錄搜索路徑。當我們從頂點 s 開始盟戏，廣度優(yōu)先搜索到頂點 t 后绪妹，prev 數(shù)組中存儲的就是搜索的路徑。不過柿究，這個路徑是反向存儲的邮旷。prev[w] 存儲的是，頂點 w 是從哪個前驅(qū)頂點遍歷過來的蝇摸。比如婶肩，我們通過頂點 2 的鄰接表訪問到頂點 3，那 prev[3] 就等于 2貌夕。

image.png

其實也就是在一個頂點出隊的時候律歼，把它的關聯(lián)頂點更已搜索數(shù)組里的數(shù)據(jù)比較，沒有被搜索就入隊蜂嗽。
V 表示頂點的個數(shù)，E 表示邊的個數(shù)殃恒。
所以植旧，廣度優(yōu)先的時間復雜度為O（V＋E），空間復雜度為O（V）离唐。

深度優(yōu)先搜索

深度優(yōu)先就是一條路走到底病附，走不通再回頭試別的路。結合圖的特點亥鬓，不難發(fā)現(xiàn)完沪，這種的實現(xiàn)肯定是基于遞歸。
如果把圖看成一棵樹，那么深度優(yōu)先搜索其實就是樹的先序遍歷覆积。
既然這樣宽档，那么相對于廣度優(yōu)先吗冤，我們不需要隊列來進行數(shù)據(jù)消費，但是我們需要定義一個布爾變量覆致，來作為遞歸終止的條件煌妈。

所以,深度優(yōu)先每條邊最多會被訪問兩次声旺，一次是遍歷腮猖，一次是回退澈缺。所以姐赡，深度優(yōu)先搜索算法的時間復雜度是 O(E)项滑∏箍瘢空間復雜度是O（V）宋渔。