stl容器總結(jié)：

• 各種容器的元素在內(nèi)存中的儲存方式

1. vector（向量）：相當(dāng)于數(shù)組，但其大小可以不預(yù)先指定，并且自動擴展。它可以像數(shù)組一樣被操作，
   由于它的特性我們完全可以將vector 看作動態(tài)數(shù)組。在創(chuàng)建一個vector 后，它會自動在內(nèi)存中分配一塊連續(xù)的
   內(nèi)存空間進(jìn)行數(shù)據(jù)存儲，初始的空間大小可以預(yù)先指定也可以由vector 默認(rèn)指定，這個大小即capacity()函數(shù)的返回值。當(dāng)存儲的數(shù)據(jù)超過分配的空間時vector 會重新分配一塊內(nèi)存塊，但這樣的分配是很耗時的，效率非常低。

2. deque（隊列）：它不像vector 把所有的對象保存在一塊連續(xù)的內(nèi)存塊，而是采用多個連續(xù)的存儲塊，并且在一個映射結(jié)構(gòu)中保存對這些塊及其順序的跟蹤。向deque 兩端添加或刪除元素的開銷很小，它不需要重新分配空間。

3. list（列表）：是一個線性鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個節(jié)點構(gòu)成，每一個節(jié)點都包括一個信息塊（即實際存儲的數(shù)據(jù)）、一個前驅(qū)指針和一個后驅(qū)指針。它無需分配指定的內(nèi)存大小且可以任意伸縮，這是因為它存儲在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來。

4. set, multiset, map, multimap 是一種非線性的樹結(jié)構(gòu)，具體的說采用的是一種比較高效的特殊的平衡檢索二叉樹—— 紅黑樹結(jié)構(gòu)。

• 各種容器優(yōu)劣分析

1. Vector：

• 優(yōu)點：
  A、支持隨機訪問，訪問效率高和方便，它像數(shù)組一樣被訪問，即支持[ ] 操作符和vector.at()。
  B、節(jié)省空間，因為它是連續(xù)存儲，在存儲數(shù)據(jù)的區(qū)域都是沒有被浪費的，但是要明確一點vector 大多情況下并不是滿存的，在未存儲的區(qū)域?qū)嶋H是浪費的。
• 缺點：
  A、在內(nèi)部進(jìn)行插入、刪除操作效率非常低。
  B、只能在vector 的最后進(jìn)行push 和pop ，不能在vector 的頭進(jìn)行push 和pop 。
  C、 當(dāng)動態(tài)添加的數(shù)據(jù)超過vector 默認(rèn)分配的大小時要進(jìn)行內(nèi)存的重新分配、拷貝與釋放，這個操作非常消耗能。

2. List：

• 優(yōu)點：不使用連續(xù)的內(nèi)存空間這樣可以隨意地進(jìn)行動態(tài)操作，插入、刪除操作效率高；
• 缺點：
  A、不能進(jìn)行內(nèi)部的隨機訪問，即不支持[ ] 操作符和vector.at()，訪問效率低。
  B、相對于verctor 占用更多的內(nèi)存。

3. Deque：

• 優(yōu)點：
  A、支持隨機訪問，方便，即支持[ ] 操作符和vector.at() ，但性能沒有vector 好；
  B、可以在兩端進(jìn)行push 、pop 。
  缺點：在內(nèi)部進(jìn)行插入、刪除操作效率低。

綜合：
vector 的查詢性能最好，并且在末端增加數(shù)據(jù)也很好，除非它重新申請內(nèi)存段；適合高效地隨機存儲。
list 是一個鏈表，任何一個元素都可以是不連續(xù)的，但它都有兩個指向上一元素和下一元素的指針。所以它對插入、刪除元素性能是最好的，而查詢性能非常差；適合 大量地插入和刪除操作而不關(guān)心隨機存取的需求。
deque 是介于兩者之間，它兼顧了數(shù)組和鏈表的優(yōu)點，它是分塊的鏈表和多個數(shù)組的聯(lián)合。所以它有被list 好的查詢性能，有被vector 好的插入、刪除性能。 如果你需要隨即存取又關(guān)心兩端數(shù)據(jù)的插入和刪除，那么deque 是最佳之選。

3. 關(guān)聯(lián)容器的特點是明顯的，相對于順序容器，有以下幾個主要特點：
   A. 其內(nèi)部實現(xiàn)是采用非線性的二叉樹結(jié)構(gòu)，具體的說是紅黑樹的結(jié)構(gòu)原理實現(xiàn)的；
   B. set 和map 保證了元素的唯一性，mulset 和mulmap 擴展了這一屬性，可以允許元素不唯一；
   C. 元素是有序的集合，默認(rèn)在插入的時候按升序排列。

基于以上特點
A. 關(guān)聯(lián)容器對元素的插入和刪除操作比vector 要快，因為vector 是順序存儲，而關(guān)聯(lián)容器是鏈?zhǔn)酱鎯?；比list 要慢，是因為即使它們同是鏈?zhǔn)浇Y(jié)構(gòu)，但list 是線性的，而關(guān)聯(lián)容器是二叉樹結(jié)構(gòu)，其改變一個元素涉及到其它元素的變動比list 要多，并且它是排序的，每次插入和刪除都需要對元素重新排序；

B. 關(guān)聯(lián)容器對元素的檢索操作比vector 慢，但是比list 要快很多。vector 是順序的連續(xù)存儲，當(dāng)然是比不上的，但相對鏈?zhǔn)降膌ist 要快很多是因為list 是逐個搜索，它搜索的時間是跟容器的大小成正比，而關(guān)聯(lián)容器 查找的復(fù)雜度基本是Log(N) ，比如如果有1000 個記錄，最多查找10 次，1,000,000 個記錄，最多查找20 次。容器越大，關(guān)聯(lián)容器相對list 的優(yōu)越性就越能體現(xiàn)；

C. 在使用上set 區(qū)別于vector,deque,list 的最大特點就是set 是內(nèi)部排序的，這在查詢上雖然遜色于vector ，但是卻大大的強于list 。

D. 在使用上map 的功能是不可取代的，它保存了“鍵- 值”關(guān)系的數(shù)據(jù)，而這種鍵值關(guān)系采用了類數(shù)組的方式。數(shù)組是用數(shù)字類型的下標(biāo)來索引元素的位置，而map 是用字符型關(guān)鍵字來索引元素的位置。在使用上map 也提供了一種類數(shù)組操作的方式，即它可以通過下標(biāo)來檢索數(shù)據(jù)，這是其他容器做不到的，當(dāng)然也包括set 。（STL 中只有vector 和map 可以通過類數(shù)組的方式操作元素，即如同ele[1] 方式）。

• stl用過哪些容器？有沒有看過源碼？比如vector原理有沒有了解，vector插入元素會發(fā)生什么？（提到allocator原理，追問二級分配器的內(nèi)存池有幾個空閑鏈表）

unordered_map和map區(qū)別，如何避免哈希沖突？

• 運行效率方面：unordered_map最高，而map效率較低但 提供了穩(wěn)定效率和有序的序列。
• 占用內(nèi)存方面：map內(nèi)存占用略低，unordered_map內(nèi)存占用略高,而且是線性成比例的。
• 需要無序容器，快速查找刪除，不擔(dān)心略高的內(nèi)存時用unordered_map；有序容器穩(wěn)定查找刪除效率，內(nèi)存很在意時候用map。
• map的內(nèi)部實現(xiàn)是二叉平衡樹(紅黑樹)；hash_map內(nèi)部是一個hash_table一般是由一個大vector，vector元素節(jié)點可掛接鏈表來解決沖突，來實現(xiàn).

hash_map其插入過程是：
1）得到key
2）通過hash函數(shù)得到hash值
3）得到桶號(一般都為hash值對桶數(shù)求模)
4）存放key和value在桶內(nèi)。

其取值過程是:
1）得到key
2）通過hash函數(shù)得到hash值
3）得到桶號(一般都為hash值對桶數(shù)求模)
4）比較桶的內(nèi)部元素是否與key相等，若都不相等，則沒有找到。
5）取出相等的記錄的value。

避免哈希沖突的四種方法
1）鏈地址法：是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。 適合頻繁進(jìn)行插入和刪除的情況。
2）開放地址法：當(dāng)發(fā)生地址沖突時，按照某種方法繼續(xù)探測哈希表中的其他存儲單元，直到找到空位置為止。
3）再哈希法：這種方法同樣是按照按某種方法探測哈希表中的其他存儲單元，直到找到空位置為止。
4）建立公共溢出區(qū)：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

• 熟悉linux的IO模型么？同步異步有何區(qū)別？同步和阻塞一回事么

• 數(shù)據(jù)庫索引是怎么回事？用的啥數(shù)據(jù)結(jié)構(gòu)？

• 操作系統(tǒng)怎么樣，比如調(diào)度算法有沒有了解？（說了解linux，重點講了CFS調(diào)度算法）

• 進(jìn)程間通信方式有哪些？熟悉哪個？

• 軟件開發(fā)會經(jīng)常用到多線程吧？你說說自旋鎖怎么回事？和互斥鎖有啥區(qū)別（睡眠鎖與非睡眠鎖）

• 熟悉哪些算法？說一下經(jīng)典的排序算法？歸并的時間和空間復(fù)雜度

• Hashmap的原理，Hashmap為什么大小是2的冪次

• 介紹一下紅黑樹

• Arraylist的原理

• Arraylist的擴容機制

• 為什么arraylist擴容是1.5倍

• 場景題：設(shè)計判斷論文抄襲的系統(tǒng)

• 堆排序的原理

基本算法
Linux命令的使用
操作系統(tǒng)(著重)
網(wǎng)絡(luò)(著重)
數(shù)據(jù)庫
編譯技術(shù)
分布式

Linux使用

• 查看內(nèi)存信息
  free/vmstat/top/htop

• 查看磁盤信息
  iostat

• 查看CPU信息
  vmstat/top/htop

• 查看網(wǎng)絡(luò)信息
  netstat -i 網(wǎng)卡信息
  netstat -a 連接信息
  lsof -i:PORT 查看端口占用信息

• proc目錄的實現(xiàn)原理
  procfs,內(nèi)部使用sysctl實現(xiàn)
  gdb調(diào)試,線程信息,線程棧

• info stack/bt 調(diào)用棧
  info threads 線程信息
  thread id 切換線程
  watch expr 監(jiān)控指定表達(dá)式
  buffer、cache和total的含義

• IO寫入時存放數(shù)據(jù)的內(nèi)存page buffer
  IO讀取時存放數(shù)據(jù)的內(nèi)存page cache

• 進(jìn)程和線程的區(qū)別
  對于Linux內(nèi)核而言,區(qū)別并不是很大。
  進(jìn)程的隔離級別更加高,可以使用命名空間等,IPC的代價稍大。
  線程間共享進(jìn)程的地址空間,所以數(shù)據(jù)交互更容易,代價也稍小,但是數(shù)據(jù)競爭更加嚴(yán)重,且一旦進(jìn)程crash,所有線程也就不存在了。

• 進(jìn)程切換所做的事情
  保存寄存器現(xiàn)場
  切換棧空間
  處理內(nèi)存頁(最好深入一下)
  線程同步機制

• 互斥鎖、自旋鎖、讀寫鎖、條件變量

• 列舉進(jìn)程通訊的方式
  PIPE、共享內(nèi)存、Socket、文件、MQ等
  其中共享內(nèi)存最快,但是需要額外的工作才能保證數(shù)據(jù)的一致性

• 命名空間及其效果
  UTS、IPC、PID、NS、NET、USER

• cgroup的功能
  限制CPU和內(nèi)存的使用量/使用頻率

• VFS文件系統(tǒng)
  磁盤中數(shù)據(jù)的存放

• IO調(diào)度算法
  為何需要IO調(diào)度?結(jié)合機械硬盤的工作原理,隨機讀寫開銷很大,因此可以通過匯總數(shù)據(jù)的方式實現(xiàn)順序讀寫。
  Anticipatory算法、Deadline算法、CFQ算法以及Noop(No Operation)算法
  NOOP算法是最簡單的IO調(diào)度算法,適合SSD,只需要將IO請求入隊列即可。
  虛擬地址、物理地址及其實現(xiàn)

進(jìn)程中可見的地址是虛擬地址,物理地址對應(yīng)真實的內(nèi)存,虛擬地址通過MMU映射成物理地址,Linux采用的是4級頁表(PGD、PUD、PMD、PTE),最終對應(yīng)到CR3寄存器。
轉(zhuǎn)換的方式為基址+“偏移”,由于頁表保存在內(nèi)存中,CPU訪存代價過大,因此引入TLB緩存,每次映射時優(yōu)先查找TLB。
網(wǎng)絡(luò)
TCP狀態(tài)圖,結(jié)合握手和揮手

注意同時打開和同時關(guān)閉即可,其余結(jié)合TCP狀態(tài)轉(zhuǎn)移圖進(jìn)行理解。
異常狀態(tài)的出現(xiàn)場景以及解決方案

大量SYN_RECV狀態(tài)的連接,大量TIME_WAIT狀態(tài)的連接等。
長連接和短連接

短連接:數(shù)據(jù)請求到達(dá)后即關(guān)閉連接
長鏈接:多次請求復(fù)用一次連接,需要清楚如何保證連接是否存活,如心跳信號等。
TIME_WAIT的等待時間,MSL的意思

MSL(Maximum Segment Lifetime)
TIME_WAIT后并不能保證最終的ACK能夠安全到達(dá)對端,因此需要預(yù)留重傳的時間,即等待2MSL。
可以通過SO_REUSEADDR規(guī)避2MSL的等待。
RTT如何估計

RTT(Round-Trip Time)
開啟SO_REUSEADDR后可能會出現(xiàn)什么問題

可能接收到對端傳回的FIN、RST等,造成莫名其妙的問題。
TCP如何保證其可靠性

重傳機制、流量控制、擁塞控制
IP序號重合對上層的影響

由IP層負(fù)責(zé)在組包時解決,對上層無影響。
內(nèi)核如何解決accept的驚群問題

使用了WQ_FLAG_EXCLUSIVE標(biāo)記,確保只有一個進(jìn)程會被喚醒。
用戶態(tài)如何解決accept的驚群問題

多進(jìn)程搶占自旋鎖即可,使用pthread_spinlock或者共享內(nèi)存+CAS自行實現(xiàn)。
進(jìn)一步討論,如何在這個階段提供負(fù)載均衡。
數(shù)據(jù)庫
悲觀鎖和樂觀鎖

SQL中如何使用鎖

索引的實現(xiàn)方式和作用

加快數(shù)據(jù)檢索的速度,但是寫入時有相應(yīng)的代價,所以適合讀多寫少的場景。
內(nèi)存通常使用B+樹實現(xiàn)。
編譯相關(guān)
解釋器和編譯器

常見的誤區(qū):所謂變異,并非一定要求生成本地代碼,只要從語言A轉(zhuǎn)換到語言B,這個過程就是編譯。
編譯的流程

預(yù)處理-詞法解析-文法解析-語義制導(dǎo)-抽象語法樹(IR的一種)-三地址碼(SSA)-優(yōu)化(控制流圖、數(shù)據(jù)流圖)-匯編
動態(tài)鏈接庫和靜態(tài)鏈接庫的區(qū)別

虛擬機如何重新加載腳本

關(guān)于熱更新的討論

分布式存儲
redis、rockdb、leveldb的存儲布局

SSD和HDD的區(qū)別使用場景

機械結(jié)構(gòu):主控+多FLASH芯片 vs 電機+磁盤+磁車
延遲:SSD的延遲至少比HDD低1個數(shù)量級
壽命:SSD的壽命主要由P/E次數(shù)決定,因此適合多讀少寫的環(huán)境
其實,對于順序讀寫,hdd的開銷也不是那么大,原因自己去計算,另外此處可以結(jié)合IO調(diào)度算法一起考察。
鎖和MVCC的適用場景

視場景而定,如果數(shù)據(jù)競爭少,則優(yōu)先使用MVCC,否則老老實實用鎖。
HDFS的讀寫操作

metadata、membership的管理

etcd或者zookeeper,真的很方便哦~
副本一致性(RSM)

通過最終一致性算法,如Paxos、2PC、3PC、Raft等
主從使用push和pull的優(yōu)缺點

1.進(jìn)程和線程的區(qū)別
2.什么叫線程安全?舉例說明
3.OSI七層模型,包括TCP,IP的一些基本知識
4.數(shù)據(jù)庫的鎖
5.DFS,BFS算法
6.還有一些諸如collection framework的Java基礎(chǔ)
7、http中,get post的區(qū)別

基礎(chǔ)知識：
算法和數(shù)據(jù)結(jié)構(gòu)
數(shù)組、鏈表、二叉樹、隊列、棧的各種操作（性能，場景）
二分查找和各種變種的二分查找
各類排序算法以及復(fù)雜度分析（快排、歸并、堆）
各類算法題（手寫）
理解并可以分析時間和空間復(fù)雜度。
動態(tài)規(guī)劃（筆試回回有。。）、貪心。
紅黑樹、AVL樹、Hash樹、Tire樹、B樹、B 樹。
圖算法（比較少，也就兩個最短路徑算法理解吧）
計算機網(wǎng)絡(luò)
OSI7層模型（TCP4層）
每層的協(xié)議
url到頁面的過程
HTTP
http/https 1.0、1.1、2.0
get/post 以及冪等性
http 協(xié)議頭相關(guān)
網(wǎng)絡(luò)攻擊（CSRF、XSS）
TCP/IP
三次握手、四次揮手
擁塞控制（過程、閾值）
流量控制與滑動窗口
TCP與UDP比較
子網(wǎng)劃分（一般只有筆試有）
DDos攻擊
(B)IO/NIO/AIO
三者原理，各個語言是怎么實現(xiàn)的
Netty
Linux內(nèi)核select poll epoll
數(shù)據(jù)庫（最多的還是mysql，Nosql有redis）
索引（包括分類及優(yōu)化方式，失效條件，底層結(jié)構(gòu)）
sql語法（join，union，子查詢，having，group by）
引擎對比（InnoDB，MyISAM）
數(shù)據(jù)庫的鎖（行鎖，表鎖，頁級鎖，意向鎖，讀鎖，寫鎖，悲觀鎖，樂觀鎖，以及加鎖的select sql方式）
隔離級別，依次解決的問題（臟讀、不可重復(fù)讀、幻讀）
事務(wù)的ACID
B樹、B 樹
優(yōu)化（explain，慢查詢，show profile）
數(shù)據(jù)庫的范式。
分庫分表，主從復(fù)制，讀寫分離。
Nosql相關(guān)（redis和memcached區(qū)別之類的，如果你熟悉redis，redis還有一堆要問的）
操作系統(tǒng)：
進(jìn)程通信IPC（幾種方式），與線程區(qū)別
OS的幾種策略（頁面置換，進(jìn)程調(diào)度等，每個里面有幾種算法）
互斥與死鎖相關(guān)的
linux常用命令（問的時候都會給具體某一個場景）
Linux內(nèi)核相關(guān)（select、poll、epoll）
編程語言（這里只說Java）：
把我之后的面經(jīng)過一遍，Java感覺覆蓋的就差不多了，不過下面還是分個類。
Java基礎(chǔ)（面向?qū)ο蟆⑺膫€特性、重載重寫、static和final等等很多東西）
集合（HashMap、ConcurrentHashMap、各種List，最好結(jié)合源碼看）
并發(fā)和多線程（線程池、SYNC和Lock鎖機制、線程通信、volatile、ThreadLocal、CyclicBarrier、Atom包、CountDownLatch、AQS、CAS原理等等）
JVM（內(nèi)存模型、GC垃圾回收，包括分代，GC算法，收集器、類加載和雙親委派、JVM調(diào)優(yōu)，內(nèi)存泄漏和內(nèi)存溢出）
IO/NIO相關(guān)
反射和代理、異常、Java8相關(guān)、序列化
設(shè)計模式（常用的，jdk中有的）
Web相關(guān)（servlet、cookie/session、Spring<AOP、IOC、MVC、事務(wù)、動態(tài)代理>、Mybatis、Tomcat、Hibernate等）

一個url到頁面全過程（讓我能說多詳細(xì)說多詳細(xì)，最好從OSI七層的每一層去擴展）
http的請求頭格式（這個真的記不太清了，只說了幾個有印象的標(biāo)志位）
getpost區(qū)別，post可不可以用url的方式傳參。
說到了url有最大長度，就問長度有限制是get的原因還是url的原因，為什么長度會有限制，是http數(shù)據(jù)包的頭的字段原因還是內(nèi)容字段的原因，詳細(xì)說明。（在他一步步追問下答了個差不多）
關(guān)于冪等性的詳細(xì)介紹。
冪等性是http層面的問題嗎，還是服務(wù)器要處理和解決的內(nèi)容。（就是看你對冪等性的定性是怎么理解的）
后臺服務(wù)器對于一個請求是如何做負(fù)載均衡的，有哪些策略，會出現(xiàn)什么樣的問題，怎么解決。（說了一致性hash算法，分布式hash的特性,具體的應(yīng)用場景，又非要問我知不知道這個最早在哪個公司使用的...我說這個真不知道。好像是amazon?）
說說http的缺點，無狀態(tài)，明文傳輸。
那https是怎么做的，如何實現(xiàn)的？ca認(rèn)證機構(gòu)。
然后問我https ssl tcp三者關(guān)系，其中哪些用到了對稱加密，哪些用到了非對稱加密，非對稱加密密鑰是如何實現(xiàn)的。（還好我項目中涉及到了一些加密）
關(guān)于加密的私鑰和公鑰各自如何分配（客戶端拿公鑰，服務(wù)器拿私鑰）
那客戶端是如何認(rèn)證服務(wù)器的真實身份，詳細(xì)說明一下過程，包括公鑰如何申請，哪一層加密哪一層解密。
java的優(yōu)先級隊列，如果讓你設(shè)計一個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)優(yōu)先級隊列如何做？
用TreeMap復(fù)雜度太高，有沒有更好的方法。
hash方法，但是隊列不是定長的，如果改變了大小要rehash代價太大，還有什么方法？
用堆實現(xiàn)，那每次get put復(fù)雜度是多少（lgN）
（思想就是并不一定要按優(yōu)先級排隊列的所有對象，復(fù)雜度太高，但每次保證能取最大的就行，剩下的順序不用保證，用堆調(diào)整最為合適）
在線編程題：敲一個字串匹配問題，寫了常規(guī)代碼。問kmp的代碼思想，最后問了下正則中用的改進(jìn)后的BM算法。（還有個比較新奇的Sunday算法，有興趣的同學(xué)也可以看一下）