搬運自?？途W(wǎng)大神總結(jié)

extern關(guān)鍵字

extern修飾變量
是個聲明，此變量/函數(shù)是在別處定義的，要在此處引用
extern修飾函數(shù)
暗示這個函數(shù)可能在別的源文件里定義，沒有其它作用。
extern C的作用？用法？
告訴編譯器在編譯函數(shù)名時按著C的規(guī)則去翻譯相應(yīng)的函數(shù)名而不是C++的(C++要支持多態(tài)，C沒有)

static關(guān)鍵字作用

修飾局部變量
被修飾的變量成為靜態(tài)變量，存儲在靜態(tài)區(qū)。存儲在靜態(tài)區(qū)的數(shù)據(jù)生命周期與程序相同，在main函數(shù)之前初始化，在程序退出時銷毀。（無論是局部靜態(tài)還是全局靜態(tài)）
局部靜態(tài)變量使得該變量在退出函數(shù)后，不會被銷毀，因此再次調(diào)用該函數(shù)時，該變量的值與上次退出函數(shù)時值相同。值得注意的是，生命周期并不代表其可以一直被訪問，因為變量的訪問還受到其作用域的限制。
修飾全局變量
全局變量本來就存儲在靜態(tài)區(qū)，因此static并不能改變其存儲位置。但是，static限制了其鏈接屬性。被static修飾的全局變量只能被該包含該定義的文件訪問。
static修飾函數(shù)使得函數(shù)只能在包含該函數(shù)定義的文件中被調(diào)用。
static修飾成員變量
static修飾的變量先于對象存在，所以static修飾的變量要在類外初始化。因為static是所有對象共享的東西嘛，必須要比對象先存在的。

static在C++中對于靜態(tài)成員變量和靜態(tài)成員函數(shù)。所有的對象都只維持同一個實例。相當于類的屬性

static修飾成員函數(shù)
由于static修飾的類成員屬于類，不屬于對象，因此static類成員函數(shù)是沒有this指針的，this指針是指向本對象的指針。正因為沒有this指針，所以static類成員函數(shù)不能訪問非static的類成員，只能訪問 static修飾的類成員。
注意事項

出現(xiàn)在類體外的函數(shù)不能指定關(guān)鍵字static；
靜態(tài)成員之間可以互相訪問，包括靜態(tài)成員函數(shù)訪問靜態(tài)數(shù)據(jù)成員和訪問靜態(tài)成員函數(shù)；
非靜態(tài)成員函數(shù)可以任意地訪問靜態(tài)成員函數(shù)和靜態(tài)數(shù)據(jù)成員；
靜態(tài)成員函數(shù)不能訪問非靜態(tài)成員函數(shù)和非靜態(tài)數(shù)據(jù)成員；
由于沒有this指針的額外開銷，因此靜態(tài)成員函數(shù)與類的全局函數(shù)相比，速度上會有少許的增長；
調(diào)用靜態(tài)成員函數(shù)，可以用成員訪問操作符(.)和(->)為一個類的對象或指向類對象的指調(diào)用靜態(tài)成員函數(shù)。

volatile關(guān)鍵字

訪問寄存器要比訪問內(nèi)存要塊，因此CPU會優(yōu)先訪問該數(shù)據(jù)在寄存器中的存儲結(jié)果，但是內(nèi)存中的數(shù)據(jù)可能已經(jīng)發(fā)生了改變，而寄存器中還保留著原來的結(jié)果。為了避免這種情況的發(fā)生將該變量聲明為volatile，告訴CPU每次都從內(nèi)存去讀取數(shù)據(jù)。
一個參數(shù)可以即是const又是volatile的嗎？可以，一個例子是只讀狀態(tài)寄存器，是volatile是因為它可能被意想不到的被改變，是const告訴程序不應(yīng)該試圖去修改他。

enum枚舉變量

某個枚舉變量的值默認為前一個變量值加一
第一個枚舉變量默認值為0
枚舉變量值是可以重復(fù)的

const的作用

修飾變量，局部變量，全局變量，成員變量（必須初始值列表）
修飾引用作為函數(shù)參數(shù)，保護值不會改變，同時也針對常量參數(shù)
修飾成員函數(shù)，類的成員函數(shù)加上const限定可以聲明此函數(shù)不會更改類對象的內(nèi)容（并不牢靠）
修飾返回值，表明返回的數(shù)據(jù)是不可修改的
修飾指針，左定值，右定向，const在*左側(cè)表示所指內(nèi)容是常量，在*右側(cè)表示指針本身是常量不可變

new和malloc區(qū)別

new分配內(nèi)存按照數(shù)據(jù)類型進行分配，malloc分配內(nèi)存按照大小分配；
new不僅分配一段內(nèi)存，而且會調(diào)用構(gòu)造函數(shù)，但是malloc則不會。new的實現(xiàn)原理？但是還需要注意的是，之前看到過一個題說int p = new int與int p = new int()的區(qū)別，因為int屬于C++內(nèi)置對象，不會默認初始化，必須顯示調(diào)用默認構(gòu)造函數(shù)，但是對于自定義對象都會默認調(diào)用構(gòu)造函數(shù)初始化。翻閱資料后，在C++11中兩者沒有區(qū)別了，自己測試的結(jié)構(gòu)也都是為0；
new返回的是指定對象的指針，而malloc返回的是void*，因此malloc的返回值一般都需要進行類型轉(zhuǎn)化；
new是一個操作符可以重載，malloc是一個庫函數(shù)；
new分配的內(nèi)存要用delete銷毀，malloc要用free來銷毀；delete銷毀的時候會調(diào)用對象的析構(gòu)函數(shù)，而free則不會；
malloc分配的內(nèi)存不夠的時候，可以用realloc擴容。擴容的原理？new沒用這樣操作；
new如果分配失敗了會拋出bad_malloc的異常，而malloc失敗了會返回NULL。因此對于new，正確的姿勢是采用try...catch語法，而malloc則應(yīng)該判斷指針的返回值。為了兼容很多c程序員的習慣，C++也可以采用new nothrow的方法禁止拋出異常而返回NULL；
new和new[]的區(qū)別，new[]一次分配所有內(nèi)存，多次調(diào)用構(gòu)造函數(shù)，分別搭配使用delete和delete[]，同理，delete[]多次調(diào)用析構(gòu)函數(shù)，銷毀數(shù)組中的每個對象。而malloc則只能sizeof(int) * n；
如果不夠可以繼續(xù)談new和malloc的實現(xiàn)，空閑鏈表，分配方法(首次適配原則，最佳適配原則，最差適配原則，快速適配原則)。delete和free的實現(xiàn)原理，free為什么直到銷毀多大的空間？

C++多態(tài)性與虛函數(shù)

C++多態(tài)的實現(xiàn)
多態(tài)分為靜態(tài)多態(tài)和動態(tài)多態(tài)。靜態(tài)多態(tài)是通過重載和模板技術(shù)實現(xiàn)，在編譯的時候確定。動態(tài)多態(tài)通過虛函數(shù)和繼承關(guān)系來實現(xiàn)，執(zhí)行動態(tài)綁定，在運行的時候確定。
動態(tài)多態(tài)實現(xiàn)有幾個條件：
(1) 虛函數(shù)；
(2) 一個基類的指針或引用指向派生類的對象；
基類指針在調(diào)用成員函數(shù)(虛函數(shù))時，就會去查找該對象的虛函數(shù)表。虛函數(shù)表的地址在每個對象的首地址。查找該虛函數(shù)表中該函數(shù)的指針進行調(diào)用。
每個對象中保存的只是一個虛函數(shù)表的指針，C++內(nèi)部為每一個類維持一個虛函數(shù)表，該類的對象的都指向這同一個虛函數(shù)表。
虛函數(shù)表中為什么就能準確查找相應(yīng)的函數(shù)指針呢？因為在類設(shè)計的時候，虛函數(shù)表直接從基類也繼承過來，如果覆蓋了其中的某個虛函數(shù)，那么虛函數(shù)表的指針就會被替換，因此可以根據(jù)指針準確找到該調(diào)用哪個函數(shù)。
虛函數(shù)的作用

用于實現(xiàn)多態(tài)
在設(shè)計上還具有封裝和抽象的作用。比如抽象工廠模式。

動態(tài)綁定是如何實現(xiàn)的
靜態(tài)多態(tài)和動態(tài)多態(tài)
靜態(tài)多態(tài)是指通過模板技術(shù)或者函數(shù)重載技術(shù)實現(xiàn)的多態(tài)，其在編譯器確定行為。動態(tài)多態(tài)是指通過虛函數(shù)技術(shù)實現(xiàn)在運行期動態(tài)綁定的技術(shù)。
虛函數(shù)表
編譯器為每一個類維護一個虛函數(shù)表，每個對象的首地址保存著該虛函數(shù)表的指針，同一個類的不同對象實際上指向同一張?zhí)摵瘮?shù)表。
純虛函數(shù)
純虛函數(shù)定義 virtual ~myClass() = 0;
為什么對于存在虛函數(shù)的類中析構(gòu)函數(shù)要定義成虛函數(shù)
為了實現(xiàn)多態(tài)進行動態(tài)綁定，將派生類對象指針綁定到基類指針上，對象銷毀時，如果析構(gòu)函數(shù)沒有定義為析構(gòu)函數(shù)，則會調(diào)用基類的析構(gòu)函數(shù)，顯然只能銷毀部分數(shù)據(jù)。如果要調(diào)用對象的析構(gòu)函數(shù)，就需要將該對象的析構(gòu)函數(shù)定義為虛函數(shù)，銷毀時通過虛函數(shù)表找到對應(yīng)的析構(gòu)函數(shù)。
析構(gòu)函數(shù)能拋出異常嗎？
肯定是不能。 C++標準指明析構(gòu)函數(shù)不能、也不應(yīng)該拋出異常。C++異常處理模型最大的特點和優(yōu)勢就是對C++中的面向?qū)ο筇峁┝俗顝姶蟮臒o縫支持。那么如果對象在運行期間出現(xiàn)了異常，C++異常處理模型有責任清除那些由于出現(xiàn)異常所導(dǎo)致的已經(jīng)失效了的對象(也即對象超出了它原來的作用域)，并釋放對象原來所分配的資源，這就是調(diào)用這些對象的析構(gòu)函數(shù)來完成釋放資源的任務(wù)，所以從這個意義上說，析構(gòu)函數(shù)已經(jīng)變成了異常處理的一部分。

如果析構(gòu)函數(shù)拋出異常，則異常點之后的程序不會執(zhí)行，如果析構(gòu)函數(shù)在異常點之后執(zhí)行了某些必要的動作比如釋放某些資源，則這些動作不會執(zhí)行，會造成諸如資源泄漏的問題。
通常異常發(fā)生時，c++的機制會調(diào)用已經(jīng)構(gòu)造對象的析構(gòu)函數(shù)來釋放資源，此時若析構(gòu)函數(shù)本身也拋出異常，則前一個異常尚未處理，又有新的異常，會造成程序崩潰的問題。

構(gòu)造函數(shù)可以調(diào)用虛函數(shù)嗎？
不可以，構(gòu)造是按繼承順序的，先基類，后派生類，如果構(gòu)造期間調(diào)用了一個子類的虛函數(shù)，但是子類還未構(gòu)造出來，出現(xiàn)未定義行為。析構(gòu)函數(shù)同理。

C++空類默認的成員函數(shù)

C++中空類默認會產(chǎn)生以下6個函數(shù)：

默認構(gòu)造函數(shù)
復(fù)制構(gòu)造函數(shù)
析構(gòu)函數(shù)
賦值運算符重載函數(shù)
取地址符重載函數(shù)
const取地址符重載函數(shù)

指針和引用

指針保存的是所指對象的地址，引用是所指對象的別名，指針需要通過解引用間接訪問，而引用是直接訪問；
指針可以改變地址，從而改變所指的對象，而引用必須從一而終；
引用在定義的時候必須初始化，而指針則不需要；
指針有指向常量的指針和指針常量，而引用沒有常量引用；
指針更靈活，用的好威力無比，用的不好處處是坑，而引用用起來則安全多了，但是比較死板。

指針與數(shù)組

一個一維int數(shù)組的數(shù)組名實際上是一個int* const 類型；
一個二維int數(shù)組的數(shù)組名實際上是一個int (*const p)[n];
數(shù)組名做參數(shù)會退化為指針，除了sizeof

C++中異常的處理方法

關(guān)鍵字有try, catch, throw
使用try{} catch(){}來捕獲異常，如果本級沒有帶適當類型參數(shù)的catch塊，則不能捕獲異常，異常就會向上一級傳遞，如果一直沒有捕獲，C++會使用默認的異常處理函數(shù)

回調(diào)函數(shù)

回調(diào)函數(shù)是通過函數(shù)指針調(diào)用的函數(shù)，把函數(shù)的指針（地址）作為參數(shù)傳遞給另一個函數(shù)
回調(diào)函數(shù)與應(yīng)用程序接口（API）非常接近，都是跨層調(diào)用的函數(shù)，區(qū)別是API是低層給高層的調(diào)用，回調(diào)函數(shù)則相反，是高層提供給低層的調(diào)用，必須由高層來安裝

內(nèi)存泄露

所謂內(nèi)存泄漏是指由于疏忽或錯誤導(dǎo)致程序未能釋放已經(jīng)不再使用的內(nèi)存的情況，一般指堆內(nèi)存的泄露，失去對該段內(nèi)存的控制，因而造成了內(nèi)存的浪費，會導(dǎo)致CPU資源耗盡的嚴重后果

緩沖區(qū)溢出

緩沖區(qū)是成勛運行的時候機器內(nèi)存的一個連續(xù)塊
當向緩沖區(qū)內(nèi)填充數(shù)據(jù)位數(shù)超過了緩沖區(qū)自身的容量限制，發(fā)生溢出的數(shù)據(jù)覆蓋在合法數(shù)據(jù)（數(shù)據(jù)，下一條指令的指針，函數(shù)返回地址等），解決辦法是檢查數(shù)據(jù)長度

野指針與空懸指針

野指針是指向不可用內(nèi)存的指針，沒有被正確的初始化，指向隨機地址
空懸指針：曾經(jīng)指向有效地址，但原來內(nèi)存被釋放了，現(xiàn)在不再有效

?？臻g的最大值

windows下棧的大小是2MB，堆的大小一般小于2GB
Linux默認?？臻g大小為8MB，可以通過 ulimit -s 來設(shè)置

智能指針的原理和實現(xiàn)

1. 構(gòu)造函數(shù)中計數(shù)初始化為1；
2. 拷貝構(gòu)造函數(shù)中計數(shù)值加1；
3. 賦值運算符中，左邊的對象引用計數(shù)減一，右邊的對象引用計數(shù)加一；
4. 析構(gòu)函數(shù)中引用計數(shù)減一；
5. 在賦值運算符和析構(gòu)函數(shù)中，如果減一后為0，則調(diào)用delete釋放對象。
6. share_prt<T>與weak_ptr<T>的區(qū)別？

share_ptr可能出現(xiàn)循環(huán)引用，從而導(dǎo)致內(nèi)存泄露

class A
{
public:
share_ptr<B> p;
};

class B
{
public:
share_ptr<A> p;
}

int main()
{
while(true)
{
share_prt<A> pa(new A()); //pa的引用計數(shù)初始化為1
share_prt<B> pb(new B()); //pb的引用計數(shù)初始化為1
pa->p = pb; //pb的引用計數(shù)變?yōu)?
pb->p = pa; //pa的引用計數(shù)變?yōu)?
}
//假設(shè)pa先離開，引用計數(shù)減一變?yōu)?，不為0因此不會調(diào)用class A的析構(gòu)函數(shù)，因此其成員p也不會被析構(gòu)，pb的引用計數(shù)仍然為2；
//同理pb離開的時候，引用計數(shù)也不能減到0
return 0;
}

weak_ptr是一種弱引用指針，其存在不會影響引用計數(shù)，從而解決循環(huán)引用的問題

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用于動態(tài)類型轉(zhuǎn)換。只能用于含有虛函數(shù)的類，用于類層次間的向上和向下轉(zhuǎn)化。只能轉(zhuǎn)指針或引用。向下轉(zhuǎn)化時，如果是非法的對于指針返回NULL，對于引用拋異常。要深入了解內(nèi)部轉(zhuǎn)換的原理。
reinterpret_cast幾乎什么都可以轉(zhuǎn)，比如將int轉(zhuǎn)指針，可能會出問題，盡量少用；
為什么不使用C的強制轉(zhuǎn)換？C的強制轉(zhuǎn)換表面上看起來功能強大什么都能轉(zhuǎn)，但是轉(zhuǎn)化不夠明確，不能進行錯誤檢查，容易出錯。

內(nèi)存對齊原則

從0位置開始存儲；
變量存儲的起始位置是該變量大小的整數(shù)倍；
結(jié)構(gòu)體總的大小是其最大元素的整數(shù)倍，不足的后面要補齊；
結(jié)構(gòu)體中包含結(jié)構(gòu)體，從結(jié)構(gòu)體中最大元素的整數(shù)倍開始存；
如果加入pragma pack(n) ，取n和變量自身大小較小的一個。

超高頻問題

struct Q{
    char c;
    int num1;
    double num2;
};

上述代碼中sizeof(Q)為多少？ 16
struct的對其系數(shù)和以下幾個關(guān)系有關(guān)

元素大小
元素順序
pragma參數(shù)

對齊規(guī)則

struct中成員在內(nèi)存中按順序排列，在沒有#pargma pack(n)的情況下，各個成員的對齊系數(shù)為自己的長度
在有#pargma pack(n)的情況下，各個成員的對齊系數(shù)為min(自己的長度，n)
struct整體的對齊系數(shù)為對齊系數(shù)中最大的
依次排列時要滿足地址對對齊系數(shù)取模為0

內(nèi)聯(lián)函數(shù)有什么優(yōu)點？與宏定義的區(qū)別？

宏定義在預(yù)處理階段進行替換
內(nèi)聯(lián)函數(shù)在編譯階段，在調(diào)用內(nèi)聯(lián)函數(shù)的地方進行替換，減少了函數(shù)的調(diào)用過程，但是使得編譯文件變大。因此，內(nèi)聯(lián)函數(shù)適合簡單函數(shù)，對于復(fù)雜函數(shù)，即使定義了內(nèi)聯(lián)編譯器可能也不會按照內(nèi)聯(lián)的方式進行編譯。
內(nèi)聯(lián)函數(shù)相比宏定義更安全，內(nèi)聯(lián)函數(shù)可以檢查參數(shù)，而宏定義只是簡單的文本替換。因此推薦使用內(nèi)聯(lián)函數(shù)，而不是宏定義。
使用宏定義函數(shù)要特別注意給所有單元都加上括號，#define MUL(a, b) ab，這很危險，正確寫法：#define MUL(a, b) ((a)(b))

C++內(nèi)存管理

C++內(nèi)存分為幾塊？
在C++中，內(nèi)存分成5個區(qū)，他們分別是堆、棧、自由存儲區(qū)、全局/靜態(tài)存儲區(qū)和常量存儲區(qū)。

棧，在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放。棧內(nèi)存分配運算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限。
堆，就是那些由new分配的內(nèi)存塊，他們的釋放編譯器不去管，由我們的應(yīng)用程序去控制，一般一個new就要對應(yīng)一個delete。如果程序員沒有釋放掉，那么在程序結(jié)束后，操作系統(tǒng)會自動回收。
自由存儲區(qū)，就是那些由malloc等分配的內(nèi)存塊，他和堆是十分相似的，不過它是用free來結(jié)束自己的生命的。
全局/靜態(tài)存儲區(qū)，全局變量和靜態(tài)變量被分配到同一塊內(nèi)存中，在以前的C語言中，全局變量又分為初始化的和未初始化的，在C++里面沒有這個區(qū)分了，他們共同占用同一塊內(nèi)存區(qū)。
常量存儲區(qū)，這是一塊比較特殊的存儲區(qū)，他們里面存放的是常量，不允許修改

在此注意自由存儲區(qū)和堆

自由存儲是C++中通過new與delete動態(tài)分配和釋放對象的抽象概念，而堆（heap）是C語言和操作系統(tǒng)的術(shù)語，是操作系統(tǒng)維護的一塊動態(tài)分配內(nèi)存。

new所申請的內(nèi)存區(qū)域在C++中稱為自由存儲區(qū)。借由堆實現(xiàn)的自由存儲，可以說new所申請的內(nèi)存區(qū)域在堆上。

堆與自由存儲區(qū)還是有區(qū)別的，它們并非等價。

學(xué)會遷移，可以說到malloc，從malloc說到操作系統(tǒng)的內(nèi)存管理，說道內(nèi)核態(tài)和用戶態(tài)，然后就什么高端內(nèi)存，slab層，伙伴算法，VMA可以巴拉巴拉了，接著可以遷移到fork()。

STL里的內(nèi)存管理

STL內(nèi)存分配分為一級分配器和二級分配器，一級分配器就是采用malloc分配內(nèi)存，二級分配器采用內(nèi)存池。

二級分配器設(shè)計的非常巧妙，分別給8k，16k,..., 128k等比較小的內(nèi)存片都維持一個空閑鏈表，每個鏈表的頭節(jié)點由一個數(shù)組來維護。需要分配內(nèi)存時從合適大小的鏈表中取一塊下來。假設(shè)需要分配一塊10K的內(nèi)存，那么就找到最小的大于等于10k的塊，也就是16K，從16K的空閑鏈表里取出一個用于分配。釋放該塊內(nèi)存時，將內(nèi)存節(jié)點歸還給鏈表。
如果要分配的內(nèi)存大于128K則直接調(diào)用一級分配器。
為了節(jié)省維持鏈表的開銷，采用了一個union結(jié)構(gòu)體，分配器使用union里的next指針來指向下一個節(jié)點，而用戶則使用union的空指針來表示該節(jié)點的地址。

STL里set和map是基于什么實現(xiàn)的？紅黑樹的特點？

STL的set和map都是基于紅黑樹實現(xiàn)的

AVL是一種高度平衡的二叉樹，所以通常的結(jié)果是，維護這種高度平衡所付出的代價比從中獲得的效率收益還大，故而實際的應(yīng)用不多，更多的地方是用追求局部而不是非常嚴格整體平衡的紅黑樹。當然，如果場景中對插入刪除不頻繁，只是對查找特別有要求，AVL還是優(yōu)于紅黑的。

紅黑樹的應(yīng)用：STL，epoll在內(nèi)核中的實現(xiàn)

每個結(jié)點或者為黑色或者為紅色。
根結(jié)點為黑色。
每個葉結(jié)點(實際上就是NULL指針)都是黑色的。
如果一個結(jié)點是紅色的，那么它的兩個子節(jié)點都是黑色的（也就是說，不能有兩個相鄰的紅色結(jié)點）。
對于每個結(jié)點，從該結(jié)點到其所有子孫葉結(jié)點的路徑中所包含的黑色結(jié)點數(shù)量必須相同。

紅黑樹能夠以O(shè)(log2 n) 的時間復(fù)雜度進行搜索、插入、刪除操作。此外，由于它的設(shè)計，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決。當然，還有一些更好的，但實現(xiàn)起來更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，能夠做到一步旋轉(zhuǎn)之內(nèi)達到平衡，但紅黑樹能夠給我們一個比較“便宜”的解決方案。紅黑樹的算法時間復(fù)雜度和AVL相同，但統(tǒng)計性能比AVL樹更高。

如果插入一個node引起了樹的不平衡，AVL和RB-Tree都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)；但是在刪除node引起樹的不平衡時，最壞情況下，AVL需要維護從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉(zhuǎn)的量級O(logN)，而RB-Tree最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度。

必須在構(gòu)造函數(shù)初始化列表里進行初始化的數(shù)據(jù)成員有哪些

常量成員，因為常量只能初始化不能賦值，所以必須放在初始化列表里面
引用類型，引用必須在定義的時候初始化，并且不能重新賦值，所以也要寫在初始化列表里面
沒有默認構(gòu)造函數(shù)的類類型，因為使用初始化列表可以不必調(diào)用默認構(gòu)造函數(shù)來初始化，而是直接調(diào)用拷貝構(gòu)造函數(shù)初始化
要注意，對非內(nèi)置類型成員，肯定還是列表的性能好，因為省略了一次復(fù)制的過程

模板特化

模板分為類模板與函數(shù)模板，特化分為全特化與偏特化。全特化就是限定死模板實現(xiàn)的具體類型，偏特化就是如果這個模板有多個類型，那么只限定其中的一部分。
模板特化的目的就是對于某一種變量類型具有不同的實現(xiàn)，因此需要特化版本。例如，在STL里迭代器為了適應(yīng)原生指針就將原生指針進行特化。

數(shù)據(jù)結(jié)構(gòu)和算法

手寫strcpy

char* strcpy(char* dst, const char* src){
    assert(dst);
    assert(src);
    char* p = dst;
    while((*dst++ = *src++)!='\0') ;
    return p;
}

若考慮重疊，則有：

char* strcpy(char* dst, const char* src){
    assert(dst);
    assert(src);
    int size = strlen(src)+1;
    char* p = dst;
    if(dst > src && dst < src+size)
    {
        dst = dst + size - 1;
        src = dst + size - 1;
        while(size--)
            *dst-- = *src--;
    }
    else
    {
        while(size--)
            *dst++ = *src++;
    }
    return p;
}

手寫memcpy函數(shù)

void* memcpy(void* dst, const void* src, size_t size){
    if(dst == NULL || src == NULL)
        return NULL;
    void* p = dst;
    char* pdst = (char*)dst;
    char* psrc = (char*)src;
    if(pdst>src && pdst<src+size)
    {
        pdst = pdst+size+1;
        psrc = psrc+size+1;
        while(size--)
            *pdst-- = *psrc--;
    }
    else
    {
        while(size--)
            *pdst++ = *psrc++;
    }
    return p;
}

手寫strcat函數(shù)

char* strcat(char* dst, const char* src){
    char* p = dst;
    while(*dst != '\0')
        dst++;
    while(*dst++ = *src++ !='\0') ;
    return p;
}

手寫strcmp函數(shù)

int strcmp(const char* s1, const char* s2){
    while(*s1 == *s2 && *s1!='\0'){
        ++s1;++s2;
    }
    return *s1-*s2;
}

Hash表

根據(jù)關(guān)鍵碼值（key value）直接訪問的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)有拉鏈法（鏈表），以及開放地址法解決沖突
開放地址法常見策略：

線性探測
線性補償探測法
隨機探測
平方探測

STL中hash_map擴容發(fā)生什么？
(1) 創(chuàng)建一個新桶，該桶是原來桶兩倍大最接近的質(zhì)數(shù)(判斷n是不是質(zhì)數(shù)的方法：用n除2到$sqrt(n)$范圍內(nèi)的數(shù)) ；
(2) 將原來桶里的數(shù)通過指針的轉(zhuǎn)換，插入到新桶中(注意STL這里做的很精細，沒有直接將數(shù)據(jù)從舊桶遍歷拷貝數(shù)據(jù)插入到新桶，而是通過指針轉(zhuǎn)換)
(3) 通過swap函數(shù)將新桶和舊桶交換，銷毀新桶。
Redis中hash擴容？
容量擴張是一次完成的，期間要花很長時間一次轉(zhuǎn)移hash表中的所有元素。
redis中的dict.c中的設(shè)計思路是用兩個hash表來進行進行擴容和轉(zhuǎn)移的工作，把第一個hash表所有元素的轉(zhuǎn)移分攤為多次轉(zhuǎn)移，而且每次轉(zhuǎn)移的期望時間復(fù)雜度為O(1)。這樣就不會出現(xiàn)某一次往字典中插入元素要等候很長時間的情況了。

樹

二叉樹結(jié)構(gòu)，二叉搜索樹在二叉樹的基礎(chǔ)上加上了這樣的一個性質(zhì)：對于樹中的每一個節(jié)點來說，如果有左兒子的話，它的左兒子的值一定小于它本身的值，如果有右兒子的話，它的右兒子的值一定大于它本身的值。
二叉樹的六種遍歷（遞歸，非遞歸）
二叉樹的層序遍歷
遞歸是解決二叉樹相關(guān)問題的神級方法
樹的各種常見算法題

什么是紅黑樹

節(jié)點為紅色或黑色
根節(jié)點為黑色
每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的
每個紅色節(jié)點的兩個子節(jié)點都是黑色的（也就是說不存在兩個連續(xù)的紅色節(jié)點）
從任一節(jié)點到其每個葉節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點

紅黑樹與AVL樹的區(qū)別

紅黑樹與AVL樹都是平衡樹，但是AVL是完全平衡的(平衡就是值樹中任意節(jié)點的左子樹和右子樹高度差不超過1)；
紅黑樹插入效率更高，因為AVL為了保證其完全平衡，插入和刪除的時候在最壞的情況下要旋轉(zhuǎn)logN次，而紅黑樹插入和刪除的旋轉(zhuǎn)次數(shù)要比AVL少，犧牲了嚴格的高度平衡的優(yōu)越條件使得三次旋轉(zhuǎn)即可平衡。

鏈表

鏈表的插入和刪除，單向雙向鏈表
鏈表的問題考慮多個指針和遞歸

反向打印鏈表（遞歸）
打印倒數(shù)第K個節(jié)點（前后指針）
鏈表是否有環(huán)（快慢指針）

棧和隊列

棧（Stack）和隊列（Queue）是兩種操作受限的線性表。
相同點：
1. 都是線性結(jié)構(gòu)。
2. 插入操作都是限定在表尾進行。
3. 都可以通過順序結(jié)構(gòu)和鏈式結(jié)構(gòu)實現(xiàn)。、
4. 插入與刪除的時間復(fù)雜度都是O（1），在空間復(fù)雜度上兩者也一樣。
5. 多鏈棧和多鏈隊列的管理模式可以相同。

不同點：

刪除數(shù)據(jù)元素的位置不同，棧的刪除操作在表尾進行，隊列的刪除操作在表頭進行。
應(yīng)用場景不同：
棧的應(yīng)用場景包括括號問題的求解，表達式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實現(xiàn)，深度優(yōu)先搜索遍歷等
隊列的應(yīng)用場景包括計算機系統(tǒng)中各種資源的管理，消息緩沖器的管理和廣度優(yōu)先搜索遍歷等。
順序棧能夠?qū)崿F(xiàn)多?？臻g共享，而順序隊列不能。

海量數(shù)據(jù)問題

類似問題的解決方法思路：首先哈希將數(shù)據(jù)分成N個文件，然后對每個文件建立K個元素最小/大堆（根據(jù)要求來選擇）。最后將文件中剩余的數(shù)插入堆中，并維持K個元素的堆。最后將N個堆中的元素合起來分析。可以采用歸并的方式來合并。在歸并的時候為了提高效率還需要建一個N個元素構(gòu)成的最大堆，先用N個堆中的最大值填充這個堆，然后就是彈出最大值，指針后移的操作了。當然這種問題在現(xiàn)在的互聯(lián)網(wǎng)技術(shù)中，一般就用map-reduce框架來做了。
大數(shù)據(jù)排序相同的思路：先哈希（哈希是好處是分布均勻，相同的數(shù)在同一個文件中），然后小文件裝入內(nèi)存快排，排序結(jié)果輸出到文件。最后建堆歸并。

海量數(shù)據(jù)重復(fù)問題

使用hash_map或者位圖，再利用歸并的思想

排序算法

必須至少能快速寫出，快排，建堆，和歸并
種算法的時間空間復(fù)雜度，最好最差平均情況

位運算

左移乘2，右移除2
不用臨時變量交換兩個整數(shù)（多次異或）
消除最后一個1
不用加減乘除完成整數(shù)相加

布隆過濾器

由一個很長的二進制向量和一系列隨機映射函數(shù)組成，布隆過濾器可以用于檢索一個元素是否在一個集合中。
優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率（但是不會漏報）

網(wǎng)絡(luò)與TCP/IP

TCP與UDP的區(qū)別

IP首部，TCP首部，UDP首部
TCP和UDP區(qū)別
- TCP基于有連接，UDP基于無連接
- TCP能保證可靠傳輸，UDP不能保證可靠傳輸TCP
- TCP結(jié)構(gòu)復(fù)雜，消耗資源多，建立過程較慢較復(fù)雜。UDP結(jié)構(gòu)簡單，消耗資源少，建立過程較快
- TCP基于流模式，UDP是數(shù)據(jù)報模式
- TCP連接只能是點到點，而UDP可以一對一，一對多或者多對多
- TCP有確認，重傳，擁賽控制機制，UDP在沒有建立連接或者對方已經(jīng)退出的情況下任然會繼續(xù)發(fā)送數(shù)據(jù)，導(dǎo)致通信流量的浪費。
TCP和UDP應(yīng)用場景

TCP：用于實現(xiàn)可靠傳輸?shù)那闆r，文件非常重要，對網(wǎng)絡(luò)擁堵有較高要求的情況。
UDP：用于高速傳輸和實時性較高的場合（即時通信），廣播通信

實現(xiàn)UDP的可靠傳輸，如RTP協(xié)議，RUDP協(xié)議
檢測包的順序，請求重傳，請求者發(fā)起或接收者發(fā)起

TCP三次握手與四次揮手

建立連接

客戶端發(fā)送請求包，告訴服務(wù)器：“我想和你通信？”數(shù)據(jù)包中SYN位置為1，假設(shè)其序列號為x，客戶端狀態(tài)變成SYN_SENT；
服務(wù)器端接受到請求包后也發(fā)送一個請求包，告訴客戶端：“現(xiàn)在可以建立連接”。數(shù)據(jù)包中SYN位置位1，假設(shè)其序列號為y，注意客戶端序列號和服務(wù)器端序列號并沒有關(guān)系，他們是由各自的內(nèi)核按照一定的規(guī)則生成的。但是這個應(yīng)答包的32位應(yīng)答號，必須是x+1，之所以加1是因為客戶端發(fā)過來的包SYN位被認為占一個數(shù)據(jù)。因此，告訴下一包從x+1開始發(fā)。發(fā)送后，服務(wù)器從監(jiān)聽狀態(tài)變成SYN_RCVD狀態(tài)。
客戶端發(fā)送應(yīng)答數(shù)據(jù)包，告訴服務(wù)器：“那我們開始發(fā)送數(shù)據(jù)吧”。數(shù)據(jù)包應(yīng)答號為y+1?？蛻舳俗兂蒃STABLISHED狀態(tài)，即可以傳輸狀態(tài)。
服務(wù)器端接受到應(yīng)答數(shù)據(jù)包后，變成ESTABLISHED狀態(tài)。
發(fā)送數(shù)據(jù)

發(fā)送數(shù)據(jù)

客戶端發(fā)送一個一個字節(jié)的數(shù)據(jù)，因此序列號為x+1；
服務(wù)端發(fā)送一個應(yīng)答包，應(yīng)答號為x+2，告訴客戶端下次從x+2開始發(fā)；

斷開連接

客戶端發(fā)送請求斷開的數(shù)據(jù)包，告訴服務(wù)器：“數(shù)據(jù)傳完了，我要斷開了”。發(fā)送一個FIN包，序列號x+2?？蛻舳宿D(zhuǎn)移到FIN_WAIT_1狀態(tài)。
服務(wù)器端發(fā)送應(yīng)答包，告訴客戶端：“行，我知道了，你斷開吧！”。應(yīng)答號為x+3，服務(wù)器進入CLOSE_WAIT狀態(tài)?？蛻舳耸盏綉?yīng)答后，轉(zhuǎn)移到FIN_WAIT_2狀態(tài)。
服務(wù)器發(fā)送一個斷開數(shù)據(jù)包，告訴客戶端：“既然傳完了，那我這邊的開關(guān)也準備關(guān)了”。序列號為y+1，發(fā)送完后服務(wù)器進入LAST_ACK狀態(tài)。
客戶端發(fā)送一個應(yīng)答包，告訴服務(wù)器：“好的，我知道你要斷開了?！睉?yīng)答號為y+2?？蛻舳诉M入TIME_WAIT狀態(tài)。

TIME_WAIT又稱為2MSL等待狀態(tài)，MSL是系統(tǒng)中定義的最大報文生存時間，任何TCP報文在網(wǎng)絡(luò)中生存時間超過這個值就必須被丟棄。
等待MSL的原因是防止最后一個ACK丟失后可以進行重發(fā)，如果ACK丟失后，服務(wù)器會重發(fā)FIN。
MSL是Maximum Segment Lifetime英文的縮寫，中文可以譯為“報文最大生存時間”

TCP相關(guān)技術(shù)

TCP重發(fā)機制

超時重傳（RTO）
當一個包被發(fā)送后，就開啟一個定時器，如果定時時間到了，還未收到能確認該發(fā)送包的應(yīng)答包，就重傳一份數(shù)據(jù)。注意收到的應(yīng)答包可能是該包也可能是后面包的，但是只要能確認該包被收到就行。另外如果，是因為網(wǎng)絡(luò)延時造成重傳，則接受端收到重復(fù)數(shù)據(jù)包后丟棄該包。
快速重傳
當如果發(fā)送端收到一個包的三次應(yīng)答包后，立即重傳，比超時重傳更高效。

Nagle算法

核心思想為任意時刻，最多只能有一個未被確認的小段。所謂“小段”，指的是小于MSS尺寸的數(shù)據(jù)塊，所謂“未被確認”，是指一個數(shù)據(jù)塊發(fā)送出去后，沒有收到對方發(fā)送的ACK確認該數(shù)據(jù)已收到。
Nagle算法簡單講就是，等待服務(wù)器應(yīng)答包到達后，再發(fā)送下一個數(shù)據(jù)包。數(shù)據(jù)在發(fā)送端被緩存，如果緩存到達指定大小就將其發(fā)送，或者上一個數(shù)據(jù)的應(yīng)答包到達，將緩存區(qū)一次性全部發(fā)送。

Nagle算法是從發(fā)送端角度考慮減少了數(shù)據(jù)包的個數(shù)，時延應(yīng)答從接收端角度考慮減少了數(shù)據(jù)包的個數(shù)。

TCP流量控制

目的：如果發(fā)送方把數(shù)據(jù)發(fā)送得過快，接收方可能會來不及接收，這就會造成數(shù)據(jù)的丟失。
所以流量控制是點對點通信的控制，而擁塞控制是對整個網(wǎng)絡(luò)內(nèi)流量負載的控制
TCP的流量控制是利用滑動窗口機制實現(xiàn)的，接收方在返回的ACK中會包含自己的接收窗口的大小，以控制發(fā)送方的數(shù)據(jù)發(fā)送。

流量控制實例

如上圖所示A向B發(fā)送數(shù)據(jù)。在連接建立時，B告訴A接收窗口rwnd（receiver window）= 400，單位字節(jié)，因此發(fā)送方A的發(fā)送窗口不能超過400。

（可以看出，B向A發(fā)送的三個報文段都設(shè)置了 ACK = 1以保證字段有效，后面的rwnd值就是接收方對發(fā)送方的三次流量控制。）

第一次把窗口設(shè)置為300 ，第二次100 ，最后一次為 0，即不允許發(fā)送方再發(fā)送數(shù)據(jù)的狀態(tài)。

但是當某個ACK報文丟失了，就會出現(xiàn)A等待B確認，并且B等待A發(fā)送數(shù)據(jù)的死鎖狀態(tài)。為了解決這種問題，TCP引入了持續(xù)計時器（Persistence timer），當A收到rwnd=0時，就啟用該計時器，時間到了則發(fā)送一個1字節(jié)的探測報文，詢問B是很忙還是上個ACK丟失了，然后B回應(yīng)自身的接收窗口大小，返回仍為0（A重設(shè)持續(xù)計時器繼續(xù)等待）或者會重發(fā)rwnd=x。

TCP窗口滑動

窗口是TCP中為了解決應(yīng)答機制等待時間過長而引入的方法，如果沒有窗口，則TCP每發(fā)送一次數(shù)據(jù)就必須等待應(yīng)答，收到應(yīng)答后繼續(xù)發(fā)送，如果沒有收到則等待一段時間后重發(fā)，如果很長時間都無法收到應(yīng)答則判斷為網(wǎng)絡(luò)斷開。而使用窗口后，窗口的大小指無需等待應(yīng)答可以連續(xù)發(fā)送多個數(shù)據(jù)包。
TCP窗口在每個傳輸方向都有兩個窗口，發(fā)送端窗口和接收端窗口，又因為TCP是全雙工通信，因此有四個窗口。
引入窗口后，TCP的應(yīng)答包如果部分丟失，無需重傳，由后面的應(yīng)答包保證。TCP為了提高效率，采用延時再確認應(yīng)答，和選擇性確認應(yīng)答，即收到數(shù)據(jù)包后不立即發(fā)送應(yīng)答包，而是等待收到下一個或多個包后發(fā)一個應(yīng)答。

TCP的擁塞控制算法和過程

網(wǎng)絡(luò)中的鏈路容量、交換結(jié)點中的緩存、處理機等等都有著工作的極限，當網(wǎng)絡(luò)的需求超過它們的工作極限時，就出現(xiàn)了擁塞。擁塞控制就是防止過多的數(shù)據(jù)注入到網(wǎng)絡(luò)中，這樣可以使網(wǎng)絡(luò)中的路由器或鏈路不致過載。

慢開始（Slow-Start）和擁塞避免（Congestion Avoidance）結(jié)合

慢開始算法是指開始發(fā)送數(shù)據(jù)時，并不清楚網(wǎng)絡(luò)的負荷情況，會先發(fā)送一個1字節(jié)的試探報文，當收到確認后，就發(fā)送2個字節(jié)的報文，繼而4個，8個以此指數(shù)類推。

需要注意的是，慢開始的“慢”并不是指擁塞窗口的增長速率慢，而是指在TCP開始發(fā)送報文時先設(shè)置擁塞窗口=1。
擁塞避免算法是讓擁塞窗口緩慢地增大，即cwnd加1，而不是如慢開始算法一樣加倍。、

擁塞窗口變化

根據(jù)上圖的實例進行分析，一開始的慢開始算法的指數(shù)增長是很恐怖的，所以為了防止擁塞窗口cwnd增長過快需要設(shè)置一個門限ssthresh，這里是16。

當 cwnd < ssthresh 時，使用上述的慢開始算法。
當 cwnd > ssthresh 時，停止使用慢開始算法而改用擁塞避免算法。
當 cwnd = ssthresh 時，既可使用慢開始算法，也可使用擁塞控制避免算法。

對超時事件作出反應(yīng)

在上述對擁塞窗口的描述中，我們只是說在連接開始的時候，以指數(shù)級的速率增加，直到第一個丟失事件發(fā)生。但實際中TCP對因超時而檢測到的丟包事件作出的反應(yīng)與對因收到3個冗余ACK而檢測到的丟包事件做出的反應(yīng)是不同的。

收到3個冗余ACK后：CongWin減半、窗口再線性增加。
檢測超時事件后：CongWin值設(shè)置為1MSS、窗口再指數(shù)增長、到達一個閾值(Threshold，初始化時被設(shè)置為一個很大的值，以使它沒有初始效應(yīng)。每發(fā)生一個丟包事件，Threshold就會被設(shè)置為當前CongWin值的一半)后，再線性增長。

原因：3個冗余ACK指示網(wǎng)絡(luò)還具有某些傳送報文段的能力；3個冗余ACK以前的超時,則更為 “嚴重”。

小結(jié)：

當CongWin < Threshold時，發(fā)送者處于慢啟動階段, CongWin指數(shù)增長。
當CongWin > Threshold時，發(fā)送者處于擁塞避免階段, CongWin線性增長。
當出現(xiàn)3個冗余確認時, 閾值Threshold設(shè)置為CongWin/2，且CongWin設(shè)置為Threshold。
當超時發(fā)生時，閾值Threshold設(shè)置為CongWin/2，并且CongWin設(shè)置為1 MSS.

快重傳（Fast Retransmit）和快恢復(fù)（Fast Recovery）結(jié)合

快重傳是指，如果發(fā)送端接收到3個以上的重復(fù)ACK，不需要等到重傳定時器溢出就重新傳遞，所以叫做快速重傳，而快速重傳以后，因為走的不是慢啟動而是擁塞避免算法，所以這又叫做快速恢復(fù)算法。

如果沒有快速重傳和快速恢復(fù)，TCP將會使用定時器來要求傳輸暫停。在暫停這段時間內(nèi)，沒有新的數(shù)據(jù)包被發(fā)送。所以快速重傳和快速恢復(fù)旨在快速恢復(fù)丟失的數(shù)據(jù)包。

快速重傳

與快重傳配合使用的還有快恢復(fù)算法，結(jié)合下圖的實例來分析，其過程有以下兩個要點：

快恢復(fù)

當發(fā)送方在cwnd=24時連續(xù)收到三個重復(fù)確認，就把慢開始門限ssthresh減半（就是上圖中的24修改為12）。
接下來不執(zhí)行慢開始算法，而是把cwnd值設(shè)置為門限ssthresh減半后的數(shù)值（即cwnd不是設(shè)置為1而是設(shè)置為12），然后開始執(zhí)行的是擁塞避免算法，使擁塞窗口緩慢地線性增大。

這里為什么替換掉了慢開始算法呢？

這是因為收到重復(fù)的ACK不僅僅告訴我們一個分組丟失了，由于接收方只有在收到另一個報文段時才會產(chǎn)生重復(fù)的ACK，所以還告訴我們該報文段已經(jīng)進入了接收方的緩存。也就是說，在收發(fā)兩端之間仍然有流動的數(shù)據(jù)，而我們不想執(zhí)行慢啟動來突然減少數(shù)據(jù)流。

TCP客戶與服務(wù)器模型，用到哪些函數(shù)

服務(wù)端：

創(chuàng)建套接字：int socket(int family,int type,int protocol);返回：非負描述字－－－成功　　　-1－－－失敗
綁定套接字：把一個套接字地址（本機IP和端口號）綁定到創(chuàng)建的套接字上
int bind(int sockfd, const struct sockaddr * server, socklen_t addrlen);
返回：0－－－成功　　　-1－－－失敗
監(jiān)聽套接字：int listen(int sockfd, int backlog);backlog是已完成隊列和未完成隊列大小之和
等待來自客戶端的連接請求：int accept(int listenfd, struct sockaddr *client, socklen_t * addrlen); 　返回已連接描述符
數(shù)據(jù)傳輸：
int write(int sockfd, char *buf, int len);　
int read(int sockfd, char *buf, intlen); 　
send和recv函數(shù)：TCP套接字提供了send()和recv()函數(shù)，用來發(fā)送和接收操作。這兩個函數(shù)與write()和read()函數(shù)很相似，只是多了一個附加的傳輸控制參數(shù)。
關(guān)閉套接字：int close(int sockfd);

客戶端：

連接服務(wù)器：int connect(int sockfd, const struct sockaddr * addr, socklen_t addrlen);
返回：0－－－成功　　　-1－－－失敗

UDP客戶與服務(wù)器模型，用到哪些函數(shù)

UDP與TCP相比要簡潔很多，UDP不需要listen，accept和connect過程。

socket函數(shù)創(chuàng)建套接字
sockfd = socket(AF_INET, SOCK_DGRAM, 0)；
bind函數(shù)，綁定服務(wù)器地址到套接字上
int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
sendto函數(shù)，發(fā)送數(shù)據(jù)給指定地址
sendto函數(shù)比send函數(shù)多出兩個參數(shù)，一個是目的地址，一個是地址長度。告訴客戶端發(fā)送給哪個IP地址和哪個端口號。
recvfrom函數(shù)，接收數(shù)據(jù)
recvfrom函數(shù)比recv函數(shù)多出兩個參數(shù)，相當于TCP的accept函數(shù)，告訴我們是誰發(fā)送了數(shù)據(jù)過來。

域名解析過程，ARP的機制，RARP的實現(xiàn)

ARP（地址解析協(xié)議）

ARP協(xié)議是輔助鏈路層傳輸?shù)?，在已?jīng)知道下一站路由器的IP地址后，要將以太網(wǎng)包發(fā)送給目的地址，但是以太網(wǎng)需要的是目的mac地址不是IP地址，而通過ARP請求包就可以獲得目的IP地址的mac地址。

ARP請求的過程：源主機以廣播的形式，發(fā)送一個ARP請求包，所有與源主機在直連的主機都會收到一個請求包，如下圖所示，請求包詢問目的IP地址的mac地址，目的IP地址的主機收到這個請求后，發(fā)送一個ARP應(yīng)答，告訴源主機自己的mac地址。

RARP以與ARP相反的方式工作。RARP發(fā)出要反向解析的物理地址并希望返回其對應(yīng)的IP地址，應(yīng)答包括由能夠提供所需信息的RARP服務(wù)器發(fā)出的IP地址。

Ping和TraceRoute實現(xiàn)原理

Ping是通過發(fā)送ICMP報文回顯請求實現(xiàn)。
ICMP是（Internet Control Message Protocol）Internet控制報文協(xié)議,用于在IP主機、路由器之間傳遞控制消息。
Tracert 命令用 IP 生存時間 (TTL) 字段和 ICMP 錯誤消息來確定從一個主機到網(wǎng)絡(luò)上其他主機的路由。

首先，tracert送出一個TTL是1的IP 數(shù)據(jù)包到目的地，當路徑上的第一個路由器收到這個數(shù)據(jù)包時，它將TTL減1。此時，TTL變?yōu)?，所以該路由器會將此數(shù)據(jù)包丟掉，并送回一個「ICMP time exceeded」消息（包括發(fā)IP包的源地址，IP包的所有內(nèi)容及路由器的IP地址），tracert 收到這個消息后，便知道這個路由器存在于這個路徑上，接著tracert 再送出另一個TTL是2 的數(shù)據(jù)包，發(fā)現(xiàn)第2 個路由器...... tracert 每次將送出的數(shù)據(jù)包的TTL 加1來發(fā)現(xiàn)另一個路由器，這個重復(fù)的動作一直持續(xù)到某個數(shù)據(jù)包抵達目的地。當數(shù)據(jù)包到達目的地后，該主機則不會送回ICMP time exceeded消息，一旦到達目的地，由于tracert通過UDP數(shù)據(jù)包向不常見端口(30000以上)發(fā)送數(shù)據(jù)包，因此會收到「ICMP port unreachable」消息，故可判斷到達目的地。
tracert 有一個固定的時間等待響應(yīng)(ICMP TTL到期消息)。如果這個時間過了，它將打印出一系列的*號表明：在這個路徑上，這個設(shè)備不能在給定的時間內(nèi)發(fā)出ICMP TTL到期消息的響應(yīng)。然后，Tracert給TTL記數(shù)器加1，繼續(xù)進行。

HTTP

HTTP/HTTPS 1.0、1.1、2.0

HTTP的主要特點

簡單快速：當客戶端向服務(wù)器端發(fā)送請求時，只是簡單的填寫請求路徑和請求方法即可
靈活：HTTP 協(xié)議允許客戶端和服務(wù)器端傳輸任意類型任意格式的數(shù)據(jù)對象
無連接：無連接的含義是限制每次連接只處理一個請求。服務(wù)器處理完客戶的請求，并收到客戶的應(yīng)答后，即斷開連接，采用這種方式可以節(jié)省傳輸時間。(當今多數(shù)服務(wù)器支持Keep-Alive功能，使用服務(wù)器支持長連接，解決無連接的問題)
無狀態(tài)：無狀態(tài)是指協(xié)議對于事務(wù)處理沒有記憶能力，服務(wù)器不知道客戶端是什么狀態(tài)。即客戶端發(fā)送HTTP請求后，服務(wù)器根據(jù)請求，會給我們發(fā)送數(shù)據(jù)，發(fā)送完后，不會記錄信息。(使用 cookie 機制可以保持 session，解決無狀態(tài)的問題)

HTTP 1.1 的特點

默認持久連接節(jié)省通信量，只要客戶端服務(wù)端任意一端沒有明確提出斷開TCP連接，就一直保持連接，可以發(fā)送多次HTTP請求
管線化，客戶端可以同時發(fā)出多個HTTP請求，而不用一個個等待響應(yīng)
斷點續(xù)傳

http2.0的特點

HTTP/2采用二進制格式而非文本格式
HTTP/2是完全多路復(fù)用的，而非有序并阻塞的——只需一個HTTP連接就可以實現(xiàn)多個請求響應(yīng)
使用報頭壓縮，HTTP/2降低了開銷
HTTP/2讓服務(wù)器可以將響應(yīng)主動“推送”到客戶端緩存中

GET和POST的區(qū)別

本質(zhì)上

GET是向服務(wù)器索取數(shù)據(jù)的請求
POST是向服務(wù)器提交數(shù)據(jù)的請求
GET是等冪的，POST不是等冪的，等冪就是一次執(zhí)行和多次執(zhí)行效果一樣！DELETE，PUT，HEAD，也是等冪的，由于網(wǎng)絡(luò)是不可靠的，安全性和等冪性就特別重要，如果POST兩次相同的，會產(chǎn)生兩個資源。

表現(xiàn)上

GET，服務(wù)器端用request.QueryString獲取變量的值，POST，服務(wù)器端用request.Form獲取數(shù)據(jù)
get傳輸數(shù)據(jù)是通過URL請求，以field（字段）= value的形式，置于URL后，并用"?"連接，多個請求數(shù)據(jù)間用"&"連接，如http://127.0.0.1/Test/login.action?name=admin&password=admin，這個過程用戶是可見的；post傳輸數(shù)據(jù)通過Http的post機制，將字段與對應(yīng)值封存在請求實體中發(fā)送給服務(wù)器，這個過程對用戶是不可見的；
GET安全性低，用戶可見，POST安全性高些
GET效率高些，只發(fā)送一次數(shù)據(jù)包，POST會發(fā)送兩次TCP數(shù)據(jù)包（先header，再data）
數(shù)據(jù)量大小：URL不存在參數(shù)上限，取決于特定的瀏覽器或服務(wù)器限制，POST數(shù)據(jù)理論上也沒有限制

返回狀態(tài)碼

100：請求者應(yīng)當繼續(xù)提出請求。服務(wù)器返回此代碼則意味著，服務(wù)器已收到了請求的第一部分，現(xiàn)正在等
待接收其余部分。
101（切換協(xié)議）請求者已要求服務(wù)器切換協(xié)議，服務(wù)器已確認并準備進行切換。

200：請求被正常處理
204：請求被受理但沒有資源可以返回
206：客戶端只是請求資源的一部分，服務(wù)器只對請求的部分資源執(zhí)行GET方法，相應(yīng)報文中通過Content-Range指定范圍的資源。
301：永久性重定向
302：臨時重定向
303：與302狀態(tài)碼有相似功能，只是它希望客戶端在請求一個URI的時候，能通過GET方法重定向到另一個URI上
304：發(fā)送附帶條件的請求時，條件不滿足時返回，與重定向無關(guān)
307：臨時重定向，與302類似，只是強制要求使用POST方法
400：請求報文語法有誤，服務(wù)器無法識別
401：請求需要認證
403：請求的對應(yīng)資源禁止被訪問
404：服務(wù)器無法找到對應(yīng)資源
500：服務(wù)器內(nèi)部錯誤
503：服務(wù)器正忙

HTTP 協(xié)議頭相關(guān)

http數(shù)據(jù)由請求行，首部字段，空行，報文主體四個部分組成
首部字段分為：通用首部字段，請求首部字段，響應(yīng)首部字段，實體首部字段

https與http的區(qū)別？如何實現(xiàn)加密傳輸？

https就是在http與傳輸層之間加上了一個SSL
對稱加密與非對稱加密：非對稱加密和解密使用的是兩個不同的密鑰，公鑰和私鑰，不需要交換密鑰

瀏覽器中輸入一個URL發(fā)生什么，用到哪些協(xié)議？

瀏覽器中輸入URL，首先瀏覽器要將URL解析為IP地址，解析域名就要用到DNS協(xié)議，首先主機會查詢DNS的緩存，如果沒有就給本地DNS發(fā)送查詢請求。DNS查詢分為兩種方式，一種是遞歸查詢，一種是迭代查詢。如果是迭代查詢，本地的DNS服務(wù)器，向根域名服務(wù)器發(fā)送查詢請求，根域名服務(wù)器告知該域名的一級域名服務(wù)器，然后本地服務(wù)器給該一級域名服務(wù)器發(fā)送查詢請求，然后依次類推直到查詢到該域名的IP地址。DNS服務(wù)器是基于UDP的，因此會用到UDP協(xié)議。

得到IP地址后，瀏覽器就要與服務(wù)器建立一個http連接。因此要用到http協(xié)議，http協(xié)議報文格式上面已經(jīng)提到。http生成一個get請求報文，將該報文傳給TCP層處理。如果采用https還會先對http數(shù)據(jù)進行加密。TCP層如果有需要先將HTTP數(shù)據(jù)包分片，分片依據(jù)路徑MTU和MSS。TCP的數(shù)據(jù)包然后會發(fā)送給IP層，用到IP協(xié)議。IP層通過路由選路，一跳一跳發(fā)送到目的地址。當然在一個網(wǎng)段內(nèi)的尋址是通過以太網(wǎng)協(xié)議實現(xiàn)(也可以是其他物理層協(xié)議，比如PPP，SLIP)，以太網(wǎng)協(xié)議需要直到目的IP地址的物理地址，有需要ARP協(xié)議。

數(shù)據(jù)庫

SQL語言(內(nèi)外連接，子查詢，分組，聚集，嵌套，邏輯)

MySQL索引方法？索引的優(yōu)化？

InnoDB與MyISAM區(qū)別？

事務(wù)的ACID

事務(wù)的四個隔離級別

查詢優(yōu)化(從索引上優(yōu)化，從SQL語言上優(yōu)化)

B-與B+樹區(qū)別？

MySQL的聯(lián)合索引(又稱多列索引)是什么？生效的條件？

分庫分表

Linux

進程與線程

進程與線程區(qū)別
1. 進程是資源分配的基本單位，線程是cpu調(diào)度，或者說是程序執(zhí)行的最小單位。但是并不是說CPU不在以進程為單位進行調(diào)度，雖然在某些操作系統(tǒng)中是這樣。同一個進程中并行運行多個線程，就是對在同一臺計算機上運行多個進程的模擬。
2. 進程有獨立的地址空間，而同一進程中的線程共享該進程的地址空間。比如在linux下面啟動一個新的進程，系統(tǒng)必須分配給它獨立的地址空間，建立眾多的數(shù)據(jù)表來維護它的代碼段、堆棧段和數(shù)據(jù)段，這是一種非常昂貴的多任務(wù)工作方式。而運行一個進程中的線程，它們之間共享大部分數(shù)據(jù)，使用相同的地址空間，因此啟動一個線程，切換一個線程遠比進程操作要快，花費也要小得多。
3. 線程之間的通信比較方便。統(tǒng)一進程下的線程共享數(shù)據(jù)（比如全局變量，靜態(tài)變量，打開的文件，子進程）
4. 多進程比多線程程序要健壯。一個線程死掉整個進程就死掉了，但是在保護模式下，一個進程死掉對另一個進程沒有直接影響。
5. 線程的執(zhí)行與進程是有區(qū)別的。每個獨立的線程有有自己的一個程序入口，順序執(zhí)行序列和程序的出口，但是線程不能獨立執(zhí)行，必須依附與程序之中，由應(yīng)用程序提供多個線程的并發(fā)控制。
6. linux中進程具有父子關(guān)系，形成進程樹，但是線程是平等的沒有父子關(guān)系
多線程VS多進程？
1. 多進程程序，一個進程崩潰不會影響其他進程，但是進程之間的切換和通信代價較大；
2. 多線程程序，一個線程崩潰會導(dǎo)致整個進程死掉，其他線程也不能正常工作，但是線程之前數(shù)據(jù)共享和通信更加方便。
3. 進程需要開辟獨立的地址空間，多進程對資源的消耗很大，而線程則是“輕量級進程”，對資源的消耗更小，對于大并發(fā)的情況，只有線程加上IO復(fù)用技術(shù)才能適應(yīng)。
因此，對于需要頻繁交互數(shù)據(jù)的，頻繁的對同一個對象進行不同的處理，選擇多線程合適，對于一些并發(fā)編程，不需要很多數(shù)據(jù)交互的采用多進程。
用線程的好處
1. 一個任務(wù)可以分成多個子任務(wù)并行執(zhí)行，他們是對一個對象在操作。
2. 線程不需要像進程一樣維護那么多信息，因此創(chuàng)建和銷毀速度更快，擁有同一個地址空間，訪問很容易
3. 任務(wù)有CPU密集和IO等待的過程，使用線程可以最大化利用CPU

進程的內(nèi)存空間布局

進程的內(nèi)存布局在結(jié)構(gòu)上是有規(guī)律的，具體來說對于linux系統(tǒng)上的進程，其內(nèi)存空間一般可以粗略地分為以下幾大段，從高內(nèi)存到低內(nèi)存排列：

內(nèi)核態(tài)內(nèi)存空間，其大小一般比較固定（可以編譯時調(diào)整），但 32 位系統(tǒng)和 64 位系統(tǒng)的值不一樣。
用戶態(tài)的棧，大小不固定，可以用 ulimit -s 進行調(diào)整，默認一般為 8M，從高地址向低地址增長。
共享內(nèi)存區(qū)，包括動態(tài)共享庫以及mmap內(nèi)存映射的區(qū)域
堆，由程序員手動分配
數(shù)據(jù)段，bss 未初始化以及 data 已初始化的全局靜態(tài)變量等
代碼段，二進制文件

進程的內(nèi)存空間.png

[圖片上傳失敗...(image-42ade8-1525264842791)]

進程間通信方式

信號量：信號量用于實現(xiàn)進程間的互斥與同步，而不是用于存儲進程間通信數(shù)據(jù)。
管道( pipe )：管道是一種半雙工的通信方式，數(shù)據(jù)只能單向流動，而且只能在具有親緣關(guān)系的進程間使用。進程的親緣關(guān)系通常是指父子進程關(guān)系。
命名管道 (named pipe) ：有名管道也是半雙工的通信方式，但是它允許無親緣關(guān)系進程間的通信。
消息隊列( message queue ) ：消息隊列是由消息的鏈表，存放在內(nèi)核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。
信號 ( sinal ) ：信號是一種比較復(fù)雜的通信方式，用于通知接收進程某個事件已經(jīng)發(fā)生。
共享內(nèi)存( shared memory ) ：共享內(nèi)存就是映射一段能被其他進程所訪問的內(nèi)存，這段共享內(nèi)存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內(nèi)存是最快的 IPC 方式，它是針對其他進程間通信方式運行效率低而專門設(shè)計的。它往往與其他通信機制，如信號兩，配合使用，來實現(xiàn)進程間的同步和通信。
套接字( socket ) ：套解口也是一種進程間通信機制，與其他通信機制不同的是，它可用于不同及其間的進程通信。

匿名管道與命名管道的區(qū)別：匿名管道只能在具有公共祖先的兩個進程間使用

共享文件映射mmap

mmap建立進程空間到文件的映射，在建立的時候并不直接將文件拷貝到物理內(nèi)存，同樣采用缺頁終端。mmap映射一個具體的文件可以實現(xiàn)任意進程間共享內(nèi)存，映射一個匿名文件，可以實現(xiàn)父子進程間共享內(nèi)存。

常見信號

SIGINT 終止進程，通常我們的Ctrl+C就發(fā)送的這個消息。
SIGKILL 消息編號為9，我們經(jīng)常用kill -9來殺死進程發(fā)送的就是這個消息，程序收到這個消息立即終止，這個消息不能被捕獲，封鎖或這忽略，所以是殺死進程的終極武器。
SIGTERM 是不帶參數(shù)時kill默認發(fā)送的信號，默認是殺死進程。(可以被捕獲）
SIGSEGV 就是SegmentFault 試圖訪問未分配給自己的內(nèi)存, 或試圖往沒有寫權(quán)限的內(nèi)存地址寫數(shù)據(jù)
SIGCHLD 一個子進程停止或終止，默認行為忽略
SIGALRM 來自alarm函數(shù)的定時信號，默認行為終止

內(nèi)存管理

虛擬內(nèi)存

操作系統(tǒng)對內(nèi)存的管理

幾種數(shù)據(jù)結(jié)構(gòu)：

位圖
空閑塊鏈表

內(nèi)存分配算法：

首次適配first fit
下次適配next fit從上次找到的空閑區(qū)接著找
最佳適配best fit查找整個空閑區(qū)表，能滿足要求的最小空閑區(qū)
最差適配worst fit總是分配最大空閑區(qū)

內(nèi)存池

內(nèi)存池的作用：

在C和C++語言中，經(jīng)常需要動態(tài)分配內(nèi)存，我們會用到new，delete，malloc，free。但是當我們分配很多小塊的內(nèi)存時，會造成很多的內(nèi)存碎片，大大降低了內(nèi)存的使用效率。為了減少內(nèi)存碎片的出現(xiàn)，采用了內(nèi)存池技術(shù)。

內(nèi)存池的實現(xiàn)原理：

內(nèi)存池的先調(diào)用malloc函數(shù)申請一大塊內(nèi)存，然后維護一個空閑鏈表，該鏈表是一個個小的空閑內(nèi)存片，每當需要內(nèi)存時就從空閑鏈表上拿過來一個小片內(nèi)存使用。如果空閑鏈表為空了，就從之前分配的大塊內(nèi)存去取幾個插入到空閑鏈表上。如果分配的大塊內(nèi)存也用光了，就繼續(xù)用malloc申請一大塊。

進程空間和內(nèi)核空間對內(nèi)存的管理不同？

linux的slab層

slab是Linux操作系統(tǒng)的一種內(nèi)存分配機制。其工作是針對一些經(jīng)常分配并釋放的對象，如進程描述符等，這些對象的大小一般比較小，如果直接采用伙伴系統(tǒng)來進行分配和釋放，不僅會造成大量的內(nèi)存碎片，而且處理速度也太慢。而slab分配器是基于對象進行管理的，相同類型的對象歸為一類(如進程描述符就是一類)，每當要申請這樣一個對象，slab分配器就從一個slab列表中分配一個這樣大小的單元出去，而當要釋放時，將其重新保存在該列表中，而不是直接返回給伙伴系統(tǒng)，從而避免這些內(nèi)碎片。slab分配器并不丟棄已分配的對象，而是釋放并把它們保存在內(nèi)存中。當以后又要請求新的對象時，就可以從內(nèi)存直接獲取而不用重復(fù)初始化。

伙伴算法

解決問題：頻繁地請求和釋放不同大小的一組連續(xù)頁框，必然導(dǎo)致在已分配頁框的塊內(nèi)分散了許多小塊的空閑頁面，由此帶來的問題是，即使有足夠的空閑頁框可以滿足請求，但要分配一個大塊的連續(xù)頁框可能無法滿足請求。

伴算法雖然能夠完全避免外部碎片的產(chǎn)生，但這恰恰是以產(chǎn)生內(nèi)部碎片為代價的。

優(yōu)點：

較好解決外部碎片問題
當需要分配若干個內(nèi)存頁面時，用于DMA的內(nèi)存頁面必須連續(xù)，伙伴算法很好的滿足了這個要求
只要請求的塊不超過512個頁面(2K)，內(nèi)核就盡量分配連續(xù)的頁面。
針對大內(nèi)存分配設(shè)計。

缺點：

合并的要求太過嚴格，只能是滿足伙伴關(guān)系的塊才能合并，比如第1塊和第2塊就不能合并。
碎片問題：一個連續(xù)的內(nèi)存中僅僅一個頁面被占用，導(dǎo)致整塊內(nèi)存區(qū)都不具備合并的條件
浪費問題：伙伴算法只能分配2的冪次方內(nèi)存區(qū)，當需要8K（2頁）時，好說，當需要9K時，那就需要分配16K（4頁）的內(nèi)存空間，但是實際只用到9K空間，多余的7K空間就被浪費掉。
算法的效率問題：伙伴算法涉及了比較多的計算還有鏈表和位圖的操作，開銷還是比較大的，如果每次2^{n大小的伙伴塊就會合并到2}(n+1)的鏈表隊列中，那么2^{n大小鏈表中的塊就會因為合并操作而減少，但系統(tǒng)隨后立即有可能又有對該大小塊的需求，為此必須再從2}(n+1)大小的鏈表中拆分，這樣的合并又立即拆分的過程是無效率的。

所有的空閑頁框分組為 11 塊鏈表，每一塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512 和 1024 個連續(xù)的頁框。

實現(xiàn)原理：

假設(shè)要請求一個256（129~256）個頁框的塊。算法先在256個頁框的鏈表中檢查是否有一個空閑塊。如果沒有這樣的塊，算法會查找下一個更大的頁塊，也就是，在512個頁框的鏈表中找一個空閑塊。如果存在這樣的塊，內(nèi)核就把512的頁框分成兩等分，一般用作滿足需求，另一半則插入到256個頁框的鏈表中。如果在512個頁框的塊鏈表中也沒找到空閑塊，就繼續(xù)找更大的塊——1024個頁框的塊。如果這樣的塊存在，內(nèi)核就把1024個頁框塊的256個頁框用作請求，然后剩余的768個頁框中拿512個插入到512個頁框的鏈表中，再把最后的256個插入到256個頁框的鏈表中。如果1024個頁框的鏈表還是空的，算法就放棄并發(fā)出錯誤信號。

高端內(nèi)存？

Linux是如何避免內(nèi)存碎片的

伙伴算法，用于管理物理內(nèi)存，避免內(nèi)存碎片;
高速緩存Slab層用于管理內(nèi)核分配內(nèi)存，避免碎片。

共享內(nèi)存的實現(xiàn)原理？

共享內(nèi)存實現(xiàn)分為兩種方式一種是采用mmap，另一種是采用XSI機制中的共享內(nèi)存方法。mmap是內(nèi)存文件映射，將一個文件映射到進程的地址空間，用戶進程的地址空間的管理是通過vm_area_struct結(jié)構(gòu)體進行管理的。mmap通過映射一個相同的文件到兩個不同的進程，就能實現(xiàn)這兩個進程的通信，采用該方法可以實現(xiàn)任意進程之間的通信。mmap也可以采用匿名映射，不指定映射的文件，但是只能在父子進程間通信。XSI的內(nèi)存共享實際上也是通過映射文件實現(xiàn)，只是其映射的是一種特殊文件系統(tǒng)下的文件，該文件是不能通過read和write訪問的。

同步方法有哪些？

互斥鎖，自旋鎖，信號量，讀寫鎖，屏障
互斥鎖與自旋鎖的區(qū)別：互斥鎖得不到資源的時候阻塞，不占用cpu資源。自旋鎖得不到資源的時候，不停的查詢，而然占用cpu資源。

++i是否是原子操作

明顯不是，++i主要有三個步驟，把數(shù)據(jù)從內(nèi)存放在寄存器上，在寄存器上進行自增，把數(shù)據(jù)從寄存器拷貝會內(nèi)存，每個步驟都可能被中斷。

大小端

大端模式，是指數(shù)據(jù)的高字節(jié)保存在內(nèi)存的低地址中，而數(shù)據(jù)的低字節(jié)保存在內(nèi)存的高地址中，這樣的存儲模式有點兒類似于把數(shù)據(jù)當作字符串順序處理：地址由小向大增加，而數(shù)據(jù)從高位往低位放；這和我們的閱讀習慣一致。

小端模式，是指數(shù)據(jù)的高字節(jié)保存在內(nèi)存的高地址中，而數(shù)據(jù)的低字節(jié)保存在內(nèi)存的低地址中，這種存儲模式將地址的高低和數(shù)據(jù)位權(quán)有效地結(jié)合起來，高地址部分權(quán)值高，低地址部分權(quán)值低。

大小端

判斷大小端

union un
{
int i;
char ch;
};
void fun()
{
union un test;
test.i = 1;
if(ch == 1)
cout << "小端" << endl;
else
cout << "大端" << endl;
}

如何判斷操作系統(tǒng)是32位還是64位？

Linux指令uname
利用sizeof，判斷指針大小，或者其他變量，如long, unsigned long
機器位數(shù)不同，表示的數(shù)字最大值也不同
對0值取反，判斷是不是大于32位下所能表示的最大數(shù)

其他

設(shè)計模式

單例模式線程安全寫法，參考12. C++寫一個線程安全的單例模式
STL里的迭代器使用了迭代器模式
MVC的理解

分布式系統(tǒng)

mapreduce
負載均衡
CDN

C++后臺開發(fā)面試常見問題匯總

static在C++中對于靜態(tài)成員變量和靜態(tài)成員函數(shù)。所有的對象都只維持同一個實例。相當于類的屬性