1. 語(yǔ)言基礎(chǔ)
1.1 C++的四種類型轉(zhuǎn)換：
-
const_cast=> 用于將const變量轉(zhuǎn)為非const; -
static_cast=> 用于各種隱式轉(zhuǎn)換，比如非const轉(zhuǎn)const，void*轉(zhuǎn)指針等, static_cast能用于多態(tài)向上轉(zhuǎn)化，如果向下轉(zhuǎn)能成功但是不安全，結(jié)果未知； -
dynamic_cast=> 用于動(dòng)態(tài)類型轉(zhuǎn)換（ 適用于包含虛函數(shù)的類 ） ，適用于指針和引用； -
reinterpret_cast=> 幾乎什么都可以轉(zhuǎn)，比如將int轉(zhuǎn)指針，可能會(huì)出問(wèn)題，盡量少用； - 為什么不用 C 風(fēng)格的強(qiáng)制類型轉(zhuǎn)換 => C的強(qiáng)制轉(zhuǎn)換表面上看起來(lái)功能強(qiáng)大什么都能轉(zhuǎn)，但是轉(zhuǎn)化不夠明確，不能進(jìn)行錯(cuò)誤檢查，容易出錯(cuò)。
1.2 海倫公式求三角形面積：
已知三角形三邊a, b, c
1.3 四種智能指針
-
auto_ptr（c++98的方案，cpp11已經(jīng)拋棄） => 采用所有權(quán)模式；（ 所有權(quán)可剝奪 ） -
unique_ptr=> 用于替換auto_ptr=> 占式擁有或嚴(yán)格擁有概念，保證同一時(shí)間內(nèi)只有一個(gè)智能指針可以指向該對(duì)象 -
shared_ptr=> 引用計(jì)數(shù)解決方案 -
weak_ptr=> 一種弱引用，不會(huì)增加對(duì)象的引用計(jì)數(shù)（ 解決 shared_ptr 相互引用問(wèn)題 ）
1.4 fork
- 寫時(shí)復(fù)制；
- 子進(jìn)程中返回大于0的pid_t，父進(jìn)程中返回0；
1.5 靜態(tài)函數(shù)和虛函數(shù)：
- 靜態(tài)函數(shù)在編譯時(shí)就確定調(diào)用時(shí)機(jī)；
- 虛函數(shù)在運(yùn)行時(shí)動(dòng)態(tài)綁定，因?yàn)椴捎昧颂摵瘮?shù)表，所以在調(diào)用時(shí)會(huì)增加內(nèi)存開(kāi)銷。
1.6 const
- 對(duì)于局部對(duì)象，常量存放在棧區(qū)，對(duì)于全局對(duì)象，常量存放在全局/靜態(tài)存儲(chǔ)區(qū)，對(duì)于字面值常量，常量存放在常量存儲(chǔ)區(qū)；
- const 可用于函數(shù)重載
- 指向常量的指針，和常量指針：
-
const char *p1=> p1 可以改變指向，但是不能修改所指的對(duì)象 -
char *const p2=> p2 本身是一個(gè)常量指針，不可以改變指向
-
1.7 malloc 和 new
-
malloc/free是C語(yǔ)言的庫(kù)函數(shù)，需指明申請(qǐng)的空間大小 => 對(duì)于類類型，不會(huì)調(diào)用構(gòu)造和析構(gòu)函數(shù)； -
new/delete是C++的關(guān)鍵字，會(huì)調(diào)用構(gòu)造和析構(gòu)函數(shù)
1.8 C++ 引用、移動(dòng)、轉(zhuǎn)發(fā)
2. 數(shù)據(jù)結(jié)構(gòu)
2.1 紅黑樹(shù)
2.2 map和set底層都是用紅黑樹(shù)（RB-tree）實(shí)現(xiàn)的;
unordered map 底層用的是 Hash 表
2.3 STL迭代器刪除元素：
對(duì)于序列容器vector,deque來(lái)說(shuō)，使用erase(itertor)后，后邊的每個(gè)元素的迭代器都會(huì)失效，但是后邊每個(gè)元素都會(huì)往前移動(dòng)一個(gè)位置，但是 erase會(huì)返回下一個(gè)有效的迭代器 ；
對(duì)于關(guān)聯(lián)容器map set來(lái)說(shuō)，使用了erase(iterator)后，當(dāng)前元素的迭代器失效，但是其結(jié)構(gòu)是紅黑樹(shù)，刪除當(dāng)前元素的，不會(huì)影響到下一個(gè)元素的迭代器，所以在 調(diào)用erase之前，記錄下一個(gè)元素的迭代器即可 ；
對(duì)于list來(lái)說(shuō)，它使用了不連續(xù)分配的內(nèi)存，并且它的erase方法也會(huì)返回下一個(gè)有效的iterator，因此上面兩種正確的方法都可以使用。
3. 操作系統(tǒng)
3.1 I/O模式
-
阻塞I/O（blocking IO）
preview -
非阻塞I/O（nonblocking IO）
preview -
I/O多路復(fù)用（IO multiplexing）
preview 信號(hào)驅(qū)動(dòng)I/O（signal driven IO）=> 不常用
-
異步I/O（asynchronous IO）
preview
3.2 blocking和non-blocking的區(qū)別
調(diào)用blocking IO會(huì)一直block住對(duì)應(yīng)的進(jìn)程直到操作完成，而non-blocking IO在kernel還準(zhǔn)備數(shù)據(jù)的情況下會(huì)立刻返回。
3.3 synchronous IO和asynchronous IO的區(qū)別
兩者的區(qū)別就在于synchronous IO做”IO operation”的時(shí)候會(huì)將process阻塞。按照這個(gè)定義，之前所述的blocking IO，non-blocking IO，IO multiplexing都屬于synchronous IO。
3.4 I/O多路復(fù)用 => select、poll、epoll
-
select
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); -
poll
struct pollfd { int fd; /* file descriptor */ short events; /* requested events to watch */ short revents; /* returned events witnessed */ }; int poll (struct pollfd *fds, unsigned int nfds, int timeout); -
epoll
https://zhuanlan.zhihu.com/p/63179839
=> epoll 采用紅黑樹(shù)和雙向鏈表實(shí)現(xiàn)
int epoll_create(int size)；//創(chuàng)建一個(gè)epoll的句柄，size用來(lái)告訴內(nèi)核這個(gè)監(jiān)聽(tīng)的數(shù)目一共有多大 int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)； int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
3.5 進(jìn)程間通信方式
-
管道通信 => 半雙工
- 匿名管道 => 只能用于有親緣關(guān)系的進(jìn)程之間；
- 命名管道 => 允許沒(méi)有親緣關(guān)系的的進(jìn)程之間進(jìn)行半雙工的管道通信。
-
消息隊(duì)列：
消息隊(duì)列( message queue ) ： 消息隊(duì)列是由消息的鏈表，存放在內(nèi)核中并由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)。消息隊(duì)列克服了信號(hào)傳遞信息少、管道只能承載無(wú)格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。
-
信號(hào)量通信：
信號(hào)量( semophore ) ： 信號(hào)量是一個(gè)計(jì)數(shù)器，可以用來(lái)控制多個(gè)進(jìn)程對(duì)共享資源的訪問(wèn)。它常作為一種鎖機(jī)制，防止某進(jìn)程正在訪問(wèn)共享資源時(shí)，其他進(jìn)程也訪問(wèn)該資源。因此，主要作為進(jìn)程間以及同一進(jìn)程內(nèi)不同線程之間的同步手段。
-
信號(hào)：
信號(hào) ( sinal ) ： 信號(hào)是一種比較復(fù)雜的通信方式，用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生。
-
共享內(nèi)存：
共享內(nèi)存( shared memory ) ：共享內(nèi)存就是映射一段能被其他進(jìn)程所訪問(wèn)的內(nèi)存，這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建，但多個(gè)進(jìn)程都可以訪問(wèn)。共享內(nèi)存是最快的 IPC 方式，它是針對(duì)其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的。它往往與其他通信機(jī)制，如信號(hào)量，配合使用，來(lái)實(shí)現(xiàn)進(jìn)程間的同步和通信。
套接字
3.6 虛擬地址空間
為了防止不同進(jìn)程同一時(shí)刻在物理內(nèi)存中運(yùn)行而對(duì)物理內(nèi)存的爭(zhēng)奪和踐踏，采用了虛擬內(nèi)存。
虛擬內(nèi)存技術(shù)使得不同進(jìn)程在運(yùn)行過(guò)程中，它所看到的是自己獨(dú)自占有了當(dāng)前系統(tǒng)的4G內(nèi)存。所有進(jìn)程共享同一物理內(nèi)存，每個(gè)進(jìn)程只把自己目前需要的虛擬內(nèi)存空間映射并存儲(chǔ)到物理內(nèi)存上。 事實(shí)上，在每個(gè)進(jìn)程創(chuàng)建加載時(shí)，內(nèi)核只是為進(jìn)程“創(chuàng)建”了虛擬內(nèi)存的布局，具體就是初始化進(jìn)程控制表中內(nèi)存相關(guān)的鏈表，實(shí)際上并不立即就把虛擬內(nèi)存對(duì)應(yīng)位置的程序數(shù)據(jù)和代碼（比如.text .data段）拷貝到物理內(nèi)存中，只是建立好虛擬內(nèi)存和磁盤文件之間的映射就好（叫做存儲(chǔ)器映射），等到運(yùn)行到對(duì)應(yīng)的程序時(shí)，才會(huì)通過(guò)缺頁(yè)異常，來(lái)拷貝數(shù)據(jù)。還有進(jìn)程運(yùn)行過(guò)程中，要?jiǎng)討B(tài)分配內(nèi)存，比如malloc時(shí)，也只是分配了虛擬內(nèi)存，即為這塊虛擬內(nèi)存對(duì)應(yīng)的頁(yè)表項(xiàng)做相應(yīng)設(shè)置，當(dāng)進(jìn)程真正訪問(wèn)到此數(shù)據(jù)時(shí)，才引發(fā)缺頁(yè)異常。
請(qǐng)求分頁(yè)系統(tǒng)、請(qǐng)求分段系統(tǒng)和請(qǐng)求段頁(yè)式系統(tǒng)都是針對(duì)虛擬內(nèi)存的，通過(guò)請(qǐng)求實(shí)現(xiàn)內(nèi)存與外存的信息置換。
-
虛擬內(nèi)存的好處：
擴(kuò)大地址空間；
內(nèi)存保護(hù)：每個(gè)進(jìn)程運(yùn)行在各自的虛擬內(nèi)存地址空間，互相不能干擾對(duì)方。虛存還對(duì)特定的內(nèi)存地址提供寫保護(hù)，可以防止代碼或數(shù)據(jù)被惡意篡改。
公平內(nèi)存分配。采用了虛存之后，每個(gè)進(jìn)程都相當(dāng)于有同樣大小的虛存空間。
當(dāng)進(jìn)程通信時(shí)，可采用虛存共享的方式實(shí)現(xiàn)。
當(dāng)不同的進(jìn)程使用同樣的代碼時(shí)，比如庫(kù)文件中的代碼，物理內(nèi)存中可以只存儲(chǔ)一份這樣的代碼，不同的進(jìn)程只需要把自己的虛擬內(nèi)存映射過(guò)去就可以了，節(jié)省內(nèi)存
虛擬內(nèi)存很適合在多道程序設(shè)計(jì)系統(tǒng)中使用，許多程序的片段同時(shí)保存在內(nèi)存中。當(dāng)一個(gè)程序等待它的一部分讀入內(nèi)存時(shí)，可以把CPU交給另一個(gè)進(jìn)程使用。在內(nèi)存中可以保留多個(gè)進(jìn)程，系統(tǒng)并發(fā)度提高
在程序需要分配連續(xù)的內(nèi)存空間的時(shí)候，只需要在虛擬內(nèi)存空間分配連續(xù)空間，而不需要實(shí)際物理內(nèi)存的連續(xù)空間，可以利用碎片
-
虛擬內(nèi)存的代價(jià)：
虛存的管理需要建立很多數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)要占用額外的內(nèi)存
虛擬地址到物理地址的轉(zhuǎn)換，增加了指令的執(zhí)行時(shí)間。
頁(yè)面的換入換出需要磁盤I/O，這是很耗時(shí)的
如果一頁(yè)中只有一部分?jǐn)?shù)據(jù)，會(huì)浪費(fèi)內(nèi)存。
3.7 操作系統(tǒng)中程序的內(nèi)存結(jié)構(gòu)
text段（代碼段）：存放程序執(zhí)行代碼的一塊內(nèi)存區(qū)域。這部分區(qū)域的大小在程序運(yùn)行前就已經(jīng)確定，并且內(nèi)存區(qū)域?qū)儆谥蛔x。在代碼段中，也有可能包含一些只讀的常數(shù)變量；
-
data段（數(shù)據(jù)段）：存放程序中已初始化的全局變量的一塊內(nèi)存區(qū)域。數(shù)據(jù)段也屬于靜態(tài)內(nèi)存分配；
- 已初始化數(shù)據(jù)區(qū)；
- BBS（未初始化區(qū)）=> 的內(nèi)容并不存放在磁盤上的程序文件中。其原因是內(nèi)核在程序開(kāi)始運(yùn)行前將它們?cè)O(shè)置為0。需要存放在程序文件中的只有正文段和初始化數(shù)據(jù)段
-
棧區(qū)（運(yùn)行時(shí)）：
由編譯器自動(dòng)釋放，存放函數(shù)的參數(shù)值、局部變量等。每當(dāng)一個(gè)函數(shù)被調(diào)用時(shí)，該函數(shù)的返回類型和一些調(diào)用的信息被存放到棧中。然后這個(gè)被調(diào)用的函數(shù)再為他的自動(dòng)變量和臨時(shí)變量在棧上分配空間。每調(diào)用一個(gè)函數(shù)一個(gè)新的棧就會(huì)被使用。棧區(qū)是從高地址位向低地址位增長(zhǎng)的，是一塊連續(xù)的內(nèi)存區(qū)域，最大容量是由系統(tǒng)預(yù)先定義好的，申請(qǐng)的棧空間超過(guò)這個(gè)界限時(shí)會(huì)提示溢出，用戶能從棧中獲取的空間較小
-
堆區(qū)（運(yùn)行時(shí)）：
用于動(dòng)態(tài)分配內(nèi)存，位于BSS和棧中間的地址區(qū)域。由程序員申請(qǐng)分配和釋放。堆是從低地址位向高地址位增長(zhǎng)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。頻繁的malloc/free造成內(nèi)存空間的不連續(xù)，產(chǎn)生碎片。當(dāng)申請(qǐng)堆空間時(shí)庫(kù)函數(shù)是按照一定的算法搜索可用的足夠大的空間。因此堆的效率比棧要低的多
3.8 死鎖發(fā)生的條件和解決辦法
3.8.1 死鎖發(fā)生條件
互斥條件：進(jìn)程對(duì)所分配到的資源不允許其他進(jìn)程訪問(wèn)，若其他進(jìn)程訪問(wèn)該資源，只能等待，直至占有該資源的進(jìn)程使用完成后釋放該資源；
請(qǐng)求和保持條件：進(jìn)程獲得一定的資源后，又對(duì)其他資源發(fā)出請(qǐng)求，但是該資源可能被其他進(jìn)程占有，此時(shí)請(qǐng)求阻塞，但該進(jìn)程不會(huì)釋放自己已經(jīng)占有的資源
不可剝奪條件：進(jìn)程已獲得的資源，在未完成使用之前，不可被剝奪，只能在使用后自己釋放
環(huán)路等待條件：進(jìn)程發(fā)生死鎖后，必然存在一個(gè)進(jìn)程-資源之間的環(huán)形鏈
3.8.2 死鎖解決
- 資源一次性分配，從而剝奪請(qǐng)求和保持條件
- 可剝奪資源：即當(dāng)進(jìn)程新的資源未得到滿足時(shí)，釋放已占有的資源，從而破壞不可剝奪的條件
- 資源有序分配法：系統(tǒng)給每類資源賦予一個(gè)序號(hào)，每個(gè)進(jìn)程按編號(hào)遞增的請(qǐng)求資源，釋放則相反，從而破壞環(huán)路等待的條件
3.9 虛擬內(nèi)存置換方式
-
FIFO
=> 缺點(diǎn)：無(wú)法體現(xiàn)頁(yè)面冷熱信息；
-
LFU => 按引用計(jì)數(shù)排序
=> 缺點(diǎn)：需要排序；緩存顛簸；
-
LRU => 使用棧，新頁(yè)面或者命中頁(yè)放到棧底，每次淘汰棧頂元素
=> 優(yōu)點(diǎn)：LRU算法對(duì)熱點(diǎn)數(shù)據(jù)命中率是很高的
=> 缺點(diǎn)：
- 緩存顛簸，當(dāng)緩存（1，2，3）滿了，之后數(shù)據(jù)訪問(wèn)（0，3，2，1，0，3，2，1。。。）；
- 緩存污染，突然大量偶發(fā)性的數(shù)據(jù)訪問(wèn)，會(huì)讓內(nèi)存中存放大量冷數(shù)據(jù)
-
LRU-K（LRU-2、LRU-3）
img數(shù)據(jù)第一次被訪問(wèn)，加入到訪問(wèn)歷史列表；
如果數(shù)據(jù)在訪問(wèn)歷史列表里后沒(méi)有達(dá)到K次訪問(wèn)，則按照一定規(guī)則（FIFO，LRU）淘汰；
當(dāng)訪問(wèn)歷史隊(duì)列中的數(shù)據(jù)訪問(wèn)次數(shù)達(dá)到K次后，將數(shù)據(jù)索引從歷史隊(duì)列刪除，將數(shù)據(jù)移到緩存隊(duì)列中，并緩存此數(shù)據(jù)，緩存隊(duì)列重新按照時(shí)間排序；
緩存數(shù)據(jù)隊(duì)列中被再次訪問(wèn)后，重新排序；
需要淘汰數(shù)據(jù)時(shí)，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問(wèn)離現(xiàn)在最久”的數(shù)據(jù)。
LRU-K具有LRU的優(yōu)點(diǎn)，同時(shí)能夠避免LRU的缺點(diǎn)，實(shí)際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會(huì)高，但適應(yīng)性差，需要大量的數(shù)據(jù)訪問(wèn)才能將歷史訪問(wèn)記錄清除掉。
【命中率】
LRU-K降低了“緩存污染”帶來(lái)的問(wèn)題，命中率比LRU要高。
【復(fù)雜度】
LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列，算法復(fù)雜度和代價(jià)比較高。
【代價(jià)】
由于LRU-K還需要記錄那些被訪問(wèn)過(guò)、但還沒(méi)有放入緩存的對(duì)象，因此內(nèi)存消耗會(huì)比LRU要多；
當(dāng)數(shù)據(jù)量很大的時(shí)候，內(nèi)存消耗會(huì)比較可觀。
LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序，也可以即時(shí)排序），CPU消耗比LRU要高
-
2Q
類似LRU-2。使用一個(gè)FIFO隊(duì)列和一個(gè)LRU隊(duì)列
3.10 進(jìn)程狀態(tài)轉(zhuǎn)換圖
3.11 僵尸進(jìn)程
- 孤兒進(jìn)程：父進(jìn)程退出，子進(jìn)程還在運(yùn)行，即成為孤兒進(jìn)程；
- 僵尸進(jìn)程：子進(jìn)程退出，父進(jìn)程并沒(méi)有調(diào)用wait或waitpid獲取子進(jìn)程的狀態(tài)信息，那么子進(jìn)程的進(jìn)程描述符仍然保存在系統(tǒng)中。這種進(jìn)程稱之為僵尸進(jìn)程。
- 如果父進(jìn)程未退出，且沒(méi)有處理僵尸進(jìn)程，僵尸進(jìn)程會(huì)一直占用空間，如果父進(jìn)程退出，則會(huì)有init進(jìn)程接管孤兒進(jìn)程，進(jìn)而處理進(jìn)程狀態(tài)信息
3.12 虛擬內(nèi)存、物理內(nèi)存和共享內(nèi)存
https://cloud.tencent.com/developer/article/1493029
3.13 Linux內(nèi)存管理
https://zhuanlan.zhihu.com/p/149581303
4. 數(shù)據(jù)庫(kù)
4.1 數(shù)據(jù)庫(kù)事務(wù)
事務(wù)（Transaction）是由一系列對(duì)系統(tǒng)中數(shù)據(jù)進(jìn)行訪問(wèn)與更新的操作所組成的一個(gè)程序執(zhí)行邏輯單元。事務(wù)是DBMS中最基礎(chǔ)的單位，事務(wù)不可分割
事務(wù)具有4個(gè)基本特征，分別是：原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Duration），簡(jiǎn)稱ACID
-
原子性
原子性是指事務(wù)包含的所有操作要么全部成功，要么全部失敗回滾。
-
一致性
事務(wù)必須使數(shù)據(jù)庫(kù)從一個(gè)一致性狀態(tài)變換到另一個(gè)一致性狀態(tài)。
-
隔離性
隔離性是當(dāng)多個(gè)用戶并發(fā)訪問(wèn)數(shù)據(jù)庫(kù)時(shí)，比如操作同一張表時(shí)，數(shù)據(jù)庫(kù)為每一個(gè)用戶開(kāi)啟的事務(wù)，不能被其他事務(wù)的操作所干擾，多個(gè)并發(fā)事務(wù)之間要相互隔離，有四種隔離級(jí)別
-
Read uncommitted（讀未提交）
一個(gè)事務(wù)可以讀取另一個(gè)事務(wù)未提交的數(shù)據(jù) => 存在臟讀問(wèn)題
-
Read committed（讀已提交）
一個(gè)事務(wù)要等另一個(gè)事務(wù)提交后才能讀取數(shù)據(jù) => 解決臟讀，存在不可重復(fù)讀問(wèn)題
-
Repeatable read（重復(fù)讀）
就是在開(kāi)始讀取數(shù)據(jù)（事務(wù)開(kāi)啟）時(shí)，不再允許修改操作 => 解決臟讀、不可重復(fù)讀問(wèn)題，存在幻讀問(wèn)題
不允許修改操作，但是允許插入操作
-
Serializable（序列化）=> 最高級(jí)別的事務(wù)隔離
事務(wù)串行化順序執(zhí)行，可以避免臟讀、不可重復(fù)讀與幻讀。但是這種事務(wù)隔離級(jí)別效率低下，比較耗數(shù)據(jù)庫(kù)性能，一般不使用
-
-
持久性
持久性是指一個(gè)事務(wù)一旦被提交了，那么對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)的改變就是永久性的，即便是在數(shù)據(jù)庫(kù)系統(tǒng)遇到故障的情況下也不會(huì)丟失提交事務(wù)的操作
4.2 數(shù)據(jù)庫(kù)索引
數(shù)據(jù)庫(kù)索引是為了增加查詢速度而對(duì)表字段附加的一種標(biāo)識(shí)，是對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)。DB在執(zhí)行一條Sql語(yǔ)句的時(shí)候，默認(rèn)的方式是根據(jù)搜索條件進(jìn)行全表掃描，遇到匹配條件的就加入搜索結(jié)果集合。如果我們對(duì)某一字段增加索引，查詢時(shí)就會(huì)先去索引列表中一次定位到特定值的行數(shù)，大大減少遍歷匹配的行數(shù)，所以能明顯增加查詢的速度。
- 優(yōu)點(diǎn)：
- 通過(guò)創(chuàng)建唯一性索引，可以保證數(shù)據(jù)庫(kù)表中每一行數(shù)據(jù)的唯一性；
- 可以大大加快數(shù)據(jù)的檢索速度，這也是創(chuàng)建索引的最主要的原因；
- 在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，同樣可以顯著減少查詢中分組和排序的時(shí)間；
- 通過(guò)使用索引，可以在查詢的過(guò)程中，使用優(yōu)化隱藏器，提高系統(tǒng)的性能。
- 缺點(diǎn)：
- 創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間，這種時(shí)間隨著數(shù)據(jù)量的增加而增加；
- 索引需要占物理空間，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間，如果要建立聚簇索引，那么需要的空間就會(huì)更大；
- 當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)的維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
- 添加索引原則：
- 在查詢中很少使用或者參考的列不應(yīng)該創(chuàng)建索引；
- 只有很少數(shù)據(jù)值的列也不應(yīng)該增加索引；
- 定義為text、image和bit數(shù)據(jù)類型的列不應(yīng)該增加索引；
- 當(dāng)修改性能遠(yuǎn)遠(yuǎn)大于檢索性能時(shí)，不應(yīng)該創(chuàng)建索引。
4.3 唯一索引和普通索引
唯一索引和普通索引的區(qū)別：https://blog.csdn.net/Srodong/article/details/88838046
4.4 聚簇索引和非聚簇索引
- 聚簇索引：將數(shù)據(jù)存儲(chǔ)與索引放到了一塊，找到索引也就找到了數(shù)據(jù)
- 非聚簇索引：將數(shù)據(jù)存儲(chǔ)于索引分開(kāi)結(jié)構(gòu)，索引結(jié)構(gòu)的葉子節(jié)點(diǎn)指向了數(shù)據(jù)的對(duì)應(yīng)行，myisam通過(guò)key_buffer把索引先緩存到內(nèi)存中，當(dāng)需要訪問(wèn)數(shù)據(jù)時(shí)（通過(guò)索引訪問(wèn)數(shù)據(jù)），在內(nèi)存中直接搜索索引，然后通過(guò)索引找到磁盤相應(yīng)數(shù)據(jù)，這也就是為什么索引不在key buffer命中時(shí)，速度慢的原因
- InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹(shù)中，而行數(shù)據(jù)就儲(chǔ)存在葉子節(jié)點(diǎn)上，若使用"where id = 14"這樣的條件查找主鍵，則按照B+樹(shù)的檢索算法即可查找到對(duì)應(yīng)的葉節(jié)點(diǎn)，之后獲得行數(shù)據(jù)。
- 若對(duì)Name列進(jìn)行條件搜索，則需要兩個(gè)步驟：第一步在輔助索引B+樹(shù)中檢索Name，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵。第二步使用主鍵在主索引B+樹(shù)種再執(zhí)行一次B+樹(shù)檢索操作，最終到達(dá)葉子節(jié)點(diǎn)即可獲取整行數(shù)據(jù)。（重點(diǎn)在于通過(guò)其他鍵需要建立輔助索引）
MyISM使用的是非聚簇索引，非聚簇索引的兩棵B+樹(shù)看上去沒(méi)什么不同，節(jié)點(diǎn)的結(jié)構(gòu)完全一致只是存儲(chǔ)的內(nèi)容不同而已，主鍵索引B+樹(shù)的節(jié)點(diǎn)存儲(chǔ)了主鍵，輔助鍵索引B+樹(shù)存儲(chǔ)了輔助鍵。表數(shù)據(jù)存儲(chǔ)在獨(dú)立的地方，這兩顆B+樹(shù)的葉子節(jié)點(diǎn)都使用一個(gè)地址指向真正的表數(shù)據(jù)，對(duì)于表數(shù)據(jù)來(lái)說(shuō)，這兩個(gè)鍵沒(méi)有任何差別。由于索引樹(shù)是獨(dú)立的，通過(guò)輔助鍵檢索無(wú)需訪問(wèn)主鍵的索引樹(shù)。
4.5 索引覆蓋
如果要查詢的字段都建立過(guò)索引，那么引擎會(huì)直接在索引表中查詢而不會(huì)訪問(wèn)原始數(shù)據(jù)（否則只要有一個(gè)字段沒(méi)有建立索引就會(huì)做全表掃描），這叫索引覆蓋。因此我們需要盡可能的在select后只寫必要的查詢字段，以增加索引覆蓋的幾率。
這里值得注意的是不要想著為每個(gè)字段建立索引，因?yàn)閮?yōu)先使用索引的優(yōu)勢(shì)就在于其體積小。
4.6 索引的類型
主鍵索引 : 數(shù)據(jù)列不允許重復(fù)，不允許為NULL，一個(gè)表只能有一個(gè)主鍵。
-
唯一索引 : 數(shù)據(jù)列不允許重復(fù)，允許為NULL值，一個(gè)表允許多個(gè)列創(chuàng)建唯一索引。
可以通過(guò)
ALTER TABLE table_name ADD UNIQUE (column);創(chuàng)建唯一索引可以通過(guò)
ALTER TABLE table_name ADD UNIQUE (column1,column2);創(chuàng)建唯一組合索引
-
普通索引 : 基本的索引類型，沒(méi)有唯一性的限制，允許為NULL值。
- 可以通過(guò)
ALTER TABLE table_name ADD INDEX index_name (column);創(chuàng)建普通索引 - 可以通過(guò)
ALTER TABLE table_name ADD INDEX index_name(column1, column2, column3);創(chuàng)建組合索引
- 可以通過(guò)
-
全文索引 ：是目前搜索引擎使用的一種關(guān)鍵技術(shù)。
- 可以通過(guò)
ALTER TABLE table_name ADD FULLTEXT (column);創(chuàng)建全文索引
- 可以通過(guò)
4.7 MySQL 最左前綴匹配原則
因?yàn)榻⒙?lián)合索引（a, b, c）時(shí)，底層是B+樹(shù)實(shí)現(xiàn)的，所以首先會(huì)按照a的順序建立樹(shù)，在a相等的情況下b才是有序的，在a和b相等的情況下c才是有序的，所以想直接查詢 b = 1，是利用不到這個(gè)聯(lián)合索引的。
4.8 MySQL 索引的分類
按數(shù)據(jù)結(jié)構(gòu)分類可分為：B+tree索引、Hash索引、Full-text索引。
按物理存儲(chǔ)分類可分為：聚簇索引、二級(jí)索引（輔助索引）。
按字段特性分類可分為：主鍵索引、普通索引、前綴索引。
按字段個(gè)數(shù)分類可分為：單列索引、聯(lián)合索引（復(fù)合索引、組合索引）。
4.8.1 按數(shù)據(jù)結(jié)構(gòu)分類
MySQL索引按數(shù)據(jù)結(jié)構(gòu)分類可分為：B+tree索引、Hash索引、Full-text索引。
| InnoDB | MyISAM | Memory | |
|---|---|---|---|
| B+tree索引 | √ | √ | √ |
| Hash索引 | × | × | √ |
| Full-text索引 | √（MySQL5.6+） | √ | × |
注：InnoDB實(shí)際上也支持Hash索引，但是InnoDB中Hash索引的創(chuàng)建由存儲(chǔ)引擎引擎自動(dòng)優(yōu)化創(chuàng)建，不能人為干預(yù)是否為表創(chuàng)建Hash索引
B+tree 是MySQL中被存儲(chǔ)引擎采用最多的索引類型。B+tree 中的 B 代表平衡（balance），而不是二叉（binary），因?yàn)?B+tree 是從最早的平衡二叉樹(shù)演化而來(lái)的。下面展示B+tree數(shù)據(jù)結(jié)構(gòu)與其他數(shù)據(jù)結(jié)構(gòu)的對(duì)比。
1. B+tree與B-tree的對(duì)比
B-tree 中的每個(gè)節(jié)點(diǎn)根據(jù)實(shí)際情況可以包含多條數(shù)據(jù)信息和子節(jié)點(diǎn)，如下圖所示為一個(gè)3階的B-tree：
（圖片來(lái)源于網(wǎng)絡(luò))
相對(duì)于B-tree，B+tree有以下兩點(diǎn)不同：
- B+tree 非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息， 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中。而B(niǎo)-tree的非葉子節(jié)點(diǎn)也存儲(chǔ)數(shù)據(jù)。所以B+tree單個(gè)節(jié)點(diǎn)的數(shù)據(jù)量更小，在相同的磁盤I/O次數(shù)下，能查詢更多的節(jié)點(diǎn)。
- B+tree 所有葉子節(jié)點(diǎn)之間都采用單鏈表連接。適合MySQL中常見(jiàn)的基于范圍的順序檢索場(chǎng)景，而B(niǎo)-tree無(wú)法做到這一點(diǎn)。
2. B+tree與紅黑樹(shù)的對(duì)比
（圖片來(lái)源于網(wǎng)絡(luò)）
紅黑樹(shù)是一種弱平衡二叉查找樹(shù)。通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色的方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出兩倍。
對(duì)于有N個(gè)葉子結(jié)點(diǎn)的 B+tree，其搜索復(fù)雜度為 O(logdN) ，其中 d(degree) 為 B+tree 的度，表示節(jié)點(diǎn)允許的最大子節(jié)點(diǎn)個(gè)數(shù)為d個(gè)，在實(shí)際應(yīng)用當(dāng)中，d值一般是大于100的，即使數(shù)據(jù)量達(dá)到千萬(wàn)級(jí)別時(shí)B+tree的高度依然維持在3-4左右，保證了3-4次磁盤I/O操作就能查詢到目標(biāo)數(shù)據(jù)。
紅黑樹(shù)是二叉樹(shù)，節(jié)點(diǎn)子節(jié)點(diǎn)個(gè)數(shù)為兩個(gè)，意味著其搜索復(fù)雜度為 O(logN)，樹(shù)的高度也會(huì)比 B+tree 高出不少，因此紅黑樹(shù)檢索到目標(biāo)數(shù)據(jù)所需經(jīng)歷的磁盤I/O次數(shù)更多。
3. B+tree與Hash的對(duì)比
Hash 索引結(jié)構(gòu)的特殊性，其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節(jié)點(diǎn)到枝節(jié)點(diǎn)，最后才能訪問(wèn)到頁(yè)節(jié)點(diǎn)這樣多次的IO訪問(wèn)，所以 Hash 索引的查詢效率要遠(yuǎn)高于 B-Tree 索引。雖然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也帶來(lái)了很多限制和弊端，主要有以下這些。
Hash 索引僅僅能滿足 = , IN 和 <=>(表示NULL安全的等價(jià)) 查詢，不能使用范圍查詢。
由于 Hash 索引比較的是進(jìn)行 Hash 運(yùn)算之后的 Hash值，所以它只能用于等值的過(guò)濾，不能用于基于范圍的過(guò)濾，因?yàn)榻?jīng)過(guò)相應(yīng)的 Hash算法處理之后的 Hash 值的大小關(guān)系，并不能保證和Hash運(yùn)算前完全一樣。
Hash 索引無(wú)法適用數(shù)據(jù)的排序操作。
由于 Hash 索引中存放的是經(jīng)過(guò) Hash 計(jì)算之后的 Hash值，而且Hash值的大小關(guān)系并不一定和 Hash運(yùn)算前的鍵值完全一樣，所以數(shù)據(jù)庫(kù)無(wú)法利用索引的數(shù)據(jù)來(lái)避免任何排序運(yùn)算；
Hash 索引不能利用部分索引鍵查詢。
對(duì)于組合索引，Hash 索引在計(jì)算 Hash 值的時(shí)候是組合索引鍵合并后再一起計(jì)算 Hash 值，而不是單獨(dú)計(jì)算 Hash值，所以通過(guò)組合索引的前面一個(gè)或幾個(gè)索引鍵進(jìn)行查詢的時(shí)候，Hash 索引也無(wú)法被利用。
Hash 索引依然需要回表掃描。
Hash 索引是將索引鍵通過(guò) Hash 運(yùn)算之后，將 Hash運(yùn)算結(jié)果的 Hash值和所對(duì)應(yīng)的行指針信息存放于一個(gè) Hash 表中，由于不同索引鍵可能存在相同 Hash 值，所以即使取滿足某個(gè) Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無(wú)法從 Hash索引中直接完成查詢，還是要通過(guò)訪問(wèn)表中的實(shí)際數(shù)據(jù)進(jìn)行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。
Hash索引遇到大量Hash值相等的情況后性能并不一定就會(huì)比B-Tree索引高。
選擇性比較低的索引鍵，如果創(chuàng)建 Hash 索引，那么將會(huì)存在大量記錄指針信息存于同一個(gè)Hash值相關(guān)聯(lián)。這樣要定位某一條記錄時(shí)就會(huì)非常麻煩，會(huì)浪費(fèi)多次表數(shù)據(jù)的訪問(wèn)，而造成整體性能低下
由于范圍查詢是MySQL數(shù)據(jù)庫(kù)查詢中常見(jiàn)的場(chǎng)景，Hash表不適合做范圍查詢，它更適合做等值查詢。另外Hash表還存在Hash函數(shù)選擇和Hash值沖突等問(wèn)題。因此，B+tree索引要比Hash表索引有更廣的適用場(chǎng)景。
4.8.2 按物理存儲(chǔ)分類
MySQL索引按葉子節(jié)點(diǎn)存儲(chǔ)的是否為完整表數(shù)據(jù)分為：聚簇索引、二級(jí)索引（輔助索引）。全表數(shù)據(jù)存儲(chǔ)在聚簇索引中，聚簇索引以外的其他索引叫做二級(jí)索引，也叫輔助索引。
1. 聚簇索引
聚簇索引的每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)了一行完整的表數(shù)據(jù)，葉子節(jié)點(diǎn)間按id列遞增連接，可以方便地進(jìn)行順序檢索。
（圖片來(lái)源于網(wǎng)絡(luò)）
InnoDB表要求必須有聚簇索引，默認(rèn)在主鍵字段上建立聚簇索引，在沒(méi)有主鍵字段的情況下，表的第一個(gè)非空的唯一索引將被建立為聚簇索引，在前兩者都沒(méi)有的情況下，InnoDB將自動(dòng)生成一個(gè)隱式的自增id列，并在此列上建立聚簇索引。
以MyISAM為存儲(chǔ)引擎的表不存在聚簇索引。
MyISAM表中的主鍵索引和非主鍵索引的結(jié)構(gòu)是一樣的，索引的葉子節(jié)點(diǎn)不存儲(chǔ)表數(shù)據(jù)，存放的是表數(shù)據(jù)的地址。所以，MyISAM表可以沒(méi)有主鍵。
（圖片來(lái)源于網(wǎng)絡(luò)）
MyISAM表的數(shù)據(jù)和索引是分開(kāi)存儲(chǔ)的。MyISAM表的主鍵索引和非主鍵索引的區(qū)別僅在于主鍵索引的B+tree上的key必須符合主鍵的限制，非主鍵索引B+tree上的key只要符合相應(yīng)字段的特性就可以了。
2. 二級(jí)索引
二級(jí)索引的葉子節(jié)點(diǎn)并不存儲(chǔ)一行完整的表數(shù)據(jù)，而是存儲(chǔ)了聚簇索引所在列的值。
（圖片來(lái)源于網(wǎng)絡(luò))
回表查詢
由于二級(jí)索引的葉子節(jié)點(diǎn)不存儲(chǔ)完整的表數(shù)據(jù)，索引當(dāng)通過(guò)二級(jí)索引查詢到聚簇索引列值后，還需要回到聚簇索引也就是表數(shù)據(jù)本身進(jìn)一步獲取數(shù)據(jù)。
（圖片來(lái)源于網(wǎng)絡(luò))
回表查詢 需要額外的 B+tree 搜索過(guò)程，必然增大查詢耗時(shí)。
需要注意的是，通過(guò)二級(jí)索引查詢時(shí)，回表不是必須的過(guò)程，當(dāng)SELECT的所有字段在單個(gè)二級(jí)索引中都能夠找到時(shí)，就不需要回表，MySQL稱此時(shí)的二級(jí)索引為覆蓋索引或觸發(fā)了索引覆蓋。
可以用Explain命令查看SQL語(yǔ)句的執(zhí)行計(jì)劃，執(zhí)行計(jì)劃的Extra字段中若出現(xiàn)Using index，表示查詢觸發(fā)了索引覆蓋。
4.8.3 按字段特性分類
MySQL索引按字段特性分類可分為：主鍵索引、普通索引、前綴索引。
1. 主鍵索引
建立在主鍵上的索引被稱為主鍵索引，一張數(shù)據(jù)表只能有一個(gè)主鍵索引，索引列值不允許有空值，通常在創(chuàng)建表時(shí)一起創(chuàng)建。
2. 唯一索引
建立在UNIQUE字段上的索引被稱為唯一索引，一張表可以有多個(gè)唯一索引，索引列值允許為空，列值中出現(xiàn)多個(gè)空值不會(huì)發(fā)生重復(fù)沖突。
3. 普通索引
建立在普通字段上的索引被稱為普通索引。
4. 前綴索引
前綴索引是指對(duì)字符類型字段的前幾個(gè)字符或?qū)ΧM(jìn)制類型字段的前幾個(gè)bytes建立的索引，而不是在整個(gè)字段上建索引。前綴索引可以建立在類型為char、varchar、binary、varbinary的列上，可以大大減少索引占用的存儲(chǔ)空間，也能提升索引的查詢效率。
4.8.4 按索引字段個(gè)數(shù)分類
MySQL索引按字段個(gè)數(shù)分類可分為：單列索引、聯(lián)合索引（復(fù)合索引、組合索引）。
1. 單列索引
建立在單個(gè)列上的索引被稱為單列索引。
2. 聯(lián)合索引（復(fù)合索引、組合索引）
建立在多個(gè)列上的索引被稱為聯(lián)合索引，又叫復(fù)合索引、組合索引。
5. 數(shù)據(jù)結(jié)構(gòu)
5.1 AVL樹(shù)（平衡二叉樹(shù)）
以樹(shù)中所有結(jié)點(diǎn)為根的樹(shù)的左右子樹(shù)高度之差的絕對(duì)值不超過(guò)1
5.2 紅黑樹(shù)
紅黑樹(shù)是一種二叉查找樹(shù)，但在每個(gè)節(jié)點(diǎn)增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅或黑（非紅即黑）。通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色的方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其它路徑長(zhǎng)出兩倍 ，因此，紅黑樹(shù)是一種弱平衡二叉樹(shù)，相對(duì)于要求嚴(yán)格的AVL樹(shù)來(lái)說(shuō)，它的旋轉(zhuǎn)次數(shù)少，所以對(duì)于搜索，插入，刪除操作較多的情況下，通常使用紅黑樹(shù)。
-
性質(zhì)：
- 每個(gè)節(jié)點(diǎn)非紅即黑；
- 根節(jié)點(diǎn)是黑的；
- 每個(gè)葉節(jié)點(diǎn)（葉節(jié)點(diǎn)即樹(shù)尾端NULL指針或NULL節(jié)點(diǎn)）都是黑的；
- 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的；
- 對(duì)于任意節(jié)點(diǎn)而言，其到葉子點(diǎn)樹(shù)NULL指針的每條路徑都包含相同數(shù)目的黑節(jié)點(diǎn)；
-
與 AVL 樹(shù)相比：
AVL 樹(shù)是高度平衡的，頻繁的插入和刪除，會(huì)引起頻繁的rebalance，導(dǎo)致效率下降；紅黑樹(shù)不是高度平衡的，算是一種折中，插入最多兩次旋轉(zhuǎn)，刪除最多三次旋轉(zhuǎn)。
紅黑樹(shù)在查找，插入刪除的性能都是O(logn)，且性能穩(wěn)定，所以STL里面很多結(jié)構(gòu)包括map底層實(shí)現(xiàn)都是使用的紅黑樹(shù)。
5.3 哈夫曼樹(shù)
哈夫曼樹(shù)是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)，也稱為最優(yōu)二叉樹(shù)。
-
構(gòu)建哈夫曼樹(shù)：
ds52- 將每個(gè)節(jié)點(diǎn)單獨(dú)作為一個(gè)樹(shù)，構(gòu)成森林；
- 選擇當(dāng)前森林中根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)，生成一個(gè)新的節(jié)點(diǎn)作為根節(jié)點(diǎn)，其權(quán)值為兩棵樹(shù)的根節(jié)點(diǎn)的權(quán)值之和；
- 從森林中刪除這兩棵樹(shù)，并將新樹(shù)加到森林中；
- 遞歸執(zhí)行前兩步，直到森林中只剩下一棵樹(shù)，那棵樹(shù)即為構(gòu)造好的哈夫曼樹(shù)。
-
哈夫曼編碼：
ds50根據(jù)字符出現(xiàn)的頻率設(shè)計(jì)的一種可變編碼（VLC），概率越低的字符權(quán)值越低，構(gòu)造一個(gè)哈夫曼樹(shù)，這樣概率越高的字符的編碼越短，概率越低的字符編碼越短，可以使得整個(gè)文本的長(zhǎng)度被大幅壓縮。
5.4 B樹(shù)
5.5 B+樹(shù)
5.6 堆和棧的區(qū)別
-
申請(qǐng)方式：
棧由系統(tǒng)自動(dòng)分配和管理，堆由程序員手動(dòng)分配和管理。
-
效率：
棧由系統(tǒng)分配，速度快，不會(huì)有內(nèi)存碎片；
堆由程序員分配，速度較慢，可能由于操作不當(dāng)產(chǎn)生內(nèi)存碎片。
-
擴(kuò)展方向：
棧從高地址向低地址進(jìn)行擴(kuò)展，堆由低地址向高地址進(jìn)行擴(kuò)展。
程序局部變量是使用的?？臻g，new/malloc動(dòng)態(tài)申請(qǐng)的內(nèi)存是堆空間，函數(shù)調(diào)用時(shí)會(huì)進(jìn)行形參和返回值的壓棧出棧，也是用的?？臻g。
5.7 Array和List的區(qū)別
- Array
- 優(yōu)點(diǎn)：
- 隨機(jī)訪問(wèn)性強(qiáng)；
- 查找速度快。
- 缺點(diǎn)：
- 插入和刪除效率低；
- 可能浪費(fèi)內(nèi)存；
- 內(nèi)存空間要求高，必須有足夠的連續(xù)內(nèi)存空間；
- 數(shù)組大小固定，不能動(dòng)態(tài)拓展。
- 優(yōu)點(diǎn)：
- List
- 優(yōu)點(diǎn)：
- 插入刪除速度快；
- 內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存；
- 大小沒(méi)有固定，拓展很靈活。
- 缺點(diǎn)：
- 不能隨機(jī)查找，必須從第一個(gè)開(kāi)始遍歷，查找效率低。
- 優(yōu)點(diǎn)：
5.8 排序算法
5.9 解決Hash沖突的方法
開(kāi)放定址法、再哈希法、鏈地址法、建立公共溢出區(qū)
5.10 分布式 rehash
http://www.itdecent.cn/p/b17bc9719645
5.11 并查集（Union-Find）
https://labuladong.gitbook.io/algo/mu-lu-ye-1/mu-lu-ye-2/unionfind-suan-fa-xiang-jie
目標(biāo)：解決圖論中 動(dòng)態(tài)連通性問(wèn)題
-
實(shí)現(xiàn)：
- 用數(shù)組模擬一個(gè)森林；
- 每個(gè)節(jié)點(diǎn)初始都指向自己；
- 合并是找到兩棵樹(shù)的根節(jié)點(diǎn)，把其中一個(gè)掛到另一個(gè)上面就可以了；
class UF { // 連通分量個(gè)數(shù) private int count; // 存儲(chǔ)一棵樹(shù) private int[] parent; // 記錄樹(shù)的“重量” private int[] size; public UF(int n) { this.count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 小樹(shù)接到大樹(shù)下面，較平衡 if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; } public boolean connected(int p, int q) { int rootP = find(p); int rootQ = find(q); return rootP == rootQ; } private int find(int x) { while (parent[x] != x) { // 進(jìn)行路徑壓縮 parent[x] = parent[parent[x]]; x = parent[x]; } return x; } public int count() { return count; } }img -
優(yōu)化：
- 小樹(shù)掛到大樹(shù)上面；
- 路徑壓縮
-
應(yīng)用：
- 可以作為DFS的一種替代方案，很多使用 DFS 深度優(yōu)先算法解決的問(wèn)題，也可以用 Union-Find 算法解決；
- 表示一種等價(jià)性
-
相關(guān)例題：
6. 算法
6.1 數(shù)據(jù)流中的中位數(shù)
https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
思路：使用兩個(gè)堆，大頂堆存較小的一半數(shù)，小頂堆存較大的一半數(shù)
6.2 用摩爾投票法解決求眾數(shù)問(wèn)題
- 相關(guān)題目：
- 解題思路：
- 記錄n個(gè)候選者的票數(shù)，如果發(fā)現(xiàn)n+1個(gè)不同的候選者則全部抵消一票，最后留下來(lái)的候選者有可能為眾數(shù)票獲得者；
- 再遍歷一遍查看余下的候選者是否超過(guò)了指定比例的票數(shù)，如果超過(guò)則當(dāng)選。
6.3 Top K 問(wèn)題
-
相關(guān)題目：
-
解題思路：
- 全部排序，取前K個(gè)；
- 用快排的思想，進(jìn)行分區(qū)劃分，當(dāng)找到一個(gè)分區(qū)元素的下標(biāo)等于k，且前k個(gè)均大于（或小于）這個(gè)元素，停止；（
）
- 用堆（大頂堆或者小頂堆），持續(xù)push，最后pop K 個(gè)元素即可；(
)
- 用優(yōu)先隊(duì)列實(shí)現(xiàn)最小堆，先往其中push前K個(gè)元素，然后每次push一次，pop一次，最后取堆頂元素即可。
6.4 統(tǒng)計(jì) 1~n 整數(shù)中 1 出現(xiàn)的次數(shù)
-
相關(guān)題目：
-
解題思路：
統(tǒng)計(jì)每個(gè)數(shù)位上1可能出現(xiàn)的次數(shù)，然后加和
-
對(duì)于每個(gè)數(shù)位上的1如何統(tǒng)計(jì)，思路如下：
-
cur == 0
Picture1.png -
cur == 1
Picture2.png -
cur > 1
Picture3.png
-
6.5 數(shù)字序列中的某位數(shù)字
-
相關(guān)題目：
-
解題思路：
- 1 ~ 9, 10 ~ 99, 100 ~ 999, ... => 若干個(gè)區(qū)間
- 定位到其中一個(gè)區(qū)間，該區(qū)間內(nèi)所有的數(shù)字的位數(shù)都是相等的，可以簡(jiǎn)單的定位到指定數(shù)字
6.6 把數(shù)組排成最小的數(shù)
-
相關(guān)題目：
輸入一個(gè)非負(fù)整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。
-
解題思路：
-
對(duì)于任意兩個(gè)數(shù)字
，定義排序規(guī)則為：
-
=>
-
=>
-
-
自定義 C++ priority_queue 比較函數(shù)：
struct queue_cmp { bool operator()(const string &a, const string &b) { return stol(a + b) > stol(b + a); } }; -
使用優(yōu)先隊(duì)列實(shí)現(xiàn)最小堆來(lái)排序：
priority_queue<string, vector<string>, queue_cmp> q;
-
6.7 最長(zhǎng)不包含重復(fù)字符的子字符串
-
相關(guān)題目：
請(qǐng)從字符串中找出一個(gè)最長(zhǎng)的不包含重復(fù)字符的子字符串，計(jì)算該最長(zhǎng)子字符串的長(zhǎng)度。
-
解題思路：
-
雙指針滑動(dòng)法：
- 動(dòng)態(tài)規(guī)劃+哈希表：
- 用hash表記錄某個(gè)字符最后出現(xiàn)的位置；
- dp[i] 表示以 s[i] 結(jié)尾的最長(zhǎng)的不含重復(fù)字符的子串的長(zhǎng)度；
- base case: dp[0] = 1；
- 狀態(tài)轉(zhuǎn)移方程：
-
6.8 丑數(shù)
-
相關(guān)題目：
我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。求按從小到大的順序的第 n 個(gè)丑數(shù)。
-
解題思路：
-
最小堆：
- 先將1放入；
- 每次取堆頂元素，并對(duì)堆頂元素分別×2、3、5，加入堆；
- 循環(huán)取n次即可；
-
動(dòng)態(tài)規(guī)劃：
dp[i] 表示第
個(gè) 丑數(shù);
pa => 指向下一個(gè)丑數(shù) * 2，pb => 指向下一個(gè)丑數(shù) * 3， pc 指向下一個(gè)丑數(shù) * 5;
base case: dp[0] = 1, pa = 0, pb = 0, pc = 0;
-
狀態(tài)轉(zhuǎn)移方程：
if (dp[i] == n1) a++; if (dp[i] == n2) b++; if (dp[i] == n3) c++;
-
6.9 數(shù)組中的逆序?qū)Γy）
-
相關(guān)題目：
劍指 Offer 51. 數(shù)組中的逆序?qū)?/a>
在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)。
-
解題思路：
-
歸并：
- 使用歸并排序的思路，每次合并有序數(shù)組時(shí)，如果右側(cè)小于左側(cè)，則逆序?qū)?shù)量加等于左側(cè)i右半數(shù)組的長(zhǎng)度
img
-
6.10 數(shù)組中數(shù)字出現(xiàn)的次數(shù)（中）
-
相關(guān)題目：
劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù)
一個(gè)整型數(shù)組
nums里除兩個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。 -
解題思路：
- 對(duì)于一個(gè)數(shù)組中除了一個(gè)數(shù)字之外，其它數(shù)字都出現(xiàn)了兩次的情況，只要對(duì)所有的數(shù)字進(jìn)行異或，剩下的結(jié)果就是那個(gè)數(shù)字；
- 對(duì)于一個(gè)數(shù)組中除了兩個(gè)數(shù)字之外，其它數(shù)字都出現(xiàn)了兩次的情況 => 可以將數(shù)組劃分成兩個(gè)子數(shù)組，保證兩個(gè)子數(shù)組都符合上面的情況，就可以簡(jiǎn)化成異或計(jì)算。
- 所以核心問(wèn)題是 => 怎么去將數(shù)組里面的元素劃分成兩組，保證每組里面除了一個(gè)數(shù)字之外，其它數(shù)字都出現(xiàn)了兩次
- 假設(shè)這兩個(gè)只出現(xiàn)一次的數(shù)字為
和
，那么對(duì)數(shù)組的所有數(shù)字異或的結(jié)果 =>
，記為
- 那么只要根據(jù)
的第一個(gè)為1的位來(lái)分組即可；
擴(kuò)展：劍指 Offer 56 - II. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) II
6.11 約瑟夫環(huán)問(wèn)題
-
相關(guān)題目：
-
解題思路
用棧模擬 => 數(shù)字較大時(shí)會(huì)超時(shí)
-
動(dòng)態(tài)規(guī)劃：
base case : dp[0] = 0
-
狀態(tài)轉(zhuǎn)移方程：
6.12 最長(zhǎng)遞增子序列（中）
-
相關(guān)題目：
給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。
子序列是由數(shù)組派生而來(lái)的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。
-
解題思路：
-
動(dòng)態(tài)規(guī)劃：
dp[i] => 以 nums[i] 結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度
base case: dp[i] = 1
-
狀態(tài)轉(zhuǎn)移方程：
-
6.13 俄羅斯信封套娃問(wèn)題（難）
-
相關(guān)題目：
給你一個(gè)二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個(gè)信封的寬度和高度。
當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。
請(qǐng)計(jì)算 最多能有多少個(gè) 信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
注意：不允許旋轉(zhuǎn)信封。
-
解題思路：
-
按 w 升序之后，相同的 w 情況下按 h 降序進(jìn)行排序；（因?yàn)橄嗤瑢挾鹊牟荒芮短?，所以要?duì)h進(jìn)行降序排序）
// 先按第一個(gè)元素升序，按第二個(gè)元素降序 sort(envelopes.begin(), envelopes.end(), [](const vector<int> &a, const vector<int> &b) { if (a[0] == b[0]) { return a[1] > b[1]; } return a[0] < b[0]; }); 對(duì)排序后的數(shù)組，按 h 進(jìn)行最長(zhǎng)遞增子序列求解即可。
-
7. Redis
https://juejin.cn/post/6844903982066827277
