当年，兔子学姐靠这个面试小抄拿了个22k
本文順序是操作系統（jvm）、網絡、數據庫（mysql/redis），都是當時兔子的學姐準備面試的時候總結的，學生面試基本不會跑出這個范圍，懂行的應該能看出來。
學姐原話：因為我本身的知識是A集合，我覺得一次記不住，需要反復看的，我就寫了下來B集合。這些并不一定是所有，特別簡單的或者特別生僻的A-B都沒寫。
所以按我的理解，那些，特別特別基礎的，不用學姐說，自己也應該會，然后再看這個文章。
目錄
生產消費讀者寫者
進程vs線程
線程生命周期
進程間通信方式
線程間通信方式
進程調度算法
死鎖
頁面置換算法
磁盤調度算法
jvmjvmjvmjvm區域
判斷對象死亡？引用計數 vs 可達性分析
如何回收對象？垃圾收集算法
垃圾收集器
分配回收策略（老年代新生代）
GC調優
JVM常用參數
Cookie session
網絡分層
握手揮手
UDP想可靠
網絡訪問過程
為什么tcp可靠？
UDP可靠
HTTP and HTTPS
HTTP方法及相互區別
狀態碼
http結構
Tcp結構
Socket
redisredisredis數據結構
對象
跳表
HyperLogLog
單線程
持久化
Redis和數據庫雙寫一致性
緩存擊穿雪崩穿透
解決Redis并發競爭Key問題
Redis緩存策略
哨兵
解決會話
sqlsqlsqlsqllsqlslqslqslq數據類型
mysql特點
存儲引擎
增刪改
范式
索引優缺點和使用原則
索引分類
索引區別
事務特性：ACID
并發錯誤
隔離級別
并發控制技術（鎖）
死鎖
分布式事務
SQL語句性能優化
索引的優化
分庫分表
Kafka
Es
生產消費讀者寫者
讀者寫者：
多讀者/多寫者互斥/多讀者互斥
消費者生產者：全互斥
生產者：p(empty),p(mutex),v(mutex),v(full)
消費者：p(full),p(mutex)v(mutex)v(empty)
進程vs線程
進程是資源（CPU、內存等）分配的基本單位，它是程序執行時的一個實例。
線程是程序執行時的最小單位，是CPU調度和分派的基本單位。
線程間共享進程的所有資源，每個線程有自己的堆棧和局部變量。
線程由CPU獨立調度執行，在多CPU環境下就允許多個線程同時運行。
線程生命周期
（五個狀態）：新建、就緒、運行、阻塞、死亡
新建狀態：線程對象已經創建，還沒有在其上調用start()方法
就緒狀態：當線程調用start方法，但調度程序還沒有把它選定為運行線程時線程
運行狀態：線程調度程序從可運行池中選擇一個線程作為當前線程時線程所處的狀態。（是線程進入運行狀態的唯一方式）
阻塞(等待/睡眠)狀態：線程仍舊是活的，但是當前沒有條件運行。當某件事件出現，他可能返回到可運行狀態
死亡狀態：當線程的run()方法完成時就認為它死去。線程一旦死亡，就不能復生。 一個死去的線程上調用start()方法，會拋出java.lang.IllegalThreadStateException異常
進程間通信方式
?
為了正確地實現信號量，信號量值的測試及減1操作應當是原子操作。為此，信號量通常是在內核中實現的。Linux環境中，有三種類型：Posix（可移植性操作系統接口）有名信號量（使用Posix IPC名字標識）、Posix基于內存的信號量（存放在共享內存區中）、System V信號量（在內核中維護）。這三種信號量都可用于進程間或線程間的同步。
?
（套接字位于傳輸層與應用層之間）
套接字是支持TCP/IP網絡通信的基本操作單元，可以看做主機間進程進行雙向通信的端點
?套節字通信基本過程
線程間通信方式
1.鎖機制：包括互斥鎖(對應于JAVA中的Synchronized)、條件變量(對應于JAVA中的volatile)
*互斥鎖提供了以排他方式防止數據結構被并發修改的方法。
*條件變量可以以原子的方式阻塞進程，直到某個特定條件為真為止。對條件的測試是在互斥鎖的保護下進行的。條件變量始終與互斥鎖一起使用。
2.信號機制：包括無名線程信號量和命名線程信號量
JAVA中線程通信的具體方式有：1.Volatile和Synchronized 2.wait()和notify()機制 3.管道輸入/輸出流：PipedReader, PipedWriter 4.Thread.join() 5.TheadLocal類：線程變量,用于線程內部共享數據。以ThreadLocal對象為鍵，任意對象為值的存儲結構 ThreadLocal<String> tl = new ThreadLocal<>();
進程調度算法
先來先服務（FCFS）最簡單調度算法。按照進入后備隊列的先后次序來加入就緒隊列等待執行。是非搶占式，易于實現，效率不高，利于長作業（CPU繁忙）不利于短作業（I/O繁忙）
短作業優先（Short Job First）是非搶占式的，具有很好性能，降低平均等待時間，提高吞吐量。不利于長作業，可能一直處于等待出現饑餓；未考慮作業緊迫程度，不能用于實時系統。
高響應比優先調度算法（Highest Reponse Ratio First, HRRF）（響應比高意味著等待時間長而服務時間短，優先處理）響應比 = （等待 + 服務） / 服務時間 = 等待 / 服務時間 + 1
時間片輪轉：用于分時系統的進程調度，搶占式。
基本思想：將CPU時間分為若干時間片（q），進程按到達順序排列。每次調度隊首，執行1個時間片后，該進程移至隊尾。能在給定時間響應所有用戶請求，達到分時系統的目的。
其性能主要取決于時間片q的大小，q太大，則所有的進程在1個時間片完成；太小則進程頻繁切換，系統開銷大。
多級反饋隊列調度算法：將時間片輪轉與優先級調度相結合，把進程按優先級分成不同的隊列，先按優先級調度，優先級相同的，按時間片輪轉。優點是兼顧長短作業，有較好的響應時間，可行性強，適用于各種作業環境。
死鎖
什么是死鎖？
當兩個以上的運算單元，雙方都在等待對方停止運行，以獲取系統資源，但是沒有一方提前退出時，就稱為死鎖。
必要條件
禁止搶占 - 資源不能被強制從一個進程中退出
持有和等待 - 一個進程可以在等待時持有系統資源
互斥 – 某個資源在一段時間內只能由一個進程占有
循環等待 - 一系列進程互相持有其他進程所需要的資源，銀行家算法-破環循環等待條件，合理分配系統資源
死鎖的應對方法
1. 最簡單、最常用方法是重新啟動，不過代價很大，意味著之前所有進程計算都將付之東流
2. 撤消進程，剝奪資源。終止參與死鎖的進程，收回它們占有的資源，從而解除死鎖。
分兩種情況：一次性剝奪全部資源；或逐步撤消參與死鎖的進程，選擇逐步撤消目的是撤消代價最小的進程，比如按進程優先級確定代價；考慮進程運行代價和此進程相關作業代價等；
3. 進程回退策略，即讓參與死鎖的進程回退到沒有發生死鎖前某一點處。操作起來系統開銷大，要有堆棧這樣的機構記錄進程的每一步變化，以便今后的回退，有時這是無法做到的。
頁面置換算法
最佳置換算法（OPT）
最佳(OPT)置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。但由于人們目前無法預知進程在內存頁面中哪個是未來最長時間內不再被訪問的，因而該算法無法實現。
先進先出置換算法（FIFO）
最簡單的頁面置換算法是先入先出（FIFO）法。這種算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。
最近最久未使用（LRU）算法
它的實質是，當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以置換。
?
?
磁盤調度算法
1.FIFO：先來先服務算法；（依次處理）
2.SSTF： 最短尋道時間算法；（距離當前磁道最近的有限處理）
3.SCAN：電梯調度算法；(這樣命名很形象，先按一個方向，掃描的過程依次訪問要求服務的隊列，當掃描到最里層的一個服務序列時就反向掃描)
4.CSCAN： 循環掃描算法（從最里面一個磁道訪問完之后，立即返回最外層，也稱單向掃描調度算法）
5.FSCAN：分步電梯調度算法(分兩個隊列)
?
jvmjvmjvmjvm區域
線程私有的：程序計數器、（虛擬機棧、本地方法棧）
線程共享的：堆、方法區、直接內存 (非運行時數據區的一部分)
程序計數器是一塊較小的內存空間，是當前線程執行字節碼的行號指示。
工作時通過改變這個計數器的值來選取下一條需要執行的字節碼指令，分支、循環、跳轉、異常處理、線程恢復等功能都需要依賴這個計數器來完成。為了線程切換后能恢復到正確的執行位置，每條線程都需要有一個獨立的程序計數器。
作用：
通過改變程序計數器來依次讀取指令實現流程控制，如：順序執行、選擇、循環、異常處理。
多線程：記錄當前線程執行的位置，線程被切換回來時能夠知道該線程上次運行到哪兒了。
虛擬機棧（Java 內存可以粗糙的區分為堆內存（Heap）和棧內存 (Stack)）
存放基本數據類型（boolean、byte、char、short、int、float、long、double）和對象引用
會出現兩種異常：StackOverFlowError 和 OutOfMemoryError。
StackOverFlowError：不動態拓展，?線程請求棧的深度超過當前虛擬機棧的最大深度
OutOfMemoryError：?動態擴展，且內存用完了，無法擴展
堆：唯一目的就是存放對象實例，幾乎所有實例和數組都在這里。
方法區（永久代）：存儲已加載的類信息、常量、靜態變量、即時編譯器編譯后的代碼等。
《Java 虛擬機規范》規定了有方法區和作用，并沒實現。（像接口），在不同的 JVM 上方法區的實現肯定是不同的了。?永久代是 HotSpot 虛擬機對方法區的一種實現方式。（像類）
判斷對象死亡？引用計數 vs 可達性分析
引用計數算法：給對象添加一個引用計數器，每當有一個地方引用到他，就加1；引用失效就減1。有問題，有可能存在循環引用，導致對象無法被回收。
可達性分析算法：以GC Roots對象為起始點，從這些節點向下搜索
可以作為GC ROOT對象的有：Java虛擬機棧中的引用對象。本地方法棧中JNI（既一般說的Native方法）引用的對象。方法區中類靜態屬性所引用的對象。方法區中常量所引用的對象。
如何回收對象？垃圾收集算法
標記清除算法：分為標記和清除兩個階段。
首先從根集合進行掃描，對存活的對象進行標記，標記完畢后，再掃描整個空間中未被標記的對象并進行回收（老年代）
主要不足有兩個：效率問題：標記和清除兩個過程的效率都不高;
空間問題：不進行對象的移動，并且僅對不存活的對象進行處理，因此標記清除之后會產生大量不連續的內存碎片，可能會導致以后在程序運行過程中需要分配較大對象時，無法找到足夠的連續內存而不得不提前觸發另一次垃圾收集動作。
復制算法將可用內存按容量劃分為大小相等的兩塊，每次只使用其中的一塊。當這一塊的內存用完了，就將還存活著的對象復制到另外一塊上面，然后再把已使用過的內存空間一次清理掉。這種算法適用于對象存活率低的場景，比如新生代。
標記整理算法的標記過程類似標記清除算法，但后續步驟不是直接對可回收對象進行清理，而是讓所有存活的對象都向一端移動，然后直接清理掉端邊界以外的內存，類似于磁盤整理的過程，該垃圾回收算法適用于對象存活率高的場景（老年代）
垃圾收集器
Serial收集器（復制算法): 新生代單線程收集器，標記和清理都是單線程，優點是簡單高效；
Serial Old收集器 (標記-整理算法): 老年代單線程收集器，Serial收集器的老年代版本；
ParNew收集器 (復制算法): 新生代并行收集器，實際上是Serial收集器的多線程版本，在多核CPU環境下有著比Serial更好的表現；
Parallel Old收集器 (標記-整理算法)： 老年代并行收集器，吞吐量優先，Parallel Scavenge收集器的老年代版本；
CMS(Concurrent Mark Sweep)收集器（標記-清除算法）： 老年代并行收集器，以獲取最短回收停頓時間為目標的收集器，具有高并發、低停頓的特點，追求最短GC回收停頓時間。
收集過程分為：初始標記，并發標記，重新標記，垃圾回收
G1(Garbage First)收集器 (標記-整理算法)： Java堆并行收集器，G1收集器是JDK1.7提供的一個新收集器，G1收集器基于“標記-整理”算法實現，也就是說不會產生內存碎片。此外，G1收集器不同于之前的收集器的一個重要特點是：G1回收的范圍是整個Java堆(包括新生代，老年代)，而前六種收集器回收的范圍僅限于新生代或老年代。
?
分配回收策略（老年代新生代）
自動內存管理可以歸結為自動化地解決兩個問題：
分配內存、回收內存。
一般而言，對象主要分配在新生代的Eden區上，少數情況下也可能直接分配在老年代中。
1)??? 對象優先在Eden分配，當Eden區沒有足夠空間時，虛擬機將發起一次MinorGC。
2)??? 大對象直接進入老年代。所謂的大對象是指，很長的字符串以及數組。
3)??? 長期存活對象進入老年代。在新生代中經歷n次（默認15）Minor GC后，晉升老年代。
4)??? 動態對象年齡判定。為了更好地適應不同程序的內存狀況，虛擬機并不是永遠地要求對象年齡必須達到了MaxTenuringThreshold才能晉升老年代，如果在Survivor空間中相同年齡所有對象大小的總和大于Survivor空間的一半，年齡大于或等于該年齡的對象就可以直接進入老年代，無須等到MaxTenuringThreshold中要求的年齡。
?
GC調優
各分區的大小對GC的性能影響很大。
如何將各分區調整到合適的大小，分析活躍數據的大小是很好的切入點。
活躍數據的大小是指，應用程序穩定運行時長期存活對象在堆中占用的空間大小，也就是Full GC后堆中老年代占用空間的大小。可以通過GC日志中Full GC之后老年代數據大小得出，比較準確的方法是在程序穩定后，多次獲取GC數據，通過取平均值的方式計算活躍數據的大小
通過收集GC信息，結合系統需求，確定優化方案，例如選用合適的GC回收器、重新設置內存比例、調整JVM參數等。
根據對象生命周期的分布情況：如果應用存在大量的短期對象，應該選擇較大的年輕代；如果存在相對較多的持久對象，老年代應該適當增大。
?
JVM常用參數
-Xms: 初始堆大小
-Xmx：最大堆大小
-XX:NewSize=n:設置年輕代大小
-XX:NewRatio=n:設置年輕代和年老代的比值。如：為3表示年輕代和年老代比值為1：3
-XX:SurvivorRatio=n:年輕代中Eden區與兩個Survivor區的比值。注意Survivor區有兩個。如3表示Eden：3 Survivor：2（3：1：1），一個Survivor區占整個年輕代的1/5
-XX:MaxPermSize=n:設置永久代大小
?
Cookie session
Cookie與Session都是用來跟蹤瀏覽器用戶身份的會話方式。
Cookie放客戶瀏覽器，Session放服務器。
Cookie不安全，別人可以分析本地Cookie進行Cookie欺騙,用加密的Cookie或Session。
Session存服務器。占服務器性能，如果減輕負擔方面，用Cookie。
單個Cookie在客戶端的限制是4K，很多瀏覽器都限制一個站點最多保存20個Cookie。
網絡分層
物理層：在傳輸媒體上傳輸數據比特流。屏蔽介質和通信手段差異，使數據鏈路層感覺不到
數據鏈路層：主機間有很多鏈路，為相鄰結點間服務。把網絡層傳來的分組封裝成幀。
網絡層：為主機間提供傳輸服務，把運輸層傳遞下來的報文段或數據報封裝成分組。
運輸層：進程間的通用數據傳輸服務。
???????? 傳輸控制協議 TCP，提供面向連接、可靠的數據傳輸服務，數據單位為報文段；
???????? 用戶數據報協議 UDP，提供無連接數據傳輸服務，數據單位為用戶數據報。
???????? TCP 主要提供完整性服務，UDP 主要提供及時性服務。
應用層：為特定應用程序提供數據傳輸服務，例如 HTTP、DNS 等。數據單位為報文。
握手揮手
序號seq ：對字節流編號，序號為 301，編號為 301，如攜帶數據 100 字節，下一個報文段的序號應為 401。用來標記順序
確認號 ack：期望收到的下一個報文段序號。例如 B 收到 A報文段序號為 501，長度 200 ，因此 B 期望701，B 發送給 A 的確認報文段中確認號就為 701。
確認 ACK ：當 ACK=1 時確認號ack字段有效，否則無效。
同步 SYN ：在連接建立時用來同步序號。當 SYN=1，ACK=0 時表示這是一個連接請求報文段。若對方同意建立連接，則響應報文中 SYN=1，ACK=1。
終止 FIN ：用來釋放一個連接，當 FIN=1 時，表示發送方已發送完畢，要求釋放連接。
窗口 ：窗口值作為接收方讓發送方設置其發送窗口的依據。這個限制是因為接收方的數據緩存空間有限
?
1、第一次握手：客戶端給服務器發送一個 SYN 報文。
2、第二次握手：服務器收到 SYN 報文之后，會應答一個 SYN+ACK 報文。
3、第三次握手：客戶端收到 SYN+ACK 報文之后，會回應一個 ACK 報文。
4、服務器收到 ACK 報文之后，三次握手建立完成。
第一次：seq隨機x,ACK=0,syn=1,ack=0,
第二次：seq隨機y,ACK=X+1,syn=1,ack=1
第三次：seq=x+1,ACK=Y+1,syn=0,ack=1
第一次握手：客戶端發，服務端收到。服務端就能得出結論：客戶端的發送能力、服務端接收能力是正常
第二次握手：服務端發，客戶端收到。客戶端就能得出結論：服務端的接收發送能力，客戶端的接收發送能力是正常的。服務器不能確認客戶端的接收能力是否正常。
第三次握手：客戶端發，服務端收到了。這樣服務端就能得出結論：客戶端的接收發送能力正常，服務器自己的發送、接收能力也正常。
第三次握手是為了防止失效的連接請求到達服務器，讓服務器錯誤打開連接。
客戶端等待一個超時重傳時間之后，就會重新請求連接。但是這個滯留的連接請求最后還是會到達服務器，如果不進行三次握手，那么服務器就會打開兩個連接。
為什么三次四次？
三次：Server在收到建立連接請求后，可以直接把ACK和SYN放在一個報文發送給Client。
四次：關閉連接時，當收到對方的FIN報文時，僅僅表示對方不再發送數據了但是還能接收數據，己方也未必全部數據都發送給對方了，因此，己方ACK和FIN一般都會分開發送。
?
四次揮手：
客戶機：我想和你斷開連接，你同意嗎？（FIN=1） ????????????服務器：我同意（ACK=1）
（期間服務器可能還會向客戶機發送數據，但是反之不可以）
服務器：客戶機，我想要和你斷開連接，你同意嗎？（FIN=1） 客戶機：我同意。（ACK=1）
?
短連接表示“業務處理+傳輸數據的時間 遠遠小于 TIMEWAIT超時的時間”的連接。
?
UDP想可靠
就要接收方收到UDP之后回復個確認包，發送方有個機制，收不到確認包就要重新發送，每個包有遞增的序號，接收方發現中間丟了包就要發重傳請求，當網絡太差時候頻繁丟包，防止越丟包越重傳的惡性循環，要有個發送窗口的限制，發送窗口的大小根據網絡傳輸情況調整，調整算法要有一定自適應性。
網絡訪問過程
域名解析
--> 發起TCP的3次握手 拿到域名對應的IP地址之后，瀏覽器向服務器的WEB程序（tomcat,nginx）80端口發起TCP連接請求。
--> 建立TCP連接后發http請求
--> 服務器響應http請求，瀏覽器得到html代碼
--> 瀏覽器解析html代碼，并請求html代碼中的資源（如js、css、圖片）
--> 瀏覽器對頁面渲染呈現
?
域名解析：搜索瀏覽器的DNS緩存 操作系統的DNS緩存? hosts文件C:\Windows 迭代DNS解析請求（根名稱/頂級名稱/二級名稱/權威名稱服務器）
?
為什么tcp可靠？
流量控制（滑動窗口）
發送方通過維持一個發送窗口確保不會發生發送方發太快接收方無法及時處理。
TCP如何保證可靠傳輸？
1、確認和重傳：接收方收到報文就會確認，發送方發送一段時間后沒有收到確認就重傳。
2、數據校驗
1）ack：數據丟失或延遲。發送時會起定時器，如果指定時間內沒接收到ACK seq + 1，就再發一次。
2）數據亂序：接收方上一個收到的正確數據是seq + 4，它返回seq + 5作為ACK。這時候它收到了seq + 7，因為順序錯了，所以接收方會再次返回seq + 5給發送方。
3）數據錯誤：每一個TCP數據都會帶著數據的校驗和。接收方收到數據seq + 3以后會先對校驗和進行驗證。如果結果不對，則發送ACK seq + 3，讓發送方重新發送數據。
4）數據重復：接收方直接丟棄重復數據。
3、流量控制：當接收方來不及處理發送方的數據，能提示發送方降低發送的速率，防止包丟失。
4、擁塞控制：當網絡擁塞時，減少數據的發送。
流量控制與滑動窗口
流量控制是為了控制發送方發送速率，保證接收方來得及接收。
接收方發送的確認報文中的窗口字段可以用來控制發送方窗口大小，從而影響發送方的發送速率。將窗口字段設置為0，則發送方不能發送數據。
發送方和接收方各有一個窗口，接收方通過窗口字段告訴發送方自己的窗口大小，發送方根據這個值和其它信息設置自己的窗口大小。
TCP使用累計確認（發送方一次發送多個連續包，接收方只需要確認最后一個包），快速重傳（收到3個冗余的ACK包立馬重傳，不用等待超時）以及選擇重傳(只對丟失的包進行重傳)提高效率
TCP的擁塞控制與擁塞窗口
擁塞控制：防止過多的數據注入到網絡中，這樣可以使網絡中的路由器或鏈路不致過載。
發送方維持一個擁塞窗口 cwnd的狀態變量。動態地在變化。發送方讓自己的發送窗口等于擁塞。
原則：沒擁塞，窗口就增大一些，以便把更多的分組發送出去。
出現擁塞，擁塞窗口就減小一些，以減少注入到網絡中的分組數。
幾種擁塞控制方法：慢開始、擁塞避免、快重傳和快恢復。
慢開始：不清楚網絡的負荷情況。因此先探測一下，由小到大逐漸增大發送窗口，也就是說，由小到大逐漸增大擁塞窗口數值。
通常在剛剛開始發送報文段時，先把擁塞窗口 cwnd 設置為一個最大報文段MSS的數值。而在每收到一個對新的報文段的確認后，把擁塞窗口增加至多一個MSS的數值。用這樣的方法逐步增大發送方的擁塞窗口 cwnd ，可以使分組注入到網絡的速率更加合理。
慢開始門限ssthresh的用法如下：
?? ?? 當 cwnd < ssthresh 時，使用慢開始算法
當 cwnd > ssthresh 時，改用擁塞避免算法。
??? 當 cwnd = ssthresh 時，都可以
擁塞避免算法：經過一個往返時間RTT就把擁塞窗口cwnd加1，不是加倍。按線性規律緩慢增長，比慢開始算法的擁塞窗口增長速率緩慢得多。
只要發送方判斷網絡出現擁塞（其根據就是沒有收到確認），就要把門限ssthresh設置為出現擁塞時的發送方窗口值的一半（但不能小于2）。然后把擁塞窗口cwnd重新設置為1，執行慢開始算法。目的就是要迅速減少主機發送到網絡中的分組數，使得發生擁塞的路由器有足夠時間把隊列中積壓的分組處理完畢。
快速恢復算法：發送方認為網絡很可能沒有發生擁塞，因此而是把cwnd值設置為門限減半后的數值，然后使擁塞窗口線性增大。
UDP可靠
最簡單的方式是在應用層模仿傳輸層TCP的可靠性傳輸。下面不考慮擁塞處理，可靠UDP的簡單設計。
?
1、添加seq/ack機制，確保數據發送到對端
2、添加發送和接收緩沖區，主要是用戶超時重傳。
3、添加超時重傳機制。
詳細說明：送端發送數據時，生成一個隨機seq=x，然后每一片按照數據大小分配seq。數據到達接收端后接收端放入緩存，并發送一個ack=x的包，表示對方已經收到了數據。發送端收到了ack包后，刪除緩沖區對應的數據。時間到后，定時任務檢查是否需要重傳數據。
?
目前有如下開源程序利用udp實現了可靠的數據傳輸。分別為RUDP、RTP、UDT。
HTTP and HTTPS
通信使用明文，內容可能被竊聽(重要密碼泄露)
不驗證通信方身份，有可能遭遇偽裝(跨站點請求偽造)
無法證明報文的完整性，有可能已遭篡改(運營商劫持)
http+加密+認證+完整性保護=https
1、https協議需要到ca申請證書，一般免費證書較少，因而需要一定費用。
2、https則是通過TLS加密后傳輸。SSL 是“Secure Sockets Layer”的縮寫，中文叫做“安全套接層”
3、http和https使用的是完全不同的連接方式，用的端口也不一樣，前者是80，后者是443。
對稱密鑰加密，又稱私鑰加密，即發送方和接收方用同一個密鑰去加密解密。優勢是速度快，適合于對大數據量進行加密，但密鑰管理困難。
非對稱密鑰加密，又稱公鑰加密，需要使用一對密鑰分別完成加密和解密，一個公開發布，即公開密鑰，另一個由用戶自己保存，即私用密鑰。信息發送者用公開密鑰去加密，而信息接收者則用私用密鑰去解密。
從功能角度而言非對稱加密比對稱加密功能強大，但加密和解密速度卻比對稱密鑰加密慢得多。
SSL/TLS協議，公鑰加密法，客戶端先向服務器端索要公鑰，然后用公鑰加密信息，服務器收到密文后，用自己的私鑰解密，如何保證公鑰不被篡改？
解決方法：將公鑰放在數字證書中，只要證書是可信的，公鑰就是可信的。
HTTP方法及相互區別
GET 用于獲取，而 POST 用于傳輸實體主體。
GET 和 POST 的請求都能使用額外的參數，但是 GET 的參數是以查詢字符串出現在 URL 中，而 POST 的參數存儲在實體主體中。不能因為 POST 參數存儲在實體主體中就認為它的安全性更高，因為照樣可以通過一些抓包工具（Fiddler）查看
因為 URL 只支持 ASCII 碼，因此 GET 的參數中如果存在中文等字符就需要先進行編碼。例如中文會轉換為%E4%B8%AD%E6%96%87 ,而空格會轉換為%20。POST參數支持標準字符集。
GET請求在URL中傳送的參數是有長度限制的，而POST么有
HEAD獲取報文首部，和 GET 方法類似，但是不返回報文實體主體部分
狀態碼
1正常2成功3重定向4客戶端錯誤5服務端錯誤
100 Continue ：表明到目前為止都很正常，客戶端可以繼續發送請求或者忽略這個響應。
200 OK
204 No Content ：請求已經成功處理，但是返回的響應報文不包含實體的主體部分。一般在只需要從客戶端往服務器發送信息，而不需要返回數據時使用。
206 Partial Content ：表示客戶端進行了范圍請求，響應報文包含由 Content-Range 指定范圍的實體內容。
301 Moved Permanently ：永久性重定向
302 Found ：臨時性重定向
303 See Other ：和 302 有著相同的功能，但是 303 明確要求客戶端應該采用 GET 方法獲取資源。
304 Not Modified ：表示資源在由請求頭中的If-Modified-Since或If-None-Match參數指定的這一版本之后，未曾被修改。在這種情況下，由于客戶端仍然具有以前下載的副本，因此不需要重新傳輸資源。
307 Temporary Redirect ：臨時重定向，與302相反，當重新發出原始請求時，不允許更改請求方法。
400 Bad Request ：請求報文中存在語法錯誤
401 Unauthorized ：該狀態碼表示發送的請求需要有認證信息。如果之前已進行過一次請求，則表示用戶認證失敗
403 Forbidden ：請求被拒絕
404 Not Found ：請求失敗，請求所希望得到的資源未被在服務器上發現，但允許用戶的后續請求。
500 Internal Server Error ：服務器正在執行請求時發生錯誤
503 Service Unavailable ：服務器暫時處于超負載或正在進行停機維護，現在無法處理請求。
504 Gateway Timeout作為網關或者代理工作的服務器嘗試執行請求時，未能及時從上游服務器
?
http結構
一個HTTP請求報文由四個部分組成：請求行、請求頭部、空行、請求數據。
1.請求行：由請求方法字段、URL字段和HTTP協議版本字段3個字段組成，它們用空格分隔。比如 GET /data/info.html HTTP/1.1
方法字段就是HTTP使用的請求方法，比如常見的GET/POST
其中HTTP協議版本有兩種：HTTP1.0/HTTP1.1 可以這樣區別：
HTTP1.0對于每個連接都只能傳送一個請求和響應，請求就會關閉，HTTP1.0沒有Host字段;而HTTP1.1在同一個連接中可以傳送多個請求和響應，多個請求可以重疊和同時進行，HTTP1.1必須有Host字段。
2.請求頭部
指明請求類型(一般是GET或者 POST)。大多數請求頭并不是必需的，但post的Content-Length除外。
Accept： 瀏覽器可接受的MIME類型。
Accept-Charset：瀏覽器可接受的字符集。
Accept-Encoding：瀏覽器能夠進行解碼的數據編碼方式，比如gzip。
Accept-Language：瀏覽器所希望的語言種類
Authorization：授權信息，通常出現在對服務器發送的WWW-Authenticate頭的應答中。
Content-Length：表示請求消息正文的長度。
Host： 客戶機通過這個頭告訴服務器，想訪問的主機名。Host頭域指定請求資源的Intenet主機和端口號，必須表示請求url的原始服務器或網關的位置。HTTP/1.1請求必須包含主機頭域，否則系統會以400狀態碼返回。
Referer：客戶機通過這個頭告訴服務器，它是從哪個資源來訪問服務器的(防盜鏈)。包含一個URL，用戶從該URL代表的頁面出發訪問當前請求的頁面。
User-Agent：User-Agent頭域的內容包含發出請求的用戶信息。瀏覽器類型，如果Servlet返回的內容與瀏覽器類型有關則該值非常有用。
Cookie：客戶機通過這個頭可以向服務器帶數據，這是最重要的請求頭信息之一。
From：請求發送者的email地址，由一些特殊的Web客戶程序使用，瀏覽器不會用到它。
Connection：處理完這次請求后是否斷開連接還是繼續保持連接。
同時指定幾個范圍：bytes=500-600,601-999
3.空行
它的作用是通過一個空行，告訴服務器請求頭部到此為止。
4.請求數據
若方法字段是GET，則此項為空，沒有數據
若方法字段是POST,則通常來說此處放置的就是要提交的數據
?
HTTP響應報文由三部分組成：響應行、響應頭、響應體
1.響應行
響應行一般由協議版本、狀態碼及其描述組成 比如 HTTP/1.1 200 OK
其中協議版本HTTP/1.1或者HTTP/1.0，200就是它的狀態碼，OK則為它的描述。
//常見狀態碼：
100~199：表示成功接收請求，要求客戶端繼續提交下一次請求才能完成整個處理過程。
200~299：表示成功接收請求并已完成整個處理過程。常用200
300~399：為完成請求，客戶需進一步細化請求。例如：請求的資源已經移動一個新地址、常用302(意味著你請求我，我讓你去找別人),307和304(我不給你這個資源，自己拿緩存)
400~499：客戶端的請求有錯誤，常用404(意味著你請求的資源在web服務器中沒有)403(服務器拒絕訪問，權限不夠)
500~599：服務器端出現錯誤，常用500
2.響應頭
響應頭用于描述服務器的基本信息，以及數據的描述，服務器通過這些數據的描述信息，可以通知客戶端如何處理等一會兒它回送的數據。
設置Cookie，指定修改日期，指示瀏覽器按照指定的間隔刷新頁面，聲明文檔的長度以便利用持久HTTP連接，……等等許多其他任務。
?
常見的響應頭字段含義：
Allow：服務器支持哪些請求方法(如GET、POST等)。
Content-Encoding：文檔的編碼(Encode)方法。只有在解碼之后才可以得到Content-Type頭指定的內容類型。利用gzip壓縮文檔能夠顯著地減少HTML文檔的下載時間。
Content-Length：表示內容長度。只有當瀏覽器使用持久HTTP連接時才需要這個數據。
Content- Type：表示后面的文檔屬于什么MIME類型。Servlet默認為text/plain，但通常需要顯式地指定為text/html。由于經常要設置 Content-Type，因此HttpServletResponse提供了一個專用的方法setContentType。
?
Date：當前的GMT時間，例如，Date:Mon,31Dec200104:25:57GMT。Date描述的時間表示世界標準時，換算成本地時間，需要知道用戶所在的時區。你可以用setDateHeader來設置這個頭以避免轉換時間格式的麻煩。
Location：這個頭配合302狀態碼使用，用于重定向接收者到一個新URI地址。表示客戶應當到哪里去提取文檔。Location通常不是直接設置的，而是通過HttpServletResponse的sendRedirect方法，該方法同時設置狀態代碼為302。
Refresh：告訴瀏覽器隔多久刷新一次，以秒計。
?
Set-Cookie：設置和頁面關聯的Cookie。Servlet不應使用response.setHeader(“Set-Cookie”, …)，而是應使用HttpServletResponse提供的專用方法addCookie。
?
Transfer-Encoding：告訴瀏覽器數據的傳送格式。
?
?
注：設置應答頭最常用是HttpServletResponse的setHeader，方法有兩個參數：應答頭的名字和值。和設置狀態代碼相似，設置應答頭應該在發送任何文檔內容之前進行。
setDateHeader方法和setIntHeadr方法專門用來設置包含日期和整數值的應答頭，前者避免了把Java時間轉換為GMT時間字符串的麻煩，后者則避免了把整數轉換為字符串的麻煩。
HttpServletResponse設置
setContentType：設置Content-Type頭。大多數Servlet都要用到這個方法。
addCookie：設置一個Cookie(Servlet API中沒有setCookie方法，因為應答往往包含多個Set-Cookie頭)。
3.響應體
響應體就是響應的消息體，如果是純數據就是返回純數據，如果請求的是HTML頁面，那么返回的就是HTML代碼，如果是JS就是JS代碼，如此之類。
?
Tcp結構
六位標志位包含以下幾項：
URG：表示緊急指針是否有效；
ACK：表示確認號是否有效，攜帶ACK標志的數據報文段為確認報文段；
PSH：提示接收端的應用程序應該立即從TCP接受緩沖區中讀走數據，為接受后續數據騰出空間；
RST：表示要求對方重新建立連接，攜帶RST標志位的TCP報文段成為復位報文段；
SYN：表示請求建立一個連接，攜帶SYN標志的TCP報文段為同步報文段；
FIN：通知對方本端要關閉了，帶FIN標志的TCP報文段為結束報文段。
確認序號：
Ack序號，占32位，只有ACK標志位為1時，確認序號字段才有效，Ack=Seq+1。
TCP頭部選項：
TCP頭部選項是一個可變長的信息，這部分最多包含40字節，因為TCP頭部最長60字節，（其中還包含前面20字節的固定部分）。
為什么在TCP首部的開始便是首部長度字段而UDP首部卻沒有？
因為UDP提供無連接服務，它的數據包包頭，是固定長度的8字節，不存在可選字段，可以減少很多傳輸開銷，所以它無需使用首部字段長，因為它的首部就是固定的。
而TCP提供連接服務，它的數據包包頭，除了固定的20字節之外，還存在一個可選項，這個可選項字段，是根據TCP連接的要求而變動。這一字段最常見到的就是最大報文大小MSS，它指明發送端所能接收的最大長度的報文段。因為這個字段的存在，所以TCP包頭使用了首部長字段。它占4位，以四字節為單位表示TCP包頭長度，也就是說，TCP的首部最大長度可以是15x4=60字節，而可選項長可以為60-20=40字節
Socket
ServerSocket serverSocket = new ServerSocket(12016);//監聽do {Socket socket = serverSocket.accept();//獲取IO流InputStream is = socket.getInputStream();OutputStream os = socket.getOutputStream();byte[] cache = new byte[1024];is.read(cache);//讀cmd = new String(cache);os.write(returnText.getBytes());//寫os.flush();is.close();os.close();} while (!returnText.equals("end"));redisredisredis數據結構
字符串
相對于c的改進：
獲取長度：c遍歷字符串，redis直接讀len
緩沖區安全：c字符串容易緩沖區溢出，比如：沒有分配足夠空間就執行拼接操作。
redis會先檢查空間是否滿足要求，如果不滿足會自動擴充。
內存分配：c長度變化總是內存重新分配。
redis：1、預分配：如修改后大于1MB，分配? 1MBfree空間。修改長度時檢查，夠的話就用free空間2、惰性空間釋放：縮短時不需要釋放空間，用free記錄即可，留作以后使用。
二進制安全
c字符串程序讀到空字符會誤以為是結尾，所以 c字符串不能保存二進制文件。
而redis字符串二進制安全，因為有len記錄長度。
鏈表：雙端、無環、帶長度記錄、多態：用 void* 指針來保存節點值。
字典：數組、大小、掩碼（等于size-1），已有節點數量
整數集合：數組、數量、編碼方式
升級：計算新空間、轉換并放入原來的數、放入新數
降級：無
壓縮列表
連鎖更新：在一個壓縮列表中有多個連續的、長度介于?250?字節到?253?字節之間的節點 ，這時， 如果我們將一個長度大于等于?254?字節的新節點?new?設置為壓縮列表的表頭節點
對象
對象組成：// 類型// 編碼// 指向底層實現數據結構的指針
不為對象關聯固定編碼，提升靈活性和效率，可以根據使用場景為對象設置不同編碼。
字符串對象：long、字符串、embstr
列表對象：所有字符串元素長度小于 64 字節；元素數量小于 512 個：ziplist否則鏈表
哈希對象：所有鍵值對的字符串長度都小于 64 字節；數量小于 512 ：ziplist 否則hashtable
集合對象：所有元素都是整數值；數量不超過 512 個：intset，否則hashtable
有序集合：所有元素的長度都小于 64 字節；元素數量小于 128 個；ziplist否則跳表
場景：
string：常規計數：微博數，粉絲數等。
hash 特別適合用于存儲對象，如用戶，商品
list查找遍歷等，可以lrange命令實現不斷下拉分頁
set去重，點贊關注
sortedset 有序，做實時排行榜，禮物榜彈幕榜。
跳表
比較
哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。
做范圍查找，平衡樹比skiplist操作要復雜。
在平衡樹上，我們找到指定范圍的小值之后，需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。
平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。
從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。
從算法實現難度上來比較，skiplist比平衡樹要簡單得多。
Redis中的skiplist和經典有何不同
skiplist的key允許重復。這在最開始介紹的經典skiplist中是不允許的。
在比較時，不僅比較key，還比較數據本身。在Redis的skiplist實現中，數據本身的內容唯一標識這份數據，而不是由key來唯一標識。另外，當多個元素分數相同的時候，還需要根據數據內容來進字典排序。
第1層鏈表不是一個單向鏈表，而是一個雙向鏈表。這是為了方便以倒序方式獲取一個范圍內的元素。
在skiplist中可以很方便地計算出每個元素的排名(rank)。
作者原話
有幾個原因：
1）它們的記憶力不是很強。基本上由你決定。更改有關節點具有給定數量級別的概率的參數將使內存密集度低于btree。
2）排序集通常是許多Zrange或Zrevrange操作的目標，即作為鏈表遍歷跳過列表。通過此操作，跳過列表的緩存區域性至少與其他類型的平衡樹一樣好。
3）它們易于實現、調試等。例如，由于跳過列表的簡單性，我收到了一個補丁（已經在redis master中），其中包含在o（log（n））中實現zrank的擴展跳過列表。它只需要對代碼稍作修改。
HyperLogLog
是一種概率數據結構，用來估算數據的基數。數據集可以是訪客 IP 地址，E-mail 或用戶 ID。
基數就是指一個集合中不同值的數目set
使用 Redis 統計集合的基數有三種方法：用 Redis 的 HashMap，BitMap 和 HyperLogLog。前兩個在集合的數量級增長時，所消耗的內存會大大增加，但是 HyperLogLog 不會。
HyperLogLog 通過犧牲準確率來減少內存空間的消耗，只需要12K內存，在標準誤差0.81%的前提下，能夠統計2^64個數據。所以 HyperLogLog 是否適合在比如統計日活月活此類的對精度要不不高的場景。
這是一個很驚人的結果，以如此小的內存來記錄如此大數量級的數據基數。
命令
> PFADD visitors a b c//插入
(integer) 1//數量變化返回1
> PFCOUNT visitors//獲取數量
(integer) 3
> PFADD customers alice dan->(integer) 1
> PFMERGE a b d//合并
OK
> PFCOUNT everyone->(integer) 4
通過Hash函數，將元素轉為64位比特串，0 代表反面，1 代表正面，從左往右第1個1
HyperLogLog： 一共分了 2^14=16384 個桶，。每個桶中是一個 6 bit 的數組。將上文所說的 64 位比特串的低 14 位單獨拿出，值對應桶號，然后將第一次出現 1 的位置值設置到桶中。50位中出現1的位置值最大為50，所以每個桶中的 6 位數組正好可以表示該值。
HyperLogLog 對象中的?registers?數組就是桶，它有兩種存儲結構，分別為密集存儲結構和稀疏存儲結構，從中我們可以看到 Redis 對節省內存極致地追求。
真使用足夠多的?uint8_t?字節去表示，只是此時會涉及到字節位置和桶的轉換，因為字節有 8 位，而桶只需要 6 位。所以我們需要將桶的序號轉換成對應的字節偏移量 offsetbytes 和其內部的位數偏移量 offsetbits。
當 offset_bits 小于等于2時，說明一個桶就在該字節內，只需要進行倒轉就能得到桶的值。
?offset_bits 大于 2 ，則說明一個桶分布在兩個字節內，此時需要將兩個字節的內容都進行倒置，然后再進行拼接得到桶的值。
Redis 為了方便表達稀疏存儲，
單線程
1、完全基于內存
2、數據結構簡單， Redis中的數據結構是專門進行設計的；
3、采用單線程，避免了不必要的上下文切換和競爭條件，也不存在多進程或者多線程導致的切換而消耗 CPU，不用考慮鎖的問題，沒有因為可能出現死鎖。
4、使用多路I/O復用模型，非阻塞IO；
多路I/O復用模型是利用 select、poll、epoll 可以同時監察多個流的 I/O 事件的能力，空閑時，當前線程阻塞，當有流有 I/O 事件時，就喚醒，于是程序就會輪詢一遍所有的流（epoll 只輪詢那些發出了事件的流），并且只依次順序的處理就緒的流，避免了大量無用操作。
持久化
RDB持久化-獲得內存里的數據在某個時間點上的副本。 (這稱為“半持久化模式”，RDB，redis默認持久化方式)；實際操作過程是fork一個子進程，先將數據集寫入臨時文件，寫入成功后，再替換之前文件，用二進制壓縮存儲。
優勢：1，數據庫將只包含一個文件，這對于文件備份來說非常完美；
2， 恢復容易。我們可以輕松的將一個文件壓縮后轉移到其它存儲介質上；
3， 性能最大化；對于服務進程而言，開始持久化時，它唯一需要做的只是fork出子進程，之后再由子進程完成這些持久化的工作，這樣就可以極大的避免服務進程執行IO操作了。
劣勢：
1， 存在數據丟失的可能。此前沒有來得及寫入磁盤的數據都將丟失。
2， 由于RDB是通過fork子進程來協助完成數據持久化工作的，因此，當數據集較大時，可能會導致整個服務器停止服務幾百毫秒，甚至是1秒鐘。
?
AOF持久化-把每一次數據變化都寫入到一個AOF文件中(“全持久化模式”)
優點：
1， 該機制可以帶來更高的數據安全性。AOF有3種同步策略，即每秒同步、每修改同步和不同步。
缺點：平時運行效率低；AOF文件通常大于RDB文件；恢復速度慢。
?
Redis和數據庫雙寫一致性
讀的時候，先讀緩存，緩存沒有的話，就讀數據庫，然后取出數據放入緩存，同時返回響應。
更新的時候，先刪除緩存，然后更新數據庫。
（1）先淘汰緩存
（2）再寫數據庫（這兩步和原來一樣）
（3）休眠1秒，再次淘汰緩存
這么做，可以將1秒內所造成的緩存臟數據，再次刪除。
?
緩存擊穿雪崩穿透
緩存擊穿是針對緩存中沒有但數據庫有的數據。場景是，當某個Key失效后，瞬間涌入大量的請求同一個Key，這些請求不會命中Redis，都會請求到DB，導致數據庫壓力過大
解決辦法
1、設置熱點Key，自動檢測熱點Key，將熱點Key的過期時間加大或者永不過期。
2、加互斥鎖。當發現沒有命中Redis，去查數據庫的時候，在執行更新緩存的操作上加鎖，當一個線程訪問時，其它線程等待，這個線程訪問過后，緩存中的數據會被重建，這樣其他線程就可以從緩存中取值。
緩存雪崩是指大量Key同時失效，對這些Key的請求又會打到DB上，同樣會導致數據庫壓力過大甚至掛掉。
解決辦法
1）讓Key的失效時間分散開，可以在統一的失效時間上再加一個隨機值，或者使用更高級的算法分散失效時間。
2）構建多個redis實例，個別節點掛了還有別的可以用。
3）多級緩存：比如增加本地緩存，減小redis壓力。
4）對存儲層增加限流措施，當請求超出限制，提供降級服務（一般就是返回錯誤即可）
緩存穿透： 一些惡意的請求會故意查詢redis不存在的key,請求量很大，就會對后端系統造成很大的壓力。
1：對查詢結果為空的情況也進行緩存，這樣，再次訪問時，緩存層會直接返回空值。緩存時間設置短一點，或者該key對應的數據insert了之后清理緩存。
2：對一定不存在的key進行過濾。具體請看布隆過濾器
?
解決Redis并發競爭Key問題
多個系統同時對一個 key 進行操作，但是最后執行的順序和我們期望的順序不同，這樣也就導致了結果的不同！
推薦一種方案：分布式鎖（zookeeper 和 redis 都可以實現分布式鎖）。（如果不存在 Redis 的并發競爭 Key 問題，不要使用分布式鎖，這樣會影響性能）
Redis緩存策略
1. volatile-lru：從已設置過期時間的數據集（server.db[i].expires）中挑選最近最少使用的數據淘汰
當需要淘汰一個key時，隨機選擇3個key，淘汰其中間隔時間最長的key。**基本上淘汰key效果很好。后來隨機3個key改成一個配置項"N隨機key"。但把默認值提高改成5個后效果大大提高。考慮到它的效果，你根本不用修改他。
版權聲明：本文為CSDN博主「一只大白兔兔兔兔兔」的原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://fantianzuo.blog.csdn.net/article/details/102580321
2. volatile-ttl：挑選將要過期的數據淘汰
3. volatile-random：任意選擇數據淘汰
4. allkeys-lru：當內存不足以容納新寫入數據時，在鍵空間中，移除最近最少使用的key（這個是最常用的）.
5. allkeys-random：從數據集（server.db[i].dict）中任意選擇數據淘汰
6. no-eviction：禁止驅逐數據，也就是說當內存不足以容納新寫入數據時，新寫入操作會報錯。
哨兵
1）Sentinel(哨兵) 進程用于監控集群中 Master 主服務器工作的狀態
2）在主服務器故障時，可以實現 Master 和 Slave 服務器切換，保證系統的高可用
工作方式
1）每個 Sentinel（哨兵）進程每秒鐘一次向所有服務器和哨兵進程發送一個 PING 命令。
2. 如果一個實例距離最后一次有效回復 PING 命令的時間超過 down-after-milliseconds 選項所指定的值， 這個實例會被 Sentinel（哨兵）進程標記為主觀下線。
3. 如果一個 Master 主服務器被標記為主觀下線，則正在監視這個 Master 主服務器的所有 Sentinel（哨兵）進程要以每秒一次的頻率確認 Master 主服務器的確進入了主觀下線狀態。
4. 當有足夠數量的 Sentinel（哨兵）進程（大于等于配置文件指定的值）在指定的時間范圍內確認 Master 主服務器進入了主觀下線狀態， 則Master 主服務器會被標記為客觀下線（ODOWN）。
5. 在一般情況下， 每個 Sentinel（哨兵）進程會以每 10 秒一次的頻率向集群中的所有Master 主服務器、Slave 從服務器發送 INFO 命令。
6. 當 Master 主服務器被 Sentinel（哨兵）進程標記為客觀下線時，Sentinel（哨兵）進程向下線的 Master 主服務器的所有 Slave 從服務器發送 INFO 命令的頻率會從 10 秒一次改為每秒一次。
7. 若沒有足夠數量的 Sentinel（哨兵）進程同意 Master 主服務器下線， Master 主服務器的客觀下線狀態就會被移除。若 Master 主服務器重新向 Sentinel（哨兵）進程發送 PING 命令返回有效回復，Master 主服務器的主觀下線狀態就會被移除。
解決會話
（粘性session）
你可以設置nginx的分配策略，下次同一個還讓同一個服務器來處理
但是很顯然，這就和分布式和nginx初衷違背了：負載很難保證均衡。
（同步session）
一臺服務器的session給所有服務器復制一份
第一，性能不好。第二，產生了一定的耦合
（專門session）
專門一臺服務器來解決，存session，其它服務器來這個服務器取session再用。
但是也有問題：你這個服務器掛了怎么辦？別的服務器都是依賴這個服務器工作的。我們分布式部署本來就是為了解決性能的瓶頸啊。
很容易想到，我們把那個處理session的服務器搞個集群：
更不行，想想就知道，本來就是為了解決分布式部署的問題，你把單獨解決session的服務器又搞集群，和之前有什么區別呢？還不如一個服務器存一份簡單呢。
可以，但是傳統的關系數據庫是存到硬盤里，速度太慢。
（nosql）
最終，我們的主流辦法使用nosql數據庫，比如redis，來解決這個問題的。
sqlsqlsqlsqllsqlslqslqslq數據類型
整數：1byte是tinyint 2 smallint 3mediumint 4int 8bigint
浮點數：float/double/real。定義方式為：FLOAT(M,D)一共顯示M位其中D位小數點后面
Bit：MySQL把BIT當做字符串類型，而非數字類型。
字符串：CHAR、VARCHAR、BINARY、VARBINARY、BLOB、TEXT、ENUM和SET。
Char固定長度，varchar隨便，BINARY、VARBINARY是二進制，BLOB、TEXT是大的
mysql特點
1.數據以表格的形式出現
2.每行為各種記錄名稱
3.每列為記錄名稱所對應的數據域
4.許多的行和列組成一張表單
5.若干的表單組成database
注：保證數據一致性。
注：關系型數據庫，表與表之間存在對應關系。
注：非關系行數據庫，表之間不存在關系，數據獨立，隨便存。
存儲引擎
如果要提供提交、回滾和恢復的事務安全（ACID 兼容）能力，并要求實現并發控制，InnoDB
如果數據表主要用來插入和查詢記錄，則 MyISAM 引擎提供較高的處理效率。
如果只是臨時存放數據，數據量不大，并且不需要較高的數據安全性，在內存的 MEMORY ，MySQL 中使用該引擎作為臨時表，存放查詢的中間結果。
增刪改
贈
--1. 表名后沒有指定屬性列：插入一條完整的
insert into student values ('201215128', '陳東', '18', '男', 'IS');
--2. 在表明后指定要插入數據的表名及屬性列，屬性列的順序可與表定義中的順序不一致
insert into student(sno, sname, sage, ssex, sdept)
values ('201215138', '陳東棟', '18', '男', 'CS');
--3. 插入部分列，未顯示給出的列按空值計算，當然前提條件是那些列可以為空值
insert into student(sno, sname) values ('201215148', '陳棟');
改
--1. 修改某些符合where子句中的條件的元組的值
update student set sage = 92 where sno = '200215121';
--2. where子句缺省，默認修改所有元組的該屬性的值
--3. 帶子查詢的修改
update sc set grade = 100
where 'CS' in (select sdeptfrom studentwhere sc.sno = student.sno);
刪
Delete from student where sno = '201215148';
范式
最重要的好處歸結為三點：
1.減少數據冗余（這是最主要的好處，其他好處都是由此而附帶的）
2.消除異常（插入異常，更新異常，刪除異常）
3.讓數據組織的更加和諧
第一范式 – 每表中的字段不可再分割
第二范式 – 要有主鍵，并且其他字段依賴于主鍵（方便唯一確定數據行，并定位其他字段）
第三范式 – 在二范式的基礎上，消除傳遞依賴，各種信息只在一個地方存儲，不出現在多張表中。比如學生信息表的學號為主鍵，此時要查看他所在的系信息，那么不能直接將系信息存儲在學生信息表中，因為系信息已經在系別管理表中，此時只能在學生信息中添加系別管理表中的系編號字段（主鍵），這樣既能根據系編號找到系別信息，又避免了冗余存儲的問題。
BC范式 – 每個表中只有一個候選鍵（唯一標識表中每一行的鍵，候選鍵可以包含多個屬性）
?
優化：
1）1對N關系中復制非鍵屬性以減少連接
例：查詢學生以及所在學院名，可以在學生表中不僅存儲學院id，并且存儲學院名
維護時：
如果在UI中，只允許用戶進行選擇，不能自行輸入，保證輸入一致性
如果是程序員，對于類似學院名這種一般不變的代碼表，在修改時直接對兩張表都進行修改；如果經常變化，則可以加一個觸發器。
2）N對N關系中復制屬性，把兩張表中經常需要的內容復制到中間關系表中以減少連接
索引優缺點和使用原則
優點：
1、所有的MySql列類型(字段類型)都可以被索引，也就是可以給任意字段設置索引
2、大大加快數據的查詢速度
缺點：
1、創建索引和維護索引要耗費時間，并且隨著數據量的增加所耗費的時間也會增加
2、占空間，數據也會有最大上線設置的，大量索引文件可能比數據文件更快到上線
3、對表中的數據進行增加刪改時，索引也需要動態的維護，降低了數據的維護速度。
使用原則：
1、對經常更新的表避免過多索引，對經常用于查詢的字段應建索引，
2、數據量小的表最好不要使用索引，可能查詢全部數據比遍歷索引的時間還要短，
3、在值少的列上不要建立索引，比如"性別"字段上只有男女。
3-5、盡量選擇區分度高的列,公式是count(distinct col)/count(*)，表示字段不重復的比例，比例越大我們掃描的記錄數越少
唯一鍵的區分度是1，而一些狀態、性別字段可能在大數據面前區分度就是0
一般需要join的字段我們都要求是0.1以上，即平均1條掃描10條記錄
4、最左前綴匹配原則，非常重要的原則，mysql會一直向右匹配直到遇到范圍查詢(>、<、between、like)就停止匹配
5、索引列不能參與計算，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因：存的都是數據表中的字段值，需要所有元素都應用函數才能比較
索引分類
普通索引
（1）直接創建索引CREATE INDEX index_name ON table(column(length))?
（3）創建表的時候同時創建索引
CREATE TABLE `table` (
??? `id` int(11) NOT NULL AUTO_INCREMENT ,
??? `title` char(255) CHARACTER NOT NULL ,
??? PRIMARY KEY (`id`),
??? INDEX index_name (title(length))
)
唯一索引
列的值必須唯一，但允許有空值。如果是組合索引，則列值的組合必須唯一。
（1）創建唯一索引CREATE UNIQUE INDEX indexName ON table(column(length))
（3）創建表的時候直接指定
主鍵索引
特殊的唯一索引，一個表只能有一個主鍵，不允許有空值。建表同時創建主鍵索引：
CREATE TABLE `table` (
??? `id` int(11) NOT NULL AUTO_INCREMENT ,
??? `title` char(255) NOT NULL ,
??? PRIMARY KEY (`id`)
);
組合索引
指多個字段上創建的索引，只有在查詢條件中使用了創建索引時的第一個字段，索引才會被使用。使用組合索引時遵循最左前綴集合
ALTER TABLE `table` ADD INDEX name_city_age (name,city,age);
全文索引
主要用來查找文本中的關鍵字，而不是直接與索引中的值相比較。fulltext索引跟其它索引大不相同，它更像是一個搜索引擎，而不是簡單的where語句的參數匹配。
fulltext索引配合match against操作使用，而不是一般的where語句加like。
它可以在create table，alter table ，create index使用，不過目前只有char、varchar，text 列上可以創建全文索引。
在數據量較大時候，現將數據放入一個沒有全局索引的表中，然后再用CREATE index創建fulltext索引，要比先為一張表建立fulltext然后再將數據寫入的速度快很多。
CREATE TABLE `table` (
??? `id` int(11) NOT NULL AUTO_INCREMENT ,
??? `content` text CHARACTER NULL ,
??? PRIMARY KEY (`id`),
??? FULLTEXT (content)
);
聚集索引的葉子節點存儲行記錄，因此， InnoDB必須要有，且只有一個聚集索引：
（1）如果表定義了PK，則PK就是聚集索引；
（2）如果表沒有定義PK，則第一個not NULL unique列是聚集索引；
（3）否則，InnoDB會創建一個隱藏的row-id作為聚集索引；
所以PK查詢非常快，直接定位行記錄。
回表：查到一個字段，再去找對應行
5.6優化，索引下推：a=1 and b like….and c like…..,之前按查出第一個條件，返回數據，再篩，現在按索引篩完了like再返回查。
索引區別
哈希索引適合等值查詢，但是無法范圍查詢
哈希索引沒辦法利用索引完成排序
哈希索引不支持多列聯合索引的最左匹配規則
如果有大量重復鍵值的情況下，哈希索引的效率會很低，因為存在哈希碰撞問題
?
局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用——程序運行期間所需要的數據通常比較集中。磁盤順序讀取的效率很高（不需尋道時間，只需很少的旋轉時間）
預讀的長度一般為頁的整倍數。
在經典B+Tree的基礎上進行了優化，增加了順序訪問指針。
平衡樹缺點：深、離得遠、
?
B和b+：只存索引，值全在葉子節點。
默認16KB一頁，1行數據1K，一頁16條數據。假設 bigint=8字節,指針在innodb是6字節，8+6=14，16KB/14=1170，三層可滿足千萬記錄。
事務特性：ACID
原子性（Atomicity）：事務作為一個整體執行，對數據的操作要么全被執行，要么都不執行。
一致性（Consistency）：事務應確保數據庫的狀態從一個一致狀態轉變為另一個一致狀態。一致狀態的含義是數據庫中的數據應滿足完整性約束（約定好的約束，如：AB相互轉錢，A有500，B也有500，那么無論他們怎么轉，最后的數額總數都會是1000）
隔離性（Isolation）：多個事務并發執行時，不互相影響。
持久性（Durability）：一個事務一旦提交，他對數據庫的修改應該永久保存在數據庫中。
并發錯誤
第一類丟失更新：某一個事務的回滾，導致另外一個事務已更新的數據丟失了。
第二類丟失更新：某一個事務的提交，導致另外一個事務已更新的數據丟失了。
臟讀：另一個事務修改了，但尚未提交，本事務讀到未被提交的數據。
不可重復讀：一個執行中，另一個更新，本事務先后讀到的數據不一致。
幻讀：某事務對同一個表前后查詢到的行數不一致（中間有人插入）
幻讀解決辦法：使用串行化讀的隔離級別
隔離級別
- Read Uncommitted：讀取未提交的數據。事務可以讀取到另一個事務未提交的修改。
- Read Committed：（有的庫默認）讀取已提交的數據。事務只能讀取另個事務已提交修改。
- Repeatable Read：（mysql默認）可重復讀。同一個事務多次讀取相同數據返回結果一樣。
- Serializable：串行化 事務串行執行。讀寫數據鎖表
1、讀提交時，寫數據只會鎖住相應的行
2、可重復讀時，如果檢索條件有索引（包括主鍵索引），默認加鎖方式是next-key 鎖；如果檢索條件沒有索引，更新數據鎖住整張表。一個間隙被事務加了鎖，其他事務是不能在這個間隙插入記錄的，這樣可以防止幻讀。
是否會發生
并發控制技術（鎖）
封鎖（locking）（主要使用的）
基本的封鎖類型有兩種：排它鎖（X鎖，exclusive locks）、共享鎖（S 鎖，share locks）
排它鎖又稱寫鎖，對A加排它鎖之后，其他事務不能對A加 任何類型的鎖（排斥讀和寫）
共享鎖又稱讀鎖，對A加共享鎖之后，其他事務只能對A加S鎖，不能加X鎖（只排斥寫）
表級鎖：開銷小，加鎖快、鎖沖突概率高、不死鎖。
行級鎖：mysql默認，開銷大、加鎖慢、鎖沖突概率高、可能死鎖
間隙鎖（NK）：行級，使用范圍條件時，對范圍內不存在的記錄加鎖。一是為了防止幻讀，二是為了滿足恢復和復制的需要
增加行級鎖之前，InnoDB會自動給表加意向鎖；
? 執行增刪改語句時，InnoDB會自動給數據加排他鎖；
? 執行查詢語句時
共享鎖（S）：SELECT … FROM … WHERE … LOCK IN SHARE MODE;
排他鎖（X）：SELECT … FROM … WHERE … FOR UPDATE;
間隙鎖（NK）：上述SQL采用范圍條件時，InnoDB對不存在的記錄自動增加間隙鎖。
?
MVCC的實現，是通過保存數據在某個時間點的快照來實現的。也就是說，不管需要執行多長時間，每個事務看到的數據是一致的。根據事務開始的時間不同，每個事物對同一張表，同一時刻看到的數據可能是不一樣的。
否則就更新數據（版本號+1）。
悲觀鎖：假定會發生并發沖突，屏蔽一切可能違反數據完整性的操作。
樂觀鎖：假設不會發生并發沖突，只在提交操作時檢查是否違反數據完整性。
使用數據版本（Version）記錄機制實現
樂觀鎖（自定義）
- 版本號、時間戳等。。。在更新數據前，檢查版本號是否發生變化。若變化則取消本次更新，
1. 版本號機制
UPDATE … SET …,VERSION=#{version+1} WHERE … AND VERSION=${version}
2. CAS算法（Compare and swap）
是一種無鎖的算法，該算法涉及3個操作數（內存值V、舊值A、新值B），當V等于A時，
采用原子方式用B的值更新V的值。該算法通常采用自旋操作，也叫自旋鎖。它的缺點是：
? ABA問題：某線程將A該為B，再改回A，則CAS會誤認為A沒被修改過。
? 自旋操作采用循環的方式實現，若加鎖時間長，則會給CPU帶來巨大的開銷。
? CAS只能保證一個共享變量的原子操作。
?
死鎖
? 場景
事務1: UPDATE T SET … WHERE ID = 1; UPDATE T SET … WHERE ID = 2;
事務2: UPDATE T SET … WHERE ID = 2; UPDATE T SET … WHERE ID = 1;
? 解決方案
1. 一般InnoDB會自動檢測到，并使一個事務回滾，另一個事務繼續；
2. 設置超時等待參數 innodb_lock_wait_timeout；
? 避免死鎖
1. 不同的業務并發訪問多個表時，應約定以相同的順序來訪問這些表；
2. 以批量的方式處理數據時，應事先對數據排序，保證線程按固定的順序來處理數據；
3. 在事務中，如果要更新記錄，應直接申請足夠級別的鎖，即排他鎖；
分布式事務
分布式事務就是指事務的參與者、支持事務的服務器、資源服務器以及事務管理器分別位于不同的分布式系統的不同節點之上。
分布式事務產生的原因總的來說有兩個：1.service產生多個節點2.resource產生多個節點
CAP理論
- C (一致性):對某個指定的客戶端來說，讀操作能返回最新的寫操作。
對于數據分布在不同節點上的數據來說，如果在某個節點更新了數據，那么在其他節點如果都能讀取到這個最新的數據，那么就稱為強一致，如果有某個節點沒有讀取到，那就是分布式不一致。
A (可用性)：非故障的節點在合理的時間內返回合理的響應(不是錯誤和超時的響應)。
可用性的兩個關鍵一個是合理的時間，一個是合理的響應。合理的時間指的是請求不能無限被阻塞，應該在合理的時間給出返回。合理的響應指的是系統應該明確返回結果并且結果是正確的，這里的正確指的是比如應該返回50，而不是返回40。
P (分區容錯性):當出現網絡分區后，系統能夠繼續工作。打個比方，這里個集群有多臺機器，有臺機器網絡出現了問題，但是這個集群仍然可以正常工作。
熟悉CAP的人都知道，三者不能共有，如果感興趣可以搜索CAP的證明，在分布式系統中，網絡無法100%可靠，分區其實是一個必然現象，如果我們選擇了CA而放棄了P，那么當發生分區現象時，為了保證一致性，這個時候必須拒絕請求，但是A又不允許，所以分布式系統理論上不可能選擇CA架構，只能選擇CP或者AP架構。
分布式事務常見的方案：2PC（兩階段提交）協調者（都成功才執行）
運行過程：
準備階段（協調者詢問參與者事務是否執行成功，參與者發回事務執行結果）
提交階段（如果事務在每個參與者上都執行成功，事務協調者發送通知讓參與者提交事務；否則，協調者發送通知讓參與者回滾事務）
需要注意的是，在準備階段，參與者執行了事務，但是還未提交。只有在提交階段接收到協調者發來的通知后，才進行提交或者回滾。
存在問題：
1.同步阻塞：所有事務參與者在等待其它參與者時都阻塞。
2.單點問題：協調者在 2PC 中起到非常大的作用，發生故障將會造成很大影響。
3.數據不一致：網絡異常，只有部分參與者接收到 Commit 消息，只有部分參與者提交了事務，使得系統數據不一致。
?
SQL語句性能優化
1.??? 對查詢進行優化，應盡量避免全表掃描，首先應考慮在 where 及 order by 涉及的列上建立索引。
2.??? 應盡量避免在 where 子句中使用!=或<>操作符， MySQL只有對以下操作符才使用索引：<，<=，=，>，>=，BETWEEN，IN，以及某些時候的LIKE。
3.??? 應盡量避免在 where 子句中使用 or 來連接條件， 否則將導致引擎放棄使用索引而進行全表掃描，可以使用UNION合并查詢
4.??? 盡可能的使用 varchar代替 char， 因為首先變長字段存儲空間小，可以節省存儲空間，其次對于查詢來說，在一個相對較小的字段內搜索效率顯然要高些。
索引的優化
1.避免有索引但未被用到的情況：(1) Like的參數以通配符開頭時（2）where條件不符合最左前綴原則時（3）使用！= 或 <> 操作符時（4）使用or來連接條件
2.避免使用 Select *
3.對order by語句進行優化：1.重寫order by語句以使用索引 2.避免在order by子句中使用表達式。
4.對group by語句進行優化：將不需要的記錄在group by之前過濾掉
5.使用exists代替in
分庫分表
垂直分庫就是根據業務耦合性，將關聯度低的不同表存儲在不同的數據庫。
水平切分分為庫內分表和分庫分表，是根據表內數據內在的邏輯關系，將同一個表按不同的條件分散到多個數據庫或多個表中，每個表中只包含一部分數據，從而使得單個表的數據量變小，達到分布式的效果。
Kafka
引入依賴- spring-kafka
? 配置Kafka- 配置server、consumer
? 訪問Kafka
- 生產者kafkaTemplate.send(topic, data);
- 消費者@KafkaListener(topics = {"test"})
public void handleMessage(ConsumerRecord record) {}
一、Kafka的優勢如下：
?????? 高吞吐量、低延遲：kafka每秒可以處理幾十萬條消息，它的延遲最低只有幾毫秒；
?????? 持久性、可靠性：消息被持久化到本地磁盤，并且支持數據備份防止數據丟失；
?????? 容錯性：允許集群中節點故障（若副本數量為n,則允許n-1個節點故障）；
?????? 高并發：支持數千個客戶端同時讀寫。
二、Kafka適合以下應用場景：
?????? 日志收集：一個公司可以用Kafka可以收集各種服務的log，通過kafka以統一接口服務的方式開放給各種consumer；
?????? 消息系統：解耦生產者和消費者、緩存消息等；
??????? 用戶活動跟蹤：kafka經常被用來記錄web用戶或者app用戶的各種活動，如瀏覽網頁、搜索、點擊等活動，這些活動信息被各個服務器發布到kafka的topic中，然后消費者通過訂閱這些topic來做實時的監控分析，亦可保存到數據庫；
?????? 運營指標：kafka也經常用來記錄運營監控數據。包括收集各種分布式應用的數據，生產各種操作的集中反饋，比如報警和報告；
?????? 流式處理：比如spark streaming和storm。
?
Broker：Kafka節點，一個Kafka節點就是一個broker，多個broker可以組成一個Kafka集群。
Topic：一類消息，消息存放的目錄即主題，例如page view日志、click日志等都可以以topic的形式存在，Kafka集群能夠同時負責多個topic的分發。
Partition：topic物理上的分組，一個topic可以分為多個partition，每個partition是一個有序的隊列
Segment：partition物理上由多個segment組成，每個Segment存著message信息
Producer : 生產message發送到topic
Consumer : 訂閱topic消費message, consumer作為一個線程來消費
Consumer Group：一個Consumer Group包含多個consumer, 這個是預先在配置文件中配置好的。各個consumer可以組成一個組（group ），partition中的每個message只能被組中的一個consumer消費，如果message可以被多個consumer消費的話，那么這些consumer必須在不同的組。
Kafka不支持一個partition中的message由兩個或兩個以上的consumer thread來處理，即便是來自不同的consumer group的也不行。它不能像AMQ那樣可以多個BET作為consumer去處理message，這是因為多個BET去消費一個Queue中的數據的時候，由于要保證不能多個線程拿同一條message，所以就需要行級別悲觀所（for update）,這就導致了consume的性能下降，吞吐量不夠。而kafka為了保證吞吐量，只允許一個consumer線程去訪問一個partition。如果覺得效率不高的時候，可以加partition的數量來橫向擴展，那么再加新的consumer thread去消費。這樣沒有鎖競爭，充分發揮了橫向的擴展性，吞吐量極高。這也就形成了分布式消費的概念。
import java.util.*;class BoundedBlockingQueue {private int size;private int capacity;private int[] queue;// 指向隊頭的指針private int last;??// 指向隊列尾private int first;// JDK 的通知模式private final ReentrantLock lock;private final Condition notFull;private final Condition notEmpty;public BoundedBlockingQueue(int capacity) {this.size = 0;this.last = 0;this.first = 0;this.capacity = capacity;this.queue = new int[capacity+1];this.lock = new ReentrantLock();notFull = this.lock.newCondition();notEmpty = this.lock.newCondition();}// 進隊列public void enqueue(int element) throws InterruptedException {// 隊列不滿的情況下可以入隊尾,在隊尾添加元素final ReentrantLock lock = this.lock;lock.lockInterruptibly();try{while(size == capacity)notFull.await();// 隊列不滿的情況下可以入隊尾,在隊尾添加元素queue[last] = element;last = (last + 1)% capacity;size ++;notEmpty.signal();}finally{lock.unlock();}}// 出隊列public int dequeue() throws InterruptedException {// 有元素的情況下才可以出隊列,刪掉隊頭的元素final ReentrantLock lock = this.lock;lock.lockInterruptibly();try{while(size == 0)notEmpty.await();int e = queue[first];first = (first + 1) % capacity;size --;notFull.signal();return e;}finally{lock.unlock();}}public int size() {return size;}}Es
? 搜索服務
- 將帖子保存至Elasticsearch服務器。
- 從Elasticsearch服務器刪除帖子。
- 從Elasticsearch服務器搜索帖子。
? 發布事件
- 發布帖子時，將帖子異步的提交到Elasticsearch服務器。
- 增加評論時，將帖子異步的提交到Elasticsearch服務器。
- 在消費組件中增加一個方法，消費帖子發布事件。
? 顯示結果
- 在控制器中處理搜索請求，在HTML上顯示搜索結果。
?
ES:?????? index(索引)-->type(類型)-->document(文檔)-->field(字段)
mysql:?? database(數據庫)-->table(表)-->row(行)-->line(列)
ES是一個開源分布式搜索引擎。
同時ES是分布式文檔數據庫，每個字段均可被索引，而且每個字段的數據均可被搜索，能夠橫向擴展至數以百計的服務器存儲以及處理PB級的數據。
可以在極短的時間內存儲、搜索和分析大量的數據。通常作為具有復雜搜索場景情況下的核心發動機。
?
分別為每個field都建立了一個倒排索引，Kate, John, 24, Female這些叫term，而[1,2]就是Posting List。Posting list就是一個int的數組，存儲了所有符合某個term的文檔id。
?
內存字典樹+硬盤倒排索引。
public class Trie {private boolean is_string=false;private Trie next[]=new Trie[26];public Trie(){}public void insert(String word){//插入單詞Trie root=this;char w[]=word.toCharArray();for(int i=0;i<w.length;++i){if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();root=root.next[w[i]-'a'];}root.is_string=true;}public boolean search(String word){//查找單詞Trie root=this;char w[]=word.toCharArray();for(int i=0;i<w.length;++i){if(root.next[w[i]-'a']==null)return false;root=root.next[w[i]-'a'];}return root.is_string;}public boolean startsWith(String prefix){//查找前綴Trie root=this;char p[]=prefix.toCharArray();for(int i=0;i<p.length;++i){if(root.next[p[i]-'a']==null)return false;root=root.next[p[i]-'a'];}return true;}}總結
以上是生活随笔為你收集整理的当年，兔子学姐靠这个面试小抄拿了个22k的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C# 静态类的使用
- 下一篇： [笔记].等占空比分频器的几种写法.[V