class ListNode {
      int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }

1.LRU演算法java資料結構實作

LRU:(least recently used) 最近最少使用演算法，LRU演算法的java中資料結構的實作是一個LRU演算法在面試中經常被問到的問題，我們可以用LinkedList來表示最近和最少使用，將訪問過的資料用LinkedList資料結構進行存盤，如果查找最少使用，直接回傳LinkedList的尾節點即可，如果添加一個最近訪問的資料a，可以將a從鏈表中的位置洗掉，移到鏈表的頭部，

但是鏈表中查詢資料DATA的位置一般訪問速度慢，所以需要借助其它資料結構來完成查找，我們知道HashMap是一個高效的查詢資料結構，如果我們將該資料DATA作為鍵，DATA對應的節點作為值，存盤在HashMap中，那么，我們可以得到查詢復雜度為O(1)的操作，

JAVA中已經幫助我們實作了一個這樣的資料結構，LinkedHashMap.LinkedHashMap存放的鍵值對和存放時的位置一致，不會變化，可以設定LinkedHashMap按照插入的順序排序，也可以按照訪問的順序排序，最先訪問的放置在最后面，最近訪問的在最前面，

LinkedHashMap自身已經實作了順序存盤，默認情況下是按照元素的添加順序存盤，也可以啟用按照訪問順序存盤，即最近讀取的資料放在最前面，最早讀取的資料放在最后面，然后它還有一個判斷是否洗掉最老資料的方法，默認是回傳false，即不洗掉資料，我們使用LinkedHashMap實作LRU快取的方法就是對LinkedHashMap實作簡單的擴展，

2.紅黑樹

1. 節點是紅色或者是黑色；
2. 每個葉節點（NIL或空節點）是黑色；
3. 每個紅色節點的兩個子節點都是黑色的（也就是說不存在兩個連續的紅色節點）；
4. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點，

優勢：紅黑樹相比avl樹，在檢索的時候效率其實差不多，都是通過平衡來二分查找，但對于插入洗掉等操作效率提高很多，紅黑樹不像avl樹一樣追求絕對的平衡，他允許區域很少的不完全平衡，這樣對于效率影響不大，但省去了很多沒有必要的調平衡操作，avl樹調平衡有時候代價較大，所以效率不如紅黑樹，在現在很多地方都是底層都是紅黑樹的天下啦，
紅黑樹和AVL樹都是最常用的平衡二叉搜索樹，它們的查找、洗掉、修改都是O(lgn) time

2.1 AVL樹和紅黑樹有幾點比較和區別：

（1）AVL樹是更加嚴格的平衡，因此可以提供更快的查找速度，一般讀取查找密集型任務，適用AVL樹，
（2）紅黑樹更適合于插入修改密集型任務，
（3）通常，AVL樹的旋轉比紅黑樹的旋轉更加難以平衡和除錯，
總結：
（1）AVL以及紅黑樹是高度平衡的樹資料結構，它們非常相似，真正的區別在于在任何添加/洗掉操作時完成的旋轉操作次數，
（2）兩種實作都縮放為a O(lg N)，其中N是葉子的數量，但實際上AVL樹在查找密集型任務上更快：利用更好的平衡，樹遍歷平均更短，另一方面，插入和洗掉方面，AVL樹速度較慢：需要更高的旋轉次數才能在修改時正確地重新平衡資料結構，
（3）在AVL樹中，從根到任何葉子的最短路徑和最長路徑之間的差異最多為1，在紅黑樹中，差異可以是2倍，
（4）兩個都給O（log n）查找，但平衡AVL樹可能需要O（log n）旋轉，而紅黑樹將需要最多兩次旋轉使其達到平衡（盡管可能需要檢查O（log n）節點以確定旋轉的位置），旋轉本身是O（1）操作，因為你只是移動指標，

3.HashMap的長度為什么要是2的n次方

HashMap為了存取高效，要盡量較少碰撞，就是要盡量把資料分配均勻，每個鏈表長度大致相同，這個實作就在把資料存到哪個鏈表中的演算法；
這個演算法實際就是取模，hash%length，計算機中直接求余效率不如位移運算，原始碼中做了優化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方；
為什么這樣能均勻分布減少碰撞呢？2的n次方實際就是1后面n個0，2的n次方-1 實際就是n個1；

4.協程

協程誕生解決的是低速IO和高速的CPU的協調問題，解決這類問題主要有三個有效途徑：

?異步非阻塞網路編程（libevent、libev、redis、Nginx、memcached這類）
?協程（golang、gevent）
?“輕量級執行緒”，相當于是在語言層面做抽象（Erlang）

協程和執行緒差異

1. 協程其實可以認為是比執行緒更小的執行單元，為啥說他是一個執行單元，因為他自帶CPU背景關系，這樣只要在合適的時機，我們可以把一個協程 切換到 另一個協程，只要這個程序中保存或恢復 CPU背景關系那么程式還是可以運行的，

2. 一個執行緒可以多個協程，一個行程也可以單獨擁有多個協程，這樣python中則能使用多核CPU，

3. 執行緒行程都是同步機制，而協程則是異步

4. 協程的開銷遠遠小于執行緒的開銷

5. 協程能保留上一次呼叫時的狀態，每次程序重入時，就相當于進入上一次呼叫的

1.協程(用戶級執行緒)完全由用戶自己的程式進行調度（協作式調度），需要協程 自己主動把控制權轉讓出去之后，其他協程才能被執行到，

2.協程，是在應用層模擬的執行緒，他避免了背景關系切換的額外耗費，兼顧了多執行緒的優點，簡化了高并發程式的復雜度，協程還是通過共享記憶體通訊.

目前的協程框架一般都是設計成 1:N 模式，
所謂 1:N 就是一個執行緒作為一個容器里面放置多個協程，
那么誰來適時的切換這些協程？答案是有協程自己主動讓出CPU，
也就是每個協程池里面有一個調度器，這個調度器是被動調度的，
意思就是他不會主動調度，
而且當一個協程發現自己執行不下去了(比如異步等待網路的資料回來，但是當前還沒有資料到)，
這個時候就可以由這個協程通知調度器，
這個時候執行到調度器的代碼，調度器根據事先設計好的調度演算法找到當前最需要CPU的協程，
切換這個協程的CPU背景關系把CPU的運行權交個這個協程，直到這個協程出現執行不下去需要等等的情況，
或者它呼叫主動讓出CPU的API之類，觸發下一次調度，對的沒錯就是類似于 領匯入模式那么這個實作有沒有問題？
其實是有問題的，假設這個執行緒中有一個協程是CPU密集型的他沒有IO操作，也就是自己不會主動觸發調度器調度的程序，
那么就會出現其他協程得不到執行的情況，所以這種情況下需要程式員自己避免，

5.HashMap為什么不是執行緒安全？

jdk7中由于頭插法，會存在resize后鏈表中形成環的情況，
執行緒1阻塞前鏈表情況：a->b->null
執行緒2此時執行，會采用頭插法將該鏈表放入新的table，放入后變成b->a->null
執行緒1此時回傳，同樣采用頭插法插入該執行緒自己的新的table中，兩次回圈后變為b->a，但是由于執行緒2執行時的后果會導致b的next不是null而是a，所以回圈多執行一次，e此時變為a會導致a.next = newTablei然后發生回圈，

jdk8造成執行緒不安全分2中情況；
1.并發執行put操作時會出現hashcode沖突從而導致資料覆寫，造成執行緒不安全；
鏈接: hsahmap為什么執行緒不安全 https://blog.csdn.net/weixin_43092168/article/details/89791106
2.resize的時候造成的，jdk8在（++size>threshold）代碼片段，如果并發操作，可能導致兩次擴容，但最終結果只有一次擴容的效果，從而執行緒不安全(回圈鏈表)

6.如何處理TCP的黏包和拆包問題：

通常會有以下一些常用的方法：
1.使用帶訊息頭的協議、訊息頭存盤訊息開始標識及訊息長度資訊，服務端獲取訊息頭的時候決議出訊息長度，然后向后讀取該長度的內容，
2.設定定長訊息，服務端每次讀取既定長度的內容作為一條完整訊息，當訊息不夠長時，空位補上固定字符，
3.設定訊息邊界，服務端從網路流中按訊息編輯分離出訊息內容，一般使用‘\n’，

7.Spring 中使用了哪些設計模式？

工廠模式：
spring中的BeanFactory就是簡單工廠模式的體現，根據傳入唯一的標識來獲得bean物件；
單例模式：
提供了全域的訪問點BeanFactory；
代理模式：
AOP功能的原理就使用代理模式（1、JDK動態代理，2、CGLib位元組碼生成技術代理，）
裝飾器模式：
依賴注入就需要使用BeanWrapper；
觀察者模式：
spring中Observer模式常用的地方是listener的實作，如ApplicationListener，
策略模式：
Bean的實體化的時候決定采用何種方式初始化bean實體（反射或者CGLIB動態位元組碼生成），
鏈接: 設計模式https://blog.csdn.net/qq_35190492/article/details/105992063.

8.springMVC流程：

（1）：用戶請求發送給DispatcherServlet，DispatcherServlet呼叫HandlerMapping處理器映射器；

（2）：HandlerMapping根據xml或注解找到對應的處理器，生成處理器物件回傳給DispatcherServlet；

（3）：DispatcherServlet會呼叫相應的HandlerAdapter；

（4）：HandlerAdapter經過適配呼叫具體的處理器去處理請求，生成ModelAndView回傳給DispatcherServlet

（5）：DispatcherServlet將ModelAndView傳給ViewReslover決議生成View回傳給DispatcherServlet；

（6）：DispatcherServlet根據View進行渲染視圖；

->DispatcherServlet->HandlerMapping->Handler
->DispatcherServlet->HandlerAdapter處理handler->ModelAndView
->DispatcherServlet->ModelAndView->ViewReslover->View
->DispatcherServlet->回傳給客戶

9.skiplist與平衡樹、哈希表的比較

1.skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的，因此，在哈希表上只能做單個key的查找，不適宜做范圍查找，所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節點，
2.在做范圍查找的時候，平衡樹比skiplist操作要復雜，在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點，如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實作，而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實作，
3.平衡樹的插入和洗掉操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和洗掉只需要修改相鄰節點的指標，操作簡單又快速，
4.從記憶體占用上來說，skiplist比平衡樹更靈活一些，一般來說，平衡樹每個節點包含2個指標（分別指向左右子樹），而skiplist每個節點包含的指標數目平均為1/(1-p)，具體取決于引數p的大小，如果像Redis里的實作一樣，取p=1/4，那么平均每個節點包含1.33個指標，比平衡樹更有優勢，
5.查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些，所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實作的，
6.從演算法實作難度上來比較，skiplist比平衡樹要簡單得多，

10.執行緒間通信的幾種實作方式

方式一：使用 volatile 關鍵字
基于 volatile 關鍵字來實作執行緒間相互通信是使用共享記憶體的思想，大致意思就是多個執行緒同時監聽一個變數，當這個變數發生變化的時候 ，執行緒能夠感知并執行相應的業務，這也是最簡單的一種實作方式
方式二：使用Object類的wait() 和 notify() 方法
眾所周知，Object類提供了執行緒間通信的方法：wait()、notify()、notifyaAl()，它們是多執行緒通信的基礎，而這種實作方式的思想自然是執行緒間通信，
注意： wait和 notify必須配合synchronized使用，wait方法釋放鎖，notify方法不釋放鎖

11.JVM記憶體模型

JVM記憶體空間分為五部分，分別是：方法區、堆、Java虛擬機堆疊、本地方法堆疊、程式計數器
1.方法區主要用來存放類資訊、類的靜態變數、常量、運行時常量池等，方法區的大小是可以動態擴展的，
2.堆主要存放的是陣列、類的實體物件、字串常量池等，
3.Java虛擬機堆疊是描述JAVA方法運行程序的記憶體模型，Java虛擬機堆疊會為每一個即將執行的方法創建一個叫做“堆疊幀”的區域，該區域用來存盤該方法運行時需要的一些資訊，包括：區域變數表、運算元堆疊、動態鏈接、方法回傳地址等，比如我們方法執行程序中需要創建變數時，就會將區域變數插入到區域變數表中，區域變數的運算、傳遞等在運算元堆疊中進行，當方法執行結束后，這個方法對應的堆疊幀將出堆疊，并釋放記憶體空間，堆疊中會發生的兩種例外，StackOverFlowError和OutOfMemoryError,StackOverFlowError表示當前執行緒申請的堆疊超過了事先定好的堆疊的最大深度，但記憶體空間可能還有很多， 而OutOfMemoryError是指當執行緒申請堆疊時發現堆疊已經滿了，而且記憶體也全都用光了，

4.本地方法堆疊結構上和Java虛擬機堆疊一樣，只不過Java虛擬機堆疊是運行Java方法的區域，而本地方法堆疊是運行本地方法的記憶體模型，運行本地方法時也會創建堆疊幀，同樣堆疊幀里也有區域變數表、運算元堆疊、動態鏈接和方法回傳地址等，在本地方法執行結束后堆疊幀也會出堆疊并釋放記憶體資源，也會發生OutOfMemoryError，

5.最后是程式計數器，程式計數器是一個比較小的記憶體空間，用來記錄當前執行緒正在執行的那一條位元組碼指令的地址，如果當前執行緒正在執行的是本地方法，那么此時程式計數器為空，程式計數器有兩個作用，1、位元組碼解釋器通過改變程式計數器來一次讀取指令，從而實作代碼的流程控制，比如我們常見的順序、回圈、選擇、例外處理等，2、在多執行緒的情況下，程式計數器用來記錄當前執行緒執行的位置，當執行緒切換回來的時候仍然可以知道該執行緒上次執行到了哪里，而且程式計數器是唯一一個不會出現OutOfMeroryError的記憶體區域，

12.談談synchronized與ReentrantLock的區別？

• ① 底層實作上來說，synchronized 是JVM層面的鎖，是Java關鍵字，通過monitor物件來完成（monitorenter與monitorexit），物件只有在同步塊或同步方法中才能呼叫wait/notify方法，ReentrantLock 是從jdk1.5以來（java.util.concurrent.locks.Lock）提供的API層面的鎖，
  synchronized 的實作涉及到鎖的升級，具體為無鎖、偏向鎖、自旋鎖、向OS申請重量級鎖，ReentrantLock實作則是通過利用CAS（CompareAndSwap）自旋機制保證執行緒操作的原子性和volatile保證資料可見性以實作鎖的功能，
• ② 是否可手動釋放：
  synchronized 不需要用戶去手動釋放鎖，synchronized 代碼執行完后系統會自動讓執行緒釋放對鎖的占用； ReentrantLock則需要用戶去手動釋放鎖，如果沒有手動釋放鎖，就可能導致死鎖現象，一般通過lock()和unlock()方法配合try/finally陳述句塊來完成，使用釋放更加靈活，
• ③ 是否可中斷
  synchronized是不可中斷型別的鎖，除非加鎖的代碼中出現例外或正常執行完成； ReentrantLock則可以中斷，可通過trylock(long timeout,TimeUnit unit)設定超時方法或者將lockInterruptibly()放到代碼塊中，呼叫interrupt方法進行中斷，
• ④ 是否公平鎖
  synchronized為非公平鎖 ReentrantLock則即可以選公平鎖也可以選非公平鎖，通過構造方法new ReentrantLock時傳入boolean值進行選擇，為空默認false非公平鎖，true為公平鎖，
• ⑤ 鎖是否可系結條件Condition
  synchronized不能系結； ReentrantLock通過系結Condition結合await()/singal()方法實作執行緒的精確喚醒，而不是像synchronized通過Object類的wait()/notify()/notifyAll()方法要么隨機喚醒一個執行緒要么喚醒全部執行緒，
• ⑥ 鎖的物件
  synchronzied鎖的是物件，鎖是保存在物件頭里面的，根據物件頭資料來標識是否有執行緒獲得鎖/爭搶鎖；ReentrantLock鎖的是執行緒，根據進入的執行緒和int型別的state標識鎖的獲得/爭搶，

13.ArrayList的大小是如何自動增加的？

1、添加元素時，首先進行判斷是否大于默認容量10

2、如果，小于默認容量，直接在原來基礎上+1，元素添加完畢

3、如果，大于默認容量，則需要進行擴容，擴容核心是grow()方法

• 3.1 擴容之前，首先創建一個新的陣列，且舊陣列被復制到新的陣列中
  這樣就得到了一個全新的副本，我們在操作時就不會影響原來陣列了
• 3.2 然后通過位運算子將新的容量更新為舊容量的1.5陪（原來長度的一半再加上原長度也就是每次擴容是原來的1.5倍）
• 3.3 如果新的容量-舊的容量<=0，就拿新的容量-最大容量長度如果<=0的，那么最終容量就是擴容后的容量

4.添加（add）方法的實作，添加時首先檢查陣列的容量是否滿足

• 1、添加元素時，首先進行判斷是否大于默認容量10
• 2、如果，小于默認容量，直接在原來基礎上+1，元素添加完畢
• 3、如果，大于默認容量，則需要進行擴容，擴容核心是grow()方法
  • 3.1 擴容之前，首先創建一個新的陣列，且舊陣列被復制到新的陣列中
    這樣就得到了一個全新的副本，我們在操作時就不會影響原來陣列了

• 3.2 然后通過位運算子將新的容量更新為舊容量的1.5陪
• 3.3 如果新的容量-舊的容量<=0，就拿新的容量-最大容量長度如果<=0的，那么最終容量就是擴容后的容量

14.索引的資料結構

為什么資料庫要用b+樹而不用b樹，平衡二叉樹

1.平衡二叉樹

平衡二叉樹是采用二分法思維，平衡二叉查找樹除了具備二叉樹的特點，最主要的特征是樹的左右兩個子樹的層級最多相差1，在插入洗掉資料時通過左旋/右旋操作保持二叉樹的平衡，不會出現左子樹很高、右子樹很矮的情況，
使用平衡二叉查找樹查詢的性能接近于二分查找法，時間復雜度是 O(log2n)，查詢id=6，只需要兩次IO，
就這個特點來看，可能各位會覺得這就很好，可以達到二叉樹的理想的情況了，然而依然存在一些問題：
1.時間復雜度和樹高相關，樹有多高就需要檢索多少次，每個節點的讀取，都對應一次磁盤 IO 操作，樹的高度就等于每次查詢資料時磁盤 IO 操作的次數，磁盤每次尋道時間為10ms，在表資料量大時，查詢性能就會很差，（1百萬的資料量，log2n約等于20次磁盤IO，時間20*10=0.2s）

3.平衡二叉樹不支持范圍查詢快速查找，范圍查詢時需要從根節點多次遍歷，查詢效率不高，

2.B樹：改造二叉樹

MySQL的資料是存盤在磁盤檔案中的，查詢處理資料時，需要先把磁盤中的資料加載到記憶體中，磁盤IO 操作非常耗時，所以我們優化的重點就是盡量減少磁盤 IO 操作，訪問二叉樹的每個節點就會發生一次IO，如果想要減少磁盤IO操作，就需要盡量降低樹的高度，那如何降低樹的高度呢？

• 這種資料結構我們稱為B樹，B樹是一種多叉平衡查找樹，如下圖主要特點：
  • 1.B樹的節點中存盤著多個元素，每個內節點有多個分叉，
  • 2.節點中的元素包含鍵值和資料，節點中的鍵值從大到小排列，也就是說，在所有的節點都儲存資料，
  • 3.父節點當中的元素不會出現在子節點中，
  • 4.所有的葉子結點都位于同一層，葉節點具有相同的深度，葉節點之間沒有指標連接，

• 缺點：

  • 1.B樹不支持范圍查詢的快速查找，你想想這么一個情況如果我們想要查找10和35之間的資料，查找到15之后，需要回到根節點重新遍歷查找，需要從根節點進行多次遍歷，查詢效率有待提高，

  • 2.如果data存盤的是行記錄，行的大小隨著列數的增多，所占空間會變大，這時，一個頁中可存盤的資料量就會變少，樹相應就會變高，磁盤IO次數就會變大，

15.Nginx

作業流程：

1、用戶通過域名發出訪問Web服務器的請求，該域名被DNS服務器決議為反向代理服務器的IP地址；
2、反向代理服務器接受用戶的請求；
3、反向代理服務器在本地快取中查找請求的內容，找到后直接把內容發送給用戶；
4、如果本地快取里沒有用戶所請求的資訊內容，反向代理服務器會代替用戶向源服務器請求同樣的資訊內容，并把資訊內容發給用戶，如果資訊內容是非快取的還會把它保存到快取中，

Nginx模塊：

Nginx有五大優點：模塊化、事件驅動、異步、非阻塞、多行程單執行緒，由內核和模塊組成的，其中內核完成的作業比較簡單，僅僅通過查找組態檔將客戶端請求映射到一個location block，然后又將這個location block中所配置的每個指令將會啟動不同的模塊去完成相應的作業，

作用：

• 保護了真實的web服務器，保證了web服務器的資源安全
• 節約了有限的IP地址資源
• 減少WEB服務器壓力，提高回應速度
  • 反向代理就是通常所說的web服務器加速，它是一種通過在繁忙的web服務器和外部網路之間增加一個高速的web緩沖服務器來降低實際的web服務器的負載的一種技術，反向代理是針對web服務器提高加速功能，作為代理快取，它并不是針對瀏覽器用戶，而針對一臺或多臺特定的web服務器，它可以代理外部網路對內部網路的訪問請求，
  • 反向代理服務器會強制將外部網路對要代理的服務器的訪問經過它，這樣反向代理服務器負責接收客戶端的請求，然后到源服務器上獲取內容，把內容回傳給用戶，并把內容保存到本地，以便日后再收到同樣的資訊請求時，它會把本地快取里的內容直接發給用戶，以減少后端web服務器的壓力，提高回應速度，因此Nginx還具有快取功能，
• 請求的統一控制，包括設定權限、過濾規則等；
• 區分動態和靜態可快取內容；
• 實作負載均衡，內部可以采用多臺服務器來組成服務器集群，外部還是可以采用一個地址訪問；
• 解決Ajax跨域問題；
• 作為真實服務器的緩沖，解決瞬間負載量大的問題；

16.理解restful(Representational State Transfer)

（1）每一個URI代表一種資源；
（2）客戶端和服務器之間，傳遞這種資源的某種表現層；
（3）客戶端通過四個HTTP動詞，對服務器端資源進行操作，實作"表現層狀態轉化"，

RESTful 架構的核心規范與約束：統一介面

分為四個子約束：
1.每個資源都擁有一個資源標識，每個資源的資源標識可以用來唯一地標明該資源
2.訊息的自描述性
3.資源的自描述性，
4.HATEOAS Hypermedia As The Engine Of Application State(超媒體作為應用狀態引擎)
即客戶只可以通過服務端所回傳各結果中所包含的資訊來得到下一步操作所需要的資訊，如到底是向哪個URL發送請求等，也就是說，一個典型的REST服務不需要額外的檔案標示通過哪些URL訪問特定型別的資源，而是通過服務端回傳的回應來標示到底能在該資源上執行什么樣的操作

17.為啥redis zset使用跳躍鏈表而不用紅黑樹實作

• skiplist的復雜度和紅黑樹一樣，而且實作起來更簡單，
• 在并發環境下紅黑樹在插入和洗掉時需要rebalance，性能不如跳表，

18.執行緒狀態

1. 新建(NEW)：新創建了一個執行緒物件，
2. 可運行(RUNNABLE)：執行緒物件創建后，其他執行緒(比如main執行緒）呼叫了該物件的start()方法，該狀態的執行緒位于可運行執行緒池中，等待被執行緒調度選中，獲取cpu 的使用權 ，
3. 運行(RUNNING)：可運行狀態(runnable)的執行緒獲得了cpu 時間片（timeslice） ，執行程式代碼，
4. 阻塞(BLOCKED)：阻塞狀態是指執行緒因為某種原因放棄了cpu 使用權，也即讓出了cpu timeslice，暫時停止運行，直到執行緒進入可運行(runnable)狀態，才有機會再次獲得cpu timeslice 轉到運行(running)狀態，阻塞的情況分三種：

(一). 等待阻塞：運行(running)的執行緒執行o.wait()方法，JVM會把該執行緒放入等待佇列(waitting queue)中，
(二). 同步阻塞：運行(running)的執行緒在獲取物件的同步鎖時，若該同步鎖被別的執行緒占用，則JVM會把該執行緒放入鎖池(lock pool)中，
(三). 其他阻塞：運行(running)的執行緒執行Thread.sleep(long ms)或t.join()方法，或者發出了I/O請求時，JVM會把該執行緒置為阻塞狀態，當sleep()狀態超時、join()等待執行緒終止或者超時、或者I/O處理完畢時，執行緒重新轉入可運行(runnable)狀態

5. 死亡(DEAD)：執行緒run()、main() 方法執行結束，或者因例外退出了run()方法，則該執行緒結束生命周期，死亡的執行緒不可再次復生，

19.jvm記憶體模型

鏈接: JVM記憶體結構和Java記憶體模型別再傻傻分不清了.

20.Spring的IOC和AOP

1.IOC本質

控制反轉IoC（Inversion of Control），是一種設計思想，DI（依賴注入）是實作IoC的一種方法 也有人認為DI只是IoC的另一種說法，沒有IoC的程式中，我們使用面向物件編程，物件的創建與物件間的依賴關系完全硬編碼在程式中，物件的創建由程式自己控制，控制反轉后將物件的創建轉移給第三方，個人認為所謂控制反轉就是：獲得依賴物件的方式反轉了，

采用XML方式配置Bean的時候，Bean的定義資訊是和實作分離的，而采用注解的方式可以把兩者合為一體，Bean的定義資訊直接以注解的形式定義在實作類中，從而達到了零配置的目的，
控制反轉是一種通過描述（XML或注解）并通過第三方去生產或獲取特定物件的方式，在Spring中實作控制反轉的是IoC容器，其實作方法是依賴注入（Dependency Injection，DI），

2.AOP

• 什么是AOP

AOP（Aspect Oriented Programming）意為：面向切面編程，通過預編譯方式和運行期動態代理實作程式功能的統一維護的一種技術，AOP是OOP的延續，是軟體開發中的一個熱點，也是Spring框架中的一個重要內容，是函式式編程的一種衍生范型，利用AOP可以對業務邏輯的各個部分進行隔離，從而使得業務邏輯各部分之間的耦合度降低，提高程式的可重用性，同時提高了開發的效率，

• AOP在Spring中的作用
  提供宣告式事務；允許用戶自定義切面

• 橫切關注點：跨越應用程式多個模塊的方法或功能，即是，與我們業務邏輯無關的，但是我們需要關注的部分，就是橫切關注點，如日志，安全，快取，事務等等…
• 切面（ASPECT）：橫切關注點被模塊化的特殊物件，即，它是一個類，
• 通知（Advice）：切面必須要完成的作業，即，它是類中的一個方法，
• 目標（Target）：被通知物件，
• 代理（Proxy）：向目標物件應用通知之后創建的物件，
• 切入點（PointCut）：切面通知執行的“地點”的定義，
• 連接點（JointPoint）：與切入點匹配的執行點，

21.synchronized和lock區別以及底層原理

區別：
1.首先synchronized是java內置關鍵字，在jvm層面，Lock是個java類；
2.synchronized無法判斷是否獲取鎖的狀態，Lock可以判斷是否獲取到鎖；
3.synchronized會自動釋放鎖(a 執行緒執行完同步代碼會釋放鎖 ；b 執行緒執行程序中發生例外會釋放鎖)，Lock需在finally中手工釋放鎖（unlock()方法釋放鎖），否則容易造成執行緒死鎖；
4.用synchronized關鍵字的兩個執行緒1和執行緒2，如果當前執行緒1獲得鎖，執行緒2執行緒等待，如果執行緒1阻塞，執行緒2則會一直等待下去，而Lock鎖就不一定會等待下去，如果嘗試獲取不到鎖，執行緒可以不用一直等待就結束了；
5.synchronized的鎖可重入、不可中斷、非公平，而Lock鎖可重入、可中斷、可公平（兩者皆可）
6.Lock鎖適合大量同步的代碼的同步問題，synchronized鎖適合代碼少量的同步問題，

底層原理

synchronized:
原子性：保證陳述句塊內是原子的
可見性：通過在unlock前需要將變數同步回主存，其他執行緒需要重新獲取
有序性：一個變數在同一時刻只允許一條執行緒對其操作
方法級的同步是通過方法呼叫和回傳中實作的，方法常量池的ACC_SYNCHRONIZED標志是否為同步方法，如果方法是同步方法，則執行執行緒需要先持有monitor然后執行方法，回傳后釋放，
代碼塊的同步是通過monitorenter和monitorexit實作的，遇到monitorenter試圖獲取monitor物件，如果未加鎖或者已經被自己持有，則鎖計數器+1，執行，遇到monitorexit則鎖計數-1.計數器為0代表鎖釋放，如果獲取monitor物件失敗會進入阻塞，且是可重入的，
1.6前慢的原因：物件內部的監視器鎖是通過底層OS的Mutex實作的，存在用戶態到內核態的切換，成本極高
1.6后的優化：四種鎖狀態 無鎖——偏向鎖——輕量級鎖——重量級鎖，(不可降級)
–
偏向鎖：無實際競爭，且將來只有第一個申請鎖的執行緒會使用鎖，只有一次CAS
鎖物件第一次被獲取時，jvm將物件頭鎖標志位設為01偏向模式，然后通過CAS將執行緒id記錄到物件的markword中，如果成功，該執行緒在以后每次進入該同步塊時，jvm不進行任何操作，如果不是第一次獲取鎖，則判斷偏向執行緒id是否為當前執行緒，是的話就進入同步塊，否則則根據當前偏向的執行緒是否存活，未存活則取消鎖到無鎖狀態，存活則升級為輕量級鎖，
–
輕量級鎖：無實際競爭，多個執行緒交替使用鎖；允許短時間的鎖競爭，申請和釋放需要CAS
輕量級鎖是相對于重量級鎖而言的，使用輕量級鎖時，不需要申請互斥量，而是在當前執行緒堆疊幀中開辟空間Lock Record用來記錄當前物件markword的拷貝，然后將Mark Word中的部分位元組CAS更新指向執行緒堆疊中的Lock Record，如果更新成功，則輕量級鎖獲取成功，記錄鎖狀態為00輕量級鎖；否則，說明已經有執行緒獲得了輕量級鎖，如果指向的是當前執行緒的堆疊幀，則重入代碼塊，否則出現了競爭，會嘗試幾次CAS，如果不行，升級為重量級鎖，標志位11，markword中指標指向重量級鎖，
–
重量級鎖：有實際競爭，且鎖競爭時間長，monitor實作，

Lock: 有三個實作類，ReentrantLock, ReentrantReadWriteLock類中的兩個靜態內部類ReadLock和WriteLock，
底層實作為AQS，
AQS：CLH鎖佇列(雙向鏈表)+state狀態變數，執行緒通過CAS去改變狀態，成功則獲取鎖成功，失敗則進入等待佇列，等待被喚醒，
lock的存盤結構：一個int型別狀態值（用于鎖的狀態變更），一個雙向鏈表（用于存盤等待中的執行緒）
lock獲取鎖的程序：本質上是通過 CAS 來獲取狀態值修改，如果當場沒獲取到，會將該執行緒放在執行緒等待鏈表中，
lock釋放鎖的程序：修改狀態值，調整等待鏈表，
lock()-acquire()-tryAcquire()-未成功獲取鎖-addwaiter()-acquireQueued()
acquireQueued的主要作用是把已經追加到佇列的執行緒節點進行阻塞，但阻塞前又通過tryAccquire重試是否能獲得鎖，如果重試成功能則無需阻塞，直接回傳，

22.Redis持久化

• RDB：RDB 持久化機制，是對 Redis 中的資料執行周期性的持久化，
• AOF：AOF 機制對每條寫入命令作為日志，以 append-only 的模式寫入一個日志檔案中，因為這個模式是只追加的方式，所以沒有任何磁盤尋址的開銷，所以很快，有點像Mysql中的binlog，

兩種方式都可以把Redis記憶體中的資料持久化到磁盤上，然后再將這些資料備份到別的地方去，RDB更適合做冷備，AOF更適合做熱備，比如我杭州的某電商公司有這兩個資料，我備份一份到我杭州的節點，再備份一個到上海的，就算發生無法避免的自然災害，也不會兩個地方都一起掛吧，這災備也就是異地容災，地球毀滅他沒辦法，

RDB優缺點

優點：

他會生成多個資料檔案，每個資料檔案分別都代表了某一時刻Redis里面的資料，這種方式，有沒有覺得很適合做冷備，完整的資料運維設定定時任務，定時同步到遠端的服務器，比如阿里的云服務，這樣一旦線上掛了，你想恢復多少分鐘之前的資料，就去遠端拷貝一份之前的資料就好了，
RDB對Redis的性能影響非常小，是因為在同步資料的時候他只是fork了一個子行程去做持久化的，而且他在資料恢復的時候速度比AOF來的快，

缺點：

RDB都是快照檔案，都是默認五分鐘甚至更久的時間才會生成一次，這意味著你這次同步到下次同步這中間五分鐘的資料都很可能全部丟失掉，AOF則最多丟一秒的資料，資料完整性上高下立判，
還有就是RDB在生成資料快照的時候，如果檔案很大，客戶端可能會暫停幾毫秒甚至幾秒，你公司在做秒殺的時候他剛好在這個時候fork了一個子行程去生成一個大快照，哦豁，出大問題，

AOF優缺點

優點：

上面提到了，RDB五分鐘一次生成快照，但是AOF是一秒一次去通過一個后臺的執行緒fsync操作，那最多丟這一秒的資料，
AOF在對日志檔案進行操作的時候是以append-only的方式去寫的，他只是追加的方式寫資料，自然就少了很多磁盤尋址的開銷了，寫入性能驚人，檔案也不容易破損，

AOF的日志是通過一個叫非常可讀的方式記錄的，這樣的特性就適合做災難性資料誤洗掉的緊急恢復了，比如公司的實習生通過flushall清空了所有的資料，只要這個時候后臺重寫還沒發生，你馬上拷貝一份AOF日志檔案，把最后一條flushall命令刪了就完事了，

缺點：

一樣的資料，AOF檔案比RDB還要大，
AOF開啟后，Redis支持寫的QPS會比RDB支持寫的要低，他不是每秒都要去異步重繪一次日志嘛fsync，當然即使這樣性能還是很高，我記得ElasticSearch也是這樣的，異步重繪快取區的資料去持久化，為啥這么做呢，不直接來一條懟一條呢，那我會告訴你這樣性能可能低到沒辦法用的，大家可以思考下為啥喲，

23.Redis和Memcache區別，優缺點對比

redis和memecache的不同在于：

• 1、存盤方式：
  memecache 把資料全部存在記憶體之中，斷電后會掛掉，資料不能超過記憶體大小
  redis有部份存在硬碟上，這樣能保證資料的持久性，支持資料的持久化（筆者注：有快照和AOF日志兩種持久化方式，在實際應用的時候，要特別注意組態檔快照引數，要不就很有可能服務器頻繁滿載做dump），
• 2、資料支持型別：
  redis在資料支持上要比memecache多的多， 例如 list、set、sorted set、hash 等，
• 3、使用底層模型不同：
  新版本的redis直接自己構建了VM 機制 ，因為一般的系統呼叫系統函式的話，會浪費一定的時間去移動和請求，
• 4、Memcache .處理請求時使用多執行緒異步 IO 的方式，可以合理利用 CPU 多核的優勢，提高性能，與 Memcache不同的是，Redis 采用單執行緒模式處理請求，這樣做的原因有 2 個：一個是因為采用了非阻塞的異步事件處理機制；另一個是快取資料都是記憶體操作 IO 時間不會太長，單執行緒可以避免執行緒背景關系切換產生的代價，
• 5、Redis 提供持久化，主從同步機制，以及 Cluster 集群部署能力，能夠提供高可用服務，

個人總結一下，有持久化需求或者對資料結構和處理有高級要求的應用，選擇redis，其他簡單的key/value存盤，選擇memcache，

24.單執行緒的redis為什么這么快

(一)純記憶體操作
(二)單執行緒操作，避免了頻繁的背景關系切換
(三)采用了非阻塞I/O多路復用機制

25.Redis 為什么是單執行緒的

官方FAQ表示，因為Redis是基于記憶體的操作，CPU不是Redis的瓶頸，Redis的瓶頸最有可能是機器記憶體的大小或者網路帶寬，既然單執行緒容易實作，而且CPU不會成為瓶頸，那就順理成章地采用單執行緒的方案了（畢竟采用多執行緒會有很多麻煩！）Redis利用佇列技術將并發訪問變為串行訪問
1）絕大部分請求是純粹的記憶體操作（非常快速）2）采用單執行緒,避免了不必要的背景關系切換和競爭條件
3）非阻塞IO優點：
1.速度快，因為資料存在記憶體中，類似于HashMap，HashMap的優勢就是查找和操作的時間復雜度都是O(1)
2. 支持豐富資料型別，支持string，list，set，sorted set，hash
3.支持事務，操作都是原子性，所謂的原子性就是對資料的更改要么全部執行，要么全部不執行
4. 豐富的特性：可用于快取，訊息，按key設定過期時間，過期后將會自動洗掉如何解決redis的并發競爭key問題

同時有多個子系統去set一個key，這個時候要注意什么呢？ 不推薦使用redis的事務機制，因為我們的生產環境，基本都是redis集群環境，做了資料分片操作，你一個事務中有涉及到多個key操作的時候，這多個key不一定都存盤在同一個redis-server上，因此，redis的事務機制，十分雞肋，
(1)如果對這個key操作，不要求順序： 準備一個分布式鎖，大家去搶鎖，搶到鎖就做set操作即可
(2)如果對這個key操作，要求順序： 分布式鎖+時間戳， 假設這會系統B先搶到鎖，將key1設定為{valueB 3:05}，接下來系統A搶到鎖，發現自己的valueA的時間戳早于快取中的時間戳，那就不做set操作了，以此類推，
(3) 利用佇列，將set方法變成串行訪問也可以redis遇到高并發，如果保證讀寫key的一致性
對redis的操作都是具有原子性的,是執行緒安全的操作,你不用考慮并發問題,redis內部已經幫你處理好并發的問題了，

26.MySQL中索引失效的常見場景與規避方法

1. where陳述句中包含or時，可能會導致索引失效
2. where陳述句中索引列使用了負向查詢，可能會導致索引失效
3. 索引欄位可以為null，使用is null或is not null時，可能會導致索引失效
4. 在索引列上使用內置函式，一定會導致索引失效
   鏈接: MySQL中索引失效的常見場景與規避方法.