記錄一下個人對于公眾號算法愛好者和程序員小灰的閱讀摘要，目錄如下，

1. B-樹
2. B+樹
3. 跳躍表
4. 動態(tài)規(guī)劃
5. 找缺失數(shù)
6. 判斷2的乘方
7. bitmap算法
8. bloomFilter
9. 決策樹算法
10. A*尋路算法/啟發(fā)式搜索
11. Base64算法
12. 對稱加密 vs 非對稱加密 vs hash
13. MD5算法
14. SHA算法
15. AES算法
16. 紅黑樹
17. HashMap
18. cocurrentHashmap
19. 單例
20. volatile關(guān)鍵字
21. Netty
22. 微服務(wù)架構(gòu)
23. ThreadPoolExecutor

B-樹（B-tree）

• B-樹就是B樹，中間的橫線并不是減號，B減樹的叫法是錯誤的
• 二叉查找樹的時間復(fù)雜度是O(logN)，但是數(shù)據(jù)庫索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量比較大的時候，索引的大小可能就有幾個G。利用索引查詢的時候，一般不能將其全部加載到內(nèi)存，而是逐一加載每一個磁盤頁，這里的磁盤頁對應(yīng)著索引樹的節(jié)點!

存儲樣式

決定磁盤IO次數(shù)的是索引樹的高度（最下面的葉子節(jié)點高度是1，根節(jié)點的深度是1），為了減少磁盤IO的次數(shù)，就需要把原來瘦高的樹結(jié)構(gòu)變得矮胖

二叉查找樹

三階B-樹

每一個節(jié)點最多包含k個孩子，k稱為B-樹的階，k的大小取決于磁盤頁的大小。特征：

• root節(jié)點至少兩個子節(jié)點
• 中間節(jié)點都包含k/2-1_{k-1個元素和k/2}k個子節(jié)點
• 每個葉子節(jié)點都包含k/2-1~k-1個元素
• 所有葉子節(jié)點都位于同一層
• 節(jié)點中元素升序排列
  • 3階，k/2=2?

查詢5的比較，

• 二叉查找樹：9->5（2次）
• B-樹：9->(2,6)->(3,5)（5次）

B-樹在查詢過程中的比較次數(shù)其實不比二叉查找樹少（如查詢5），但是由于加載的該頁節(jié)點數(shù)量多，都在內(nèi)存中，內(nèi)存多次比較耗時遠(yuǎn)小于從二叉查找樹的磁盤加載節(jié)點到內(nèi)存中的耗時

B+樹（B+tree）

B+樹是基于B-樹的一種變體，有著更高的查詢性能

B+樹snapshot

特征：

• 每一個父節(jié)點的元素都出現(xiàn)于子節(jié)點中，是子節(jié)點的最大（或最?。┰?/li>
• 衛(wèi)星數(shù)據(jù)，指的是索引元素所指向的數(shù)據(jù)記錄
  • B-樹中，每個節(jié)點都帶有衛(wèi)星數(shù)據(jù)
  • B+樹中，只有葉子節(jié)點帶有衛(wèi)星數(shù)據(jù)，其余中間節(jié)點僅僅是索引，沒有任何數(shù)據(jù)關(guān)聯(lián)
  • B+樹中間節(jié)點沒有衛(wèi)星數(shù)據(jù)，所以同樣大小的磁盤頁可以容納更多的節(jié)點元素。意味著數(shù)據(jù)量相同的情況下，B+樹比B-樹更矮胖，因此查詢時IO次數(shù)更少
  • B+樹的查詢必須最終查找到葉子節(jié)點，而B-樹只要找到匹配元素即可，無論匹配元素處于根節(jié)點還是中間節(jié)點還是葉子節(jié)點
• 所有葉子節(jié)點形成有序鏈表，便于范圍查詢，查詢性能穩(wěn)定

跳躍表（skiplist）

需求：搭建一個拍賣，拍賣商品幾十萬件對應(yīng)數(shù)據(jù)庫商品表的幾十萬條記錄。

方案：全量查詢排序的處理？一般情況是先拿query去數(shù)據(jù)庫index找到對應(yīng)的doc，如果在master的時候?qū)⒉煌瑂lave的docs merge起來再sort，最后又mater返回sorted result給client。

拍賣行商品列表是線性的，最容易表達(dá)線性結(jié)構(gòu)的自然是數(shù)組和鏈表，但是它們在插入新商品的時候，存在性能問題，

• 數(shù)組：

1. 查位，查找新商品的插入位置，可以用二分查找法length/2, O(1)的隨機(jī)查詢性能，O(logN)
2. 插入，原數(shù)組中大于新商品的都要右移，給新元素騰出空位，O(N)
3. 總復(fù)雜度O(N)+O(logN)

• 鏈表：

1. 查位，無法使用二分查找，因為length不知道，只能新商品與原鏈表中的節(jié)點逐一比較大小來確定位置，O(N)
2. 插入，鏈表插入是O(1)
3. 總體復(fù)雜度O(N)

跳躍表是一種基于有序鏈表的擴(kuò)展，簡稱跳表。
跳躍表插入節(jié)點的流程：

1. 新節(jié)點與各層索引節(jié)點逐一比較，確定原鏈表的插入位置，O(logN)
2. 把新節(jié)點插入到原鏈表O(1)
3. 利用拋硬幣的隨機(jī)方式，決定新節(jié)點是否提升為上一級索引O(logN)
4. 總體時間復(fù)雜度O(logN)，空間復(fù)雜度O(N)

skiplist1

skiplist2

skiplist3

跳躍表利用了空間換時間策略。

應(yīng)用場景：

• redis當(dāng)中的sorted-set/lucene index就是使用了跳躍表這種有序鏈表（memory，跳躍表簡化了集合插入復(fù)雜度）
• 而在關(guān)系型數(shù)據(jù)庫中卻是使用B+樹這種數(shù)據(jù)結(jié)構(gòu)來維護(hù)有序的記錄集合（disk，B+樹減少了磁盤IO次數(shù)）

動態(tài)規(guī)劃（dynamic programming）

問題：需要爬上第十臺階。一步只能走1個臺階或2個臺階，那么還差一步就到第十個臺階，那么會出現(xiàn)多少種情況？
F(10) = F(9) + F(8) (第一種是從9級到10級，第二種是從8級到10級）
F(N) = F(N-1) + F(N-2) (N >2)，狀態(tài)轉(zhuǎn)移方程，最優(yōu)子結(jié)構(gòu)，
F(2) = 2，邊界
F(1) = 1，邊界

解法：

1. 使用遞歸方式，但是遞歸方式N越大，重復(fù)計算部分就越多，O(2^N)
2. 備忘錄算法replay，記錄每次F(N)的結(jié)果，先找Map里的，沒有再遞歸計算，O(N), O(N)
3. 因為F(N)只需要保留F(N-1)和F(N-2)，只需要2個狀態(tài)，而備忘錄算法是保留全部狀態(tài)，所以既不需要遞歸，也不需要備忘錄算法，直接遞推最簡便，O(N), O(1)

找缺失數(shù)

題目：給出一個包含 0 .. N 中 N 個數(shù)的序列，找出0 .. N 中沒有出現(xiàn)在序列中的那個數(shù)。
解法：異或（0^1=1,11=0,0^0=0,0N=N)
result = 0^....N^Array[0]....^Array[N-1]

判斷2的乘方

特征：

1. 如果一個整數(shù)是2的乘方，那么它轉(zhuǎn)換成2進(jìn)制的時候，只有最高位是1（8 -> 1000)
2. 如果二進(jìn)制結(jié)果減去1，那么就是全1的情況（ 8-1=7 -> 111)
3. 那么N ^ (N-1) -> 0 （N是2的乘方數(shù)）
4. 一般情況，N^N-1能夠消除最右邊的1 （7⁶⁼¹¹¹110=110)

bitmap算法

背景：通過用戶標(biāo)簽，實現(xiàn)多樣的用戶群體統(tǒng)計。比如統(tǒng)計用戶的男女比例，統(tǒng)計喜歡旅游的用戶數(shù)量等。

設(shè)計：mysql表結(jié)構(gòu)

mysql table snapshot

要想統(tǒng)計所有90后的程序員該怎么做呢？
Select count（distinct Name） as 用戶數(shù) from table where age = '90后' and Occupation = '程序員'；
要想統(tǒng)計所有使用蘋果手機(jī)或者00后的用戶總合該怎么做？
Select count（distinct Name） as 用戶數(shù) from table where Phone = '蘋果' or age = '00后'；

問題：
隨著標(biāo)簽越來越多，表結(jié)構(gòu)的列數(shù)量就越來越多，同時sql語句的where拼接也越來越臃腫。

BITMAP: 每個標(biāo)簽一個bitmap數(shù)組，數(shù)組長度表示為用戶數(shù)，bitmap數(shù)組的數(shù)量表示為有多少類標(biāo)簽

1. 建立用戶名與用戶id的映射（bitmap遍歷不能用string，只能是bitmap數(shù)組的第幾位）

映射

2. 讓每一類標(biāo)簽存儲包含此標(biāo)簽的所有用戶ID（也可以是全部用戶，只是第幾位用戶的數(shù)組posi為0而已），每一類標(biāo)簽都是一個獨立的bitmap

拆映射為標(biāo)簽

3. 最后實現(xiàn)

implementation

4. 例子

• 如何查找使用蘋果手機(jī)的程序員用戶？

example1

• 如何查找所有男性或者00后的用戶？

example2

優(yōu)勢：

• 非常節(jié)約存儲空間
• 高性能的位運(yùn)算操作（&， |，^）

劣勢：

• 不支持非運(yùn)算（！）。全量異或可以解決這個問題

開源方案：
java bitSet
google EWAHCompressedBitmap

bitmap進(jìn)階
RLE游程編碼

布隆算法bloomFilter

一種以bitMap集合為基礎(chǔ)的去重算法。
如果說爬蟲，因為爬取得是網(wǎng)頁URL，String類型，與數(shù)字類型不一樣，因為不同string，hashCode可能相同，所有不能直接使用單個bitmap就來判斷2個url是否相同。

映射流程：（bloomFilter只需要一個bitMap，但是一個key多次要映射）

1. 創(chuàng)建一個空的bitmap集合
2. 把第一個URL按照三種hash算法，分別生成三個不同的hash值
3. 分別判斷key1的三個hash值對應(yīng)的bitmap位置是否為1，只要全部都為1的情況，才認(rèn)為key1已經(jīng)存在了

誤判幾率：

1. 雖然bloomFilter極力降低了hash沖突的幾率，但是仍存在一定的誤判率
2. 可以在單key hash次數(shù)與hash長度，沖突率之間做取舍
3. 因為bloomFilter只用了一個bitmap，如果單個key的每次hash都對應(yīng)一個bitmap，那么這樣的方式就會占用翻倍的空間，反而不如用hashset好
4. 如果想完全杜絕誤判，可以增加一個白名單機(jī)制

決策樹算法

樹是一種很重要的數(shù)據(jù)結(jié)構(gòu)，可以為我們縮小問題規(guī)模，實現(xiàn)高效的查找。
背景：猜人名游戲。游戲中，出題者寫下一個明星的名字，其他人需要猜出這個人是誰。當(dāng)然，如果游戲規(guī)則僅此而已的話，幾乎是無法猜出來的，因為問題的規(guī)模太大了。為了降低游戲的難度，答題者可以向出題者問問題，而出題者必須準(zhǔn)確回答是或者否，答題者依據(jù)回答提出下一個問題，如果能夠在指定次數(shù)內(nèi)確定謎底，即為勝出，

• 是男的嗎？Y
• 是亞洲人嗎？Y
• 是中國人嗎？N
• 是印度人嗎？Y
• ……

decision tree snapshot

算法思想：

1. 每次選擇其中一個特征對樣本集合進(jìn)行分類
2. 對分類后的所有子集遞歸進(jìn)行步驟1

最重要的是第一步，即需要想出一個重要的策略，即選擇什么樣的特征可以實現(xiàn)最好的分類效果。使用純凈度來評價分類效果，熵來量化純凈度。
熵表示一個系統(tǒng)的混亂程度，熵越大，說明數(shù)據(jù)集純凈度越低；當(dāng)數(shù)據(jù)集都是同一個類別的時候，此時熵是0。目標(biāo)就是使得熵最低。

6組樣本

一共6組樣本，每一組樣本包含4個特征，分別是年齡段，學(xué)歷，收入，婚姻狀況，最后一列數(shù)所屬分類，代表該組/用戶是否購買了該產(chǎn)品。使用這些樣本去訓(xùn)練一顆決策樹如下：

6組樣本的決策樹

使用上述決策樹來判斷一個新晉用戶（需要將該用戶的4個特征都拿到）是否會購買該產(chǎn)品。

A*尋路算法/啟發(fā)式搜索

前提：
OpenList，可達(dá)格子
CloseList，已達(dá)到格子
F=G+H，G起點走到當(dāng)前格的成本；H當(dāng)前格到目標(biāo)格的距離，不考慮障礙物。

a star algorithm snapshot

起點(1,2)，終點(5,2)。過程，

1. 計算當(dāng)期點的可達(dá)點
2. Fmin是(2,2)，所以將其加入移出openList，加入closeList
3. 看當(dāng)前格子(2,2)的上下左右，是否在openlist當(dāng)中，如果不在，加入openList，并計算F

Base64算法

文本協(xié)議(http)
二進(jìn)制協(xié)議（pb, thrift）

字節(jié)碼byte是8bit，base64可以將原來ASCII字符打印成6bit字符。8，6最小公倍數(shù)24。意味著可以用4個base64字符(TWFu)來表達(dá)3個傳統(tǒng)的8bit字符(Man)。

base64 encode

base64索引表（0-A,46-u,19-T,20-U）

對稱加密 vs 非對稱加密 vs hash

對稱加密，一方通過密鑰將信息加密后，把密文傳給另一方，另一方通過這個相同的密鑰將密文解密，轉(zhuǎn)換成可以理解的明文，這類算法在加密和解密時使用相同的密鑰，這組密鑰成為在兩個或多個成員間的共同秘密，
指加密和解密使用相同密鑰的加密算法

明文 <-> 密鑰 <-> 密文
常見的對稱加密算法有DES、3DES、Blowfish、IDEA、RC4、RC5、RC6和AES

非對稱加密，首先要有一對key，一個被稱為private key私鑰，一個成為public key公鑰，然后可以把你的public key分發(fā)給想給你傳密文的用戶，然后這些用戶使用該public key加密過的密文，只有使用你的private key才能解密。也就是說，只要你自己保存好你的private key，就能確保，別人想給你發(fā)的密文不被破解，所以你不用擔(dān)心盟友的密鑰被盜，
指加密和解密使用不同密鑰的加密算法，也稱為公私鑰加密

常見的非對稱加密算法有：RSA、ECC（移動設(shè)備用）、Diffie-Hellman、El Gamal、DSA（數(shù)字簽名用）
SSH的加密原理中，使用到了RSA非對稱加密算法

hash算法，Hash算法特別的地方在于它是一種單向算法，用戶可以通過Hash算法對目標(biāo)信息生成一段特定長度的唯一的Hash值，卻不能通過這個Hash值重新獲得目標(biāo)信息。因此Hash算法常用在不可還原的密碼存儲、信息完整性校驗等。

常見的Hash算法有MD2、MD4、MD5、HAVAL、SHA

消息安全傳輸
用戶甲乙之間先建立安全通信信道，再開始傳輸具體消息，

1. 甲生成pk1(public key，公鑰)和sk1(secret key，私鑰)
2. 甲在Internet中傳輸pk1給乙（黑客可以截取到pk）
3. 乙接收到pk1后，乙生成非對稱加密(pk2, sk2)
4. 乙用pk1對pk2加密，并傳給甲（pk1加密的只有sk1能加密）（黑客可以截取pk1加密過的pk2）
5. 甲收到pk1加密過的pk2后，用sk1解密，得到pk2
6. 甲用pk2對對稱密鑰keyX加密，然后傳給乙（可截?。?/li>
7. 乙用sk2解密得到keyX
8. 后續(xù)甲乙雙方就基于keyX來通信（先非對稱加密，再對稱加密）

一次一密安全傳輸

MD5算法, message digest algorithm

就是信息摘要的一種實現(xiàn)，它可以從任意長度的明文字符串生成128位的哈希值。

生成：

md5 generation

傳輸：

md5 transmission

傳輸內(nèi)容是（拼接明文+MD5(拼接明文)）
MD5破解
一般不需要原文一致，而是MD5值一致即可。

設(shè)MD5的哈希函數(shù)是H（X），那么：
H(A) = M
H(B) = M
任意一個B即為破解結(jié)果。

B有可能等于A，也可能不等于A。即殊途同歸，

1. 暴力枚舉法：復(fù)雜度，假設(shè)只考慮大小寫和數(shù)字，每一位有62種可能，那么8位密碼的排列組合就是62^8（時間換空間）
2. 字典法：62^{8種可能性，每一對映射占xx=(128+8chars)位。那么需要62}8 * xx bit
3. 彩虹表：函數(shù)族Rk(k=1,2,3,4,..)將hash密文空間映射回明文的字符空間

彩虹表例子，

• qshud(明文) -> e978c6b019ac22a3fd05b14d36621852(32位MD5密文），最簡單的轉(zhuǎn)化處理就是直接截取第一個字符e；
• e -> e1671797c52e15f763380b45e841ec32，截取前兩位；
• e1 -> cd3dc8b6cffb41e4163dcbd857ca87da，截取前三位
• cd3 -> XXX，假設(shè)截取到前k位(k=8)
• XXX -> 5626cf5e6f1093c2840a16512f62c3b5
• 5626cf5e
• 最后存儲字符串qshud和5626cf5e
• 下一步就是查表過程（從中間鏈的倒數(shù)開始遍歷）

SHA算法

哈希摘要算法
和MD5算法類似，SHA(secure hash algorithm)也是一種生成信息摘要的算法。
SHA-1,SHA-2,SHA-256，第一位數(shù)字大版本號，第二位數(shù)字是子版本號。
SHA-1摘要長度160bit；而MD5的摘要長度是128bit，但MD5生成摘要的性能比SHA-1好。
SHA-256：可以生成長度256bit的信息摘要。

AES算法，advanced encryption standard

對稱加密算法

• 摘要算法是不可逆的，它的主要作用是對信息一致性和完整性的校驗
• 對稱加密算法是可逆的，它的主要作用是保證私密信息不被泄露

AES128, AES192, AES256，指的是AES算法對不同長度密鑰的使用。特點，

• 明文分組，AES并不是將整個明文全部加密成一整段密文，而是將明文拆成一個個獨立的明文塊，每一個明文塊長度128bit，逐一加密后的密文塊最后拼接在一起，成為AES加密結(jié)果
• 填充方式，如果最后一塊明文塊不夠，需要將其填充為128/192/256bit
  • Nopadding，不做任何填充，但是要求明文必須是16字節(jié)的整數(shù)倍
  • PKCS5Padding（默認(rèn)）
  • ISO10126Padding
• 工作模式，表現(xiàn)在把明文塊加密成密文塊的處理過程中
  • CBC模式
  • ECB模式（默認(rèn)）
  • CTR模式
  • CFB模式
  • OFB模式

AES

java code example

其中，

1. kgen.init(128, new...)，第一個參數(shù)決定了分組長度是128bit
2. Cipher.getInstance("AES/CBC/NoPadding")，決定了填充方式是NoPadding，工作模式是CBC

AES加密不是一次就將明文變成密文的，而是先后經(jīng)過很多輪加密，1+N+1輪，

1. 初始輪 Initial round，1次
2. 普通輪 rounds，N次
3. 最終輪 final round，1次

AES的分組長度對應(yīng)的輪數(shù)如下，

1. AES128，10輪，N=8
2. AES192，12輪
3. AES256，14輪

不同截斷的round有不同的處理步驟，
初始輪，

1. 加輪密鑰 addRoundKey

普通輪，

1. 字節(jié)代替 subBytes，就是把明文塊的每一個字節(jié)都替代成另外一個字節(jié)
2. 行移位 shiftRows，每行左移X個字節(jié)
3. 列混淆 mixColumns，明文塊矩陣與修補(bǔ)矩陣相乘
4. 加輪密鑰，這是唯一用到密鑰的一步，明文塊與密鑰異或

最終輪，

1. 字節(jié)代替
2. 行移位
3. 加輪密鑰

解密過程與加密過程相反：最終輪 -> 普通輪 -> 初始輪

工作模式，ECB明文塊之間沒有聯(lián)系，完全并行；CBC模式，某一個明文塊需要上一個明文塊作“加鹽”處理，內(nèi)部IV變量為初始鹽

AES ori

AES+salt

紅黑樹

根節(jié)點的樹深度（樹高度）=1
二叉查找樹（binary search tree）特征，

1. 左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值
2. 右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值
3. 左、右子樹也分別為二叉排序樹

二叉查找樹BST snapshot1

BST snapshot2

紅黑樹（red black tree）是BST的自平衡優(yōu)化，改善了BST的樹高落差，除了符合BST的基本特性外，它還要符合以下特征，

1. 節(jié)點是紅色或者黑色
2. 根節(jié)點一定是黑色
3. 每個葉子節(jié)點都是黑色的空節(jié)點
4. 每個紅色節(jié)點的兩個子節(jié)點都是黑色的（即每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）
5. 對于任一節(jié)點而言，其到葉節(jié)點的每一條路徑都包含相同數(shù)目的黑結(jié)點

由于有了上面的3+5點規(guī)則，才保證了紅黑樹的自平衡。紅黑樹從根節(jié)點到葉子節(jié)點的最長路徑不會超過最短路徑的2倍。當(dāng)插入或者刪除節(jié)點的時候，紅黑樹的規(guī)則很有可能被打破。這時候就需要作出一些調(diào)整，來繼續(xù)維持3+5規(guī)則，這些調(diào)整主要包括變色和旋轉(zhuǎn)，

1. 變色，紅黑互換
2. 左旋，要符合BST的規(guī)則，就很容易理解b這個節(jié)點該放在哪個位置，因為Y要上來，但是x < b < y，所以b要在x的右節(jié)點，x又要在y的左節(jié)點。
3. 右旋，y < c < x

左旋

右旋

RBT before adjust

RBT insert 21 and adjust

HashMap

HashMap是一個用于存儲Key-Value pair 鍵值對的集合，每一個鍵值對pairs也叫Entry。這個Entry分散存儲在一個數(shù)組當(dāng)中，這個數(shù)組就是HashMap的主干。

hashmap snapshot1

index = Hash("apple") = 2

hashmap snapshot2

如果下一個index = Hash("banana") = 2，那么就發(fā)生碰撞，可以用鏈表來解決，鏈表頭節(jié)點始終是最晚進(jìn)入的Entry。

hashmap snapshot3

put(k, v), 存儲某個(key, value)時，調(diào)用Entry(k, v)的hashcode計算hash從而得到index，然后將Entry放入其中。

get(key), 查找某個key的value，步驟如下，

1. key hash得到index，array(index)來O(1)定位到鏈表
2. 線性查找鏈表，比較Entry(key, value)，keyInLink.equals(search_key)?，如果equal返回該Entry(search_key, value)的value，否則為null。碰撞鏈表查找性能O(N)，若為樹就O(logN)
   • 在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認(rèn)是8)，則使用紅黑樹來替換鏈表，從而提高速度

為什么hashMap的默認(rèn)初始長度是16，并且每次自動擴(kuò)展或是手動初始化時，長度必須是2的冪？
選擇2的冪，是為了服務(wù)于從key映射到index的hash算法。要求一個盡量均勻的hash函數(shù)，減少key的index碰撞。
index = HashCode（Key） & （hashMap_Length - 1）

2的冪

看到hashMap_Length為2的冪，那么其低位全為1，就可以都將hashCode對應(yīng)的低位信息都保留，從而增加index distinct count。這是后碰撞機(jī)率就完全依賴于HashCode自身的分布均勻性了。

summary

cocurrentHashmap

在jdk8之前，concurrentHashmap使用了分段鎖segment來實現(xiàn)并發(fā)。
concurrentHashmap當(dāng)中每個segment各自持有一把鎖，在保證線程安全的同時降低了鎖的粒度，讓并發(fā)操作效果更高。
讀寫過程，
Get方法，

1. 為輸入的key做hash運(yùn)算，得到hash值
2. 通過hash值，定位到對應(yīng)的segment對象
3. 再次通過hash值，定位到segment當(dāng)中數(shù)組的具體位置

Put方法，

1. 為輸入的key做hash運(yùn)算，得到hash值
2. 通過hash值，定位到對應(yīng)的segment對象
3. 獲取可重入鎖
4. 再次通過hash值，定位到segment當(dāng)中數(shù)組的具體位置
5. 插入或覆蓋hashEntry對象
6. 釋放鎖

在讀寫時都需要二次定位。首先定位到segment，之后定位到segment內(nèi)的具體數(shù)組下標(biāo)。

返回concurrentHashmap的總元素數(shù)量的size()函數(shù)，大體邏輯，

1. 遍歷所有segment
2. 把segment的元素數(shù)量累加起來，S1
3. 把segment的修改次數(shù)累加起來，S2
4. 判斷所有segment的總修改次數(shù)是否大于上一次的總修改次數(shù)
   1. 如果大于，說明統(tǒng)計過程中有修改，重新統(tǒng)計，嘗試次數(shù)+1
   2. 如果沒有修改，統(tǒng)計結(jié)束
5. 如果嘗試次數(shù)超過閾值(=2)，則對每一個segment加鎖，再重新統(tǒng)計
6. 再次判斷所有segment的總修改次數(shù)是否大于上一次的總修改次數(shù)。由于已經(jīng)加鎖，次數(shù)一定和上次相等
7. 釋放鎖，統(tǒng)計結(jié)束

這里引入嘗試次數(shù)，這種思想和樂觀鎖悲觀鎖的思想如出一轍。為了盡量不要鎖住所有segment，首次樂觀地假設(shè)求size過程中不會有修改。當(dāng)嘗試了一定次數(shù)之后，才無奈轉(zhuǎn)為悲觀鎖，鎖住所有segment來保證強(qiáng)一致性。
在jdk8之后，廢棄了segment改變，改為由CAS原理來實現(xiàn)，直接使用一個大數(shù)組，在發(fā)生碰撞的時候，產(chǎn)生鏈表，如果鏈表長度超過了閾值(=8)，則將鏈表轉(zhuǎn)換為紅黑樹（尋址時間復(fù)雜度有O(N)降到O(logN)了，原作者認(rèn)為引入紅黑樹之后，即使hash沖突比較嚴(yán)重，尋址效率也足夠高）。

單例

1. 雙重鎖檢測

public class Singleton {

    private volatile static Singleton instance = null; //單例對象

    private Singleton() { //構(gòu)造函數(shù),私有
    }

    public static Singleton getInstance() {
        if (instance == null) { //雙重檢測機(jī)制
            synchronized (Singleton.class) { //同步鎖,要類級別的,不能是對象鎖
                if (instance == null) { //雙重檢測機(jī)制
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

2. 靜態(tài)內(nèi)部類

public class Singleton {

    private Singleton() {
    }

    public static Singleton getInstance() {
        return LazyHolder.instance;
    }

    private static class LazyHolder {

        private static final Singleton instance = new Singleton();
    }

}

3. 枚舉

public enum Singleton {
    INSTANCE;
}

4. scala object

object Singleton {
  private val instance = “I am singleton"

  def getInstance() = {
    instance
  }
}

volatile關(guān)鍵字

volatile如字面意思，不穩(wěn)定的，變化無常的，所以需要被時刻關(guān)注著。
其大概作用，

1. 保證一個變量在線程之間的可見性，表現(xiàn)為即時更新變量值到主內(nèi)存?；贑PU的內(nèi)存屏障指令是可見性的保證，happen-before原則
2. 阻止編譯時和運(yùn)行時的指令重排。編譯時依靠內(nèi)存屏障來阻止JVM編譯器對指令的重排；運(yùn)行時依靠CPU屏障指令來阻止重排
3. 64位long/double安全讀取，因為 Java 中讀取 long 類型變量不是原子的

線程間的可見性

指令重排

• threadlocal，一個關(guān)于創(chuàng)建線程局部變量的類
• Atomic原子類
• ConcurrentHashMap，鎖，jdk7基于segment，jdk8基于CAS

Netty

遠(yuǎn)程過程調(diào)用，

1. http協(xié)議（簡單明了，但是很多頭信息）
2. socket（偏底層，要注意高并發(fā)）

   1. 阻塞IO，blocking io，一個線程對應(yīng)一個socket

      
      
      BIO

   2. 非阻塞IO，non-blocking io，多路復(fù)用的思路，一個線程/選擇器selector去處理多個socket

      
      
      NIO

Netty本身是一個基于java NIO的網(wǎng)絡(luò)框架，封裝了java NIO的復(fù)雜底層細(xì)節(jié)，提供簡單易用的抽象概念來編程。
Netty是一個半成品，不能開箱即用，必須在其基礎(chǔ)之上做點定制，利用它開發(fā)出自己的應(yīng)用程序，然后才能運(yùn)行（類似spring那樣）。grpc，dubbo這些rpc框架的底層用的就是Netty

微服務(wù)架構(gòu)

單體架構(gòu)優(yōu)點，

1. 便于管理，所有代碼都在一個項目當(dāng)中

但是當(dāng)其產(chǎn)品規(guī)模越來越大時，缺點就更為突出，

1. 項目過于臃腫，當(dāng)大大小小的功能模塊都集中在同一項目的時候，整個項目必然會變得臃腫，讓開發(fā)者難以維護(hù)
2. 資源無法隔離，整個單體系統(tǒng)的各個功能模塊都依賴于同樣的數(shù)據(jù)庫、內(nèi)存、IO等資源，一旦某個功能模塊對資源使用不當(dāng)，整個系統(tǒng)的其他功能都會被拖垮
3. 無法靈活擴(kuò)展，當(dāng)系統(tǒng)的訪問量越來越大的時候，單體系統(tǒng)固然可以進(jìn)行水平擴(kuò)展（多個實例），部署在多臺機(jī)器上組成集群。但是這種擴(kuò)展并非靈活的擴(kuò)展。比如我們現(xiàn)在的性能瓶頸是支付模塊，希望只針對支付模塊做水平擴(kuò)展，這一點在單體系統(tǒng)是做不到的（因為部署是整個項目的部署，而整個項目不僅僅包含支付模塊）

單體架構(gòu)

單體架構(gòu)水平擴(kuò)展

微服務(wù)架構(gòu)是為了解決上述臃腫單項目問題，將單項目拆開成多個獨立的服務(wù)，然后各自調(diào)用，特點如下，

1. 可靈活擴(kuò)展，比如根據(jù)每個服務(wù)的吞吐量不同，支付服務(wù)需要部署20臺機(jī)器，用戶服務(wù)需要部署30臺機(jī)器，而商品服務(wù)只需要部署10臺機(jī)器。這種靈活部署只有微服務(wù)架構(gòu)才能實現(xiàn)

單體架構(gòu) vs. 微服務(wù)架構(gòu)

2. 資源的有效隔離，每一個微服務(wù)擁有獨立的數(shù)據(jù)源，假如微服務(wù)A想要讀寫微服務(wù)B的數(shù)據(jù)庫，只能調(diào)用微服務(wù)B對外暴露的接口來完成。這樣有效避免了服務(wù)之間爭用數(shù)據(jù)庫和緩存資源所帶來的問題

各個模塊調(diào)用各自的DB

3. 團(tuán)隊組織架構(gòu)的調(diào)整

單體架構(gòu)組織架構(gòu)

微服務(wù)組織架構(gòu)

4. 拆分出很多業(yè)務(wù)模塊，增加了開發(fā)和測試復(fù)雜度
5. 難以保證不同服務(wù)之間的數(shù)據(jù)一致性，所引入的分布式事務(wù)和異步補(bǔ)償機(jī)制可以緩解一致性問題，但也增加了設(shè)計和開發(fā)難度

總而言之，微服務(wù)架構(gòu)的核心思想是，一個應(yīng)用是由多個小的、相互獨立的、微服務(wù)組成，這些服務(wù)運(yùn)行在自己的進(jìn)程中，開發(fā)和發(fā)布都沒有依賴。不同服務(wù)通過一些輕量級交互機(jī)制來通信，例如 RPC、HTTP 等，服務(wù)可獨立擴(kuò)展伸縮，每個服務(wù)定義了明確的邊界，不同的服務(wù)甚至可以采用不同的編程語言來實現(xiàn)，由獨立的團(tuán)隊來維護(hù)。

SOA vs 微服務(wù)

• SOA，粗粒度，系統(tǒng)之間的服務(wù)調(diào)用。合，把很多系統(tǒng)串聯(lián)在一起
• 微服務(wù)，細(xì)粒度，按業(yè)務(wù)拆分成不同的服務(wù)。拆，把很多功能模塊拆分出來提供服務(wù)

ThreadPoolExecutor

線程池處理流程 From moonandstar08

//構(gòu)造函數(shù)
public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler) 

工作規(guī)則

1. 如果curPoolSize < corePoolSize，則創(chuàng)建新線程執(zhí)行任務(wù)
2. 如果curPoolSize > corePoolSize，且等待隊列未滿，則進(jìn)入等待隊列
3. 如果curPoolSize > corePoolSize，且等待隊列已滿，且小于maximumPoolSize，則創(chuàng)建新線程執(zhí)行任務(wù)
4. 如果curPoolSize > corePoolSize，且等待隊列已滿，且大于maximumPoolSize，則調(diào)用飽和策略來處理該任務(wù)
5. 線程池里的每個線程執(zhí)行完任務(wù)后不會立刻退出，而是會去檢查下等待隊列里是否還有線程任務(wù)需要執(zhí)行，如果在keepAliveTime里等不到新的任務(wù)了，那么線程就會退出，直至baseline = corePoolSize條

線程池具體實現(xiàn)

• FixedThreadPool

//可重用固定線程數(shù)的線程池，超出的線程會在隊列中等待
public static ExecutorService newFixedThreadPool(int nThreads) {
        return new ThreadPoolExecutor(nThreads, nThreads,
                                      0L, TimeUnit.MILLISECONDS,
                                      new LinkedBlockingQueue<Runnable>());
    }
//其corePoolSize == maximumPoolSize，即不設(shè)置非核心線程
//keepAliveTime為0L表示多余的線程會立刻終止

• CachedThreadPool

//無窮大的線程池
public static ExecutorService newCachedThreadPool() {
        return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                      60L, TimeUnit.SECONDS,
                                      new SynchronousQueue<Runnable>());
    }
//corePoolSize是0，maximumPoolSize是Int的最大值，也就是說CachedThreadPool沒有核心線程，全部都是非核心線程，并且沒有上限
//keepAliveTime是60秒，就是說空閑線程等待新任務(wù)60秒，超時則銷毀

• SingleThreadExecutor

//單個線程工作的線程池
public static ExecutorService newSingleThreadExecutor() {
        return new FinalizableDelegatedExecutorService
            (new ThreadPoolExecutor(1, 1,
                                    0L, TimeUnit.MILLISECONDS,
                                    new LinkedBlockingQueue<Runnable>()));
    }
//按入隊順序逐一進(jìn)行任務(wù)

• ScheduledThreadPool

//定時或者周期性運(yùn)行任務(wù)的線程池
public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) {
        return new ScheduledThreadPoolExecutor(corePoolSize);
    }

public ScheduledThreadPoolExecutor(int corePoolSize) {
        super(corePoolSize, Integer.MAX_VALUE,
              DEFAULT_KEEPALIVE_MILLIS, MILLISECONDS,
              new DelayedWorkQueue());
    }
//等待隊列DelayedWorkQueue是無界的，所以maximumPoolSize參數(shù)無效