後端面試知識點總結 算法與資料結構

算法與資料結構

樹

樹在計算機科學中，是一種十分基礎的資料結構。幾乎所有作業系統都将檔案存放在樹狀結構中；幾乎所有的編譯器都要實作一個表達式樹；檔案壓縮所用到的哈夫曼算法（Huffman’s Algorithm）需要用到樹狀結構；資料庫所使用的B+tree則是一種相當複雜的樹狀結構。

二叉樹

二叉樹是n個節點的有限集合，該集合或者為空集，或者由一個根節點和兩根互不相交的、分别被稱為根節點的左子樹和右子樹組成。

特點：

• 每個節點最多有兩個子樹，是以二叉樹不存在出度大于2的結點
• 左子樹和右子樹是由順序的，次序不能颠倒
• 即使樹中某節點隻有一棵子樹，也要區分左子樹還是右子樹

二叉搜尋樹

可以提供對數時間O(logn)的元素插入和通路，二叉搜尋樹的放置規則為：任何節點的鍵值一定大于其左子樹中的每個節點的鍵值，并小于其右子樹中的每個節點的鍵值。

• 應用場景
  • 哈夫曼編碼
  • 海量資料并發查詢
  • stl容器中的set，multiset，map，multimap内部結構

平衡二叉搜尋樹

平衡的大緻意義為：沒有任何一個節點過深（深度過大）。

AVL

• 一種自平衡的二叉查找樹
• AVL樹中任何節點的兩個子樹的高度最大差是1，是以是完全平衡的
• 查找、插入和删除的平均和最壞情況都是O(logn)
• 經過修改的二叉樹可能失去平衡狀态（即左右高差大于1），就不是一棵AVL樹了，需要将其進行旋轉處理，使之重新平衡

為什麼AVL的高度差不超過1

• 平衡二叉樹是在二叉排序樹的基礎上引入的，就是為了解決二叉排序樹的不平衡性導緻的時間複雜度大大下降，不超過1的平衡二叉樹就保持住了BST的最好時間複雜度O(logn)

紅黑樹

規則：

• 每個節點不是紅色就是黑色
• 根節點為黑色
• 如果節點為紅色，其子節點必須為黑色
• 任一節點至NULL（樹尾端）的任何路徑，所含的黑色節點數必須相同

特點：

• 隻追求近似平衡（節點最大的深度<=最小深度*2）
• 在插入和删除節點時，翻轉次數遠小于平衡樹，是以在需要較多插入删除操作時，使用紅黑樹更好。
• 在查詢操作比較多時，使用平衡樹比較好，因為紅黑樹查詢的深度可能會大于平衡二叉樹

B樹，B+樹

• 一種多路查找樹
• B樹中所有節點都有指向記錄的指針，在非葉子節點種出現的索引項不會出現在葉子節點中；B+樹種隻有葉子節點會帶有指向記錄的指針。
• B+樹的所有葉子節點通過雙向連結清單連接配接在一起；B樹不連接配接
• B樹優點：對于在内部節點的資料，可以直接獲得，不必根據葉子節點來定位
• B+樹優點：1非葉子節點不會帶上指向記錄的指針，這樣一個塊中就可以容納更多的索引項；2葉子節點通過指針連接配接在一起，可以橫向周遊。

R樹，R+樹

R樹是一種多級平衡樹,它是B樹在多元空間上的擴充。在R樹中存放的資料并不是原始資料，而是這些資料的最小邊界矩形（MBR），空間對象的MBR被包含于R樹的葉結點中。在R樹空間索引中，設計一些虛拟的矩形目标，将一些空間位置相近的目标，包含在這個矩形内，這些虛拟的矩形作為空間索引，它含有所包含的空間對象的指針。虛拟矩形還可以進一步細分，即可以再套虛拟矩形形成多級空間索引。

在R樹的構造中，要求虛拟矩形一般盡可能少地重疊，并且一個空間對通常僅被一個虛拟矩形所包含。但空間對象千姿百态，它們的最小矩形範圍經常重疊。 R+ 改進R樹的空間索引，為了平衡，它允許虛拟矩形互相重疊，并允許一個空間目标被多個虛拟矩形所包含。

heap

堆實際是一個完全二叉樹，所有元素都可以将其儲存在一個vector之中，heap沒有疊代器。

max-heap的最大值在根節點，即在vector的第一個元素；min-heap的最小值在根節點，即在vector的第一個元素。

• 插入：先将元素插入到vector的尾部，然後進行上溯程式，将新節點與其父節點比較，如果鍵值大于父節點，就對換位置，否則一直上溯，直到不需對換或者到達根節點。
• 彈出：彈出操作取走根節點（實作中其實時将其移至底層容器vector的最後一個元素）之後，為了滿了完全二叉樹的特性，必須将最下一層最右邊的葉子節點拿掉，然後為其找一個适當的位置。
  • 執行下溯操作，即将根節點填入根節點，然後将它與它的兩個子節點作比較，并于較大的鍵值對調位置，一直下放到他的鍵值大于左右兩個子節點或者到達葉子節點為止。

hash

哈希表

• 哈希表（HashTable）也叫散清單，是根據關鍵碼值（key-value）而直接通路的資料結構
• 可以把關鍵碼值映射到表中的一個位置來通路記錄，加快查找的速度
• 這個映射函數叫做哈希函數（散列函數），存放記錄的數組叫做哈希表

• storage location(bucket)=H(key)

  ，

  H()

  被稱為哈希函數（散列函數），采用哈希技術将記錄存儲在一塊連續的存儲空間

哈希表的存取

• 存值：把key通過一個固定的哈希函數轉換為一個整形數字，然後對該數字長度進行取餘，取餘結果當作數組的下标，将value存儲在以該數字為下标的數組空間中
• 取值：再次使用哈希函數将key轉換為對應的數組下标，并定位到哈希表中擷取value

哈希的應用

• 加密算法：把不同長度的資訊轉換為雜亂的128位的編碼（MD5）
• 查找：當知道key值之後，可以直接計算出元素在集合中的位置

常見的哈希函數

• 直接定址法：取關鍵字key或者關鍵字中的某個線性函數值作為散列位址，即

  H(key)=key or H(key)=a*key+b; a,b=常數

• 除留餘數法：取關鍵字key被某個不大于哈希表大小m的數p求餘
• 數字分析法：當關鍵字位數大于位址位數，對關鍵字的各位分布進行分析，選出分布均勻的任意幾位作為哈希位址
• 平方取中法：計算關鍵字值的平方，然後取平均值中間幾位作為哈希位址
• 折疊法：将關鍵字分為位數相同的及部分，然後取這及部分的疊加和（進位舍去）作為哈希位址

哈希沖突

• 不同關鍵字通過相同哈希函數計算處相同的哈希位址，這種現象稱為哈希沖突
• 處理方法：
  • 鍊位址法：key相同的使用單連結清單連接配接（數組+連結清單）
  • 開放定址法：
    • 線性探測法：放到

      H(key)

      的下一個位置，

      Hi=(H(key)+i)%m

    • 二次探測法：放到計算位置後偏移量（1，2，3…）的二次方位址處
    • 随機探測法：

      Hi=(H(key)+random)%m

• STL中通常使用鍊位址法解決哈希沖突，使用的節點結構體為

• template <class Value>
  struct __hashtable_node{
  	__hashtable_node* next;
  	Value val;
  };
             

STL中的hash表

stl中的hash_table是用于實作無序關聯容器的底層結構。

其中哈希表裡的元素節點被稱為桶（bucket），桶内維護的是連結清單，但不是STL中的連結清單，而是自行維護的一個node。bucket聚合體也即hash_table使用vector實作。

• hash_table擴容時發生什麼：
  • 建立一個新桶，該桶是原來桶兩倍大最接近的質數（判斷質數：用n除以2到

    sqrt(n)

    的所有整數）
  • 将原來桶裡的數通過指針的轉換，插入到新桶裡
  • 通過swap函數将新桶和舊桶交換，銷毀舊桶

hash_map和map的差別

• map優點：有序，底層為紅黑樹，可以使map的很多操作以O(logN)的時間複雜度完成
• map缺點：空間占用高，因為内部使用RB-tree，雖然提高了運作效率，但每個節點都存儲了父節點、孩子節點和顔色。
• map适用于：對于有順序要求的場合
• hash_map優點：内部實作了哈希表，查找速度很快
• hash_map缺點：哈希表建立比較耗費時間
• hash_map适用于：對于查找問題，速度很高效

一緻性哈希

一緻性哈希（Distribute Hash Table, DHT）是一種哈希分布方式，其目的是為了客服傳統哈希分布在伺服器節點數量變化時大量資料遷移的問題。

基本原理

将哈希空間

[0,2^n-1], n=32

看成一個哈希環，每個伺服器節點都配知道哈希環上，每個資料對象通過哈希取模得到哈希值之後，存放到哈希環中順時針方向第一個大于該哈希值的伺服器節點上。如下圖将資料對象C插入到節點中，計算

Hash()%2^32

會得到一個節點，此時他的順時針方向第一個伺服器節點

Node C

，則将它放入節點

Node C

中。

一緻性哈希在增加（叢集擴容）或者删除伺服器節點（某節點當機）時隻會影響到哈希環中相鄰的節點。例如下圖中新增伺服器節點X，隻需要将在節點

Node B

和節點

Node X

之間的原本屬于

Node C

的資料對象C重新配置設定即可，對于其他資料對象A,B,D均沒有影響。

一緻性哈希中的資料傾斜問題

當一緻性Hash算法中的伺服器節點過少時，容易因為分布不均勻而造成資料傾斜（被緩存的對象大部分集中緩存在某一台伺服器上）的問題。如圖中，隻有兩台機器

D0, D1

，這兩台機器離的很近，那麼順時針第一個機器節點上将存有大量的資料；第二台機器上的資料很少。

• 使用虛拟節點解決資料傾斜問題，也就是每台機器節點會進行多次哈希，最終每個機器節點在哈喜歡上會有多個虛拟節點存在，使用這種方式來大大削弱甚至避免資料傾斜問題。同時資料定位算法不變，隻是多了一步虛拟節點到實際節點的映射，例如定位到“D1#1”、“D1#2”、“D1#3”三個虛拟節點的資料均定位到 D1 上。

排序算法

算法分類

十種常見排序算法可以分為兩大類：

• 比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以也稱為非線性時間比較類排序。
• 非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。

  

算法複雜度

歸并排序（Merge Sort）

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。

算法描述

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；
• 對這兩個子序列分别采用歸并排序；
• 将兩個排序好的子序列合并成一個最終的排序序列。

動圖示範

算法分析

歸并排序是一種穩定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是O(nlogn）的時間複雜度。代價是需要額外的記憶體空間。

快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

• 從數列中挑出一個元素，稱為 “基準”（pivot）；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
• 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

動圖示範

堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

算法描述

• 将初始待排序關鍵字序列(R1,R2….Rn)建構成大頂堆，此堆為初始的無序區；
• 将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
• 由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區(R1,R2,……Rn-1)調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。

動圖示範

計數排序（Counting Sort）

計數排序不是基于比較的排序算法，其核心在于将輸入的資料值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有确定範圍的整數。

算法描述

• 找出待排序的數組中最大和最小的元素；
• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1。

動圖示範

桶排序（Bucket Sort）

桶排序是計數排序的更新版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。桶排序 (Bucket sort)的工作的原理：假設輸入資料服從均勻分布，将資料分到有限數量的桶裡，每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排）。

算法描述

• 設定一個定量的數組當作空桶；
• 周遊輸入資料，并且把資料一個一個放到對應的桶裡去；
• 對每個不是空的桶進行排序；
• 從不是空的桶裡把排好序的資料拼接起來。

圖檔示範