記錄一下個(gè)人對(duì)于公眾號(hào)算法愛(ài)好者和程序員小灰的閱讀摘要衰齐，目錄如下僵控，

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

B-樹(shù)（B-tree）

• B-樹(shù)就是B樹(shù)霜运，中間的橫線并不是減號(hào)勾邦，B減樹(shù)的叫法是錯(cuò)誤的
• 二叉查找樹(shù)的時(shí)間復(fù)雜度是O(logN)道川，但是數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤上的午衰，當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引的大小可能就有幾個(gè)G冒萄。利用索引查詢的時(shí)候臊岸，一般不能將其全部加載到內(nèi)存，而是逐一加載每一個(gè)磁盤頁(yè)尊流，這里的磁盤頁(yè)對(duì)應(yīng)著索引樹(shù)的節(jié)點(diǎn)!

存儲(chǔ)樣式

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

二叉查找樹(shù)

三階B-樹(shù)

每一個(gè)節(jié)點(diǎn)最多包含k個(gè)孩子逻住，k稱為B-樹(shù)的階，k的大小取決于磁盤頁(yè)的大小迎献。特征：

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

查詢5的比較，

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

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

B+樹(shù)（B+tree）

B+樹(shù)是基于B-樹(shù)的一種變體践盼，有著更高的查詢性能

B+樹(shù)snapshot

特征：

• 每一個(gè)父節(jié)點(diǎn)的元素都出現(xiàn)于子節(jié)點(diǎn)中鸦采，是子節(jié)點(diǎn)的最大（或最小）元素
• 衛(wèi)星數(shù)據(jù)咕幻，指的是索引元素所指向的數(shù)據(jù)記錄
  • B-樹(shù)中渔伯，每個(gè)節(jié)點(diǎn)都帶有衛(wèi)星數(shù)據(jù)
  • B+樹(shù)中，只有葉子節(jié)點(diǎn)帶有衛(wèi)星數(shù)據(jù)肄程，其余中間節(jié)點(diǎn)僅僅是索引锣吼，沒(méi)有任何數(shù)據(jù)關(guān)聯(lián)
  • B+樹(shù)中間節(jié)點(diǎn)沒(méi)有衛(wèi)星數(shù)據(jù)，所以同樣大小的磁盤頁(yè)可以容納更多的節(jié)點(diǎn)元素蓝厌。意味著數(shù)據(jù)量相同的情況下玄叠，B+樹(shù)比B-樹(shù)更矮胖，因此查詢時(shí)IO次數(shù)更少
  • B+樹(shù)的查詢必須最終查找到葉子節(jié)點(diǎn)拓提，而B(niǎo)-樹(shù)只要找到匹配元素即可读恃，無(wú)論匹配元素處于根節(jié)點(diǎn)還是中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)
• 所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢，查詢性能穩(wěn)定

跳躍表（skiplist）

需求：搭建一個(gè)拍賣寺惫，拍賣商品幾十萬(wàn)件對(duì)應(yīng)數(shù)據(jù)庫(kù)商品表的幾十萬(wàn)條記錄疹吃。

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

拍賣行商品列表是線性的艇肴，最容易表達(dá)線性結(jié)構(gòu)的自然是數(shù)組和鏈表腔呜，但是它們?cè)诓迦胄律唐返臅r(shí)候，存在性能問(wèn)題再悼，

• 數(shù)組：

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

• 鏈表：

1. 查位，無(wú)法使用二分查找泳炉，因?yàn)閘ength不知道憾筏，只能新商品與原鏈表中的節(jié)點(diǎn)逐一比較大小來(lái)確定位置，O(N)
2. 插入花鹅，鏈表插入是O(1)
3. 總體復(fù)雜度O(N)

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

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

skiplist1

skiplist2

skiplist3

跳躍表利用了空間換時(shí)間策略黄痪。

應(yīng)用場(chǎng)景：

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

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

問(wèn)題：需要爬上第十臺(tái)階桅打。一步只能走1個(gè)臺(tái)階或2個(gè)臺(tái)階，那么還差一步就到第十個(gè)臺(tái)階愈案，那么會(huì)出現(xiàn)多少種情況挺尾？
F(10) = F(9) + F(8) (第一種是從9級(jí)到10級(jí)，第二種是從8級(jí)到10級(jí)）
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ù)計(jì)算部分就越多锰蓬，O(2^N)
2. 備忘錄算法replay幔睬，記錄每次F(N)的結(jié)果，先找Map里的芹扭，沒(méi)有再遞歸計(jì)算麻顶，O(N), O(N)
3. 因?yàn)镕(N)只需要保留F(N-1)和F(N-2)，只需要2個(gè)狀態(tài)舱卡，而備忘錄算法是保留全部狀態(tài)辅肾，所以既不需要遞歸，也不需要備忘錄算法轮锥，直接遞推最簡(jiǎn)便矫钓，O(N), O(1)

找缺失數(shù)

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

判斷2的乘方

特征：

1. 如果一個(gè)整數(shù)是2的乘方新娜，那么它轉(zhuǎn)換成2進(jìn)制的時(shí)候，只有最高位是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算法

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

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

mysql table snapshot

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

問(wèn)題：
隨著標(biāo)簽越來(lái)越多铝耻，表結(jié)構(gòu)的列數(shù)量就越來(lái)越多，同時(shí)sql語(yǔ)句的where拼接也越來(lái)越臃腫骑疆。

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

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

映射

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

拆映射為標(biāo)簽

3. 最后實(shí)現(xiàn)

implementation

4. 例子

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

example1

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

example2

優(yōu)勢(shì)：

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

劣勢(shì)：

• 不支持非運(yùn)算（５堆隆）惊科。全量異或可以解決這個(gè)問(wèn)題

開(kāi)源方案：
java bitSet
google EWAHCompressedBitmap

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

布隆算法bloomFilter

一種以bitMap集合為基礎(chǔ)的去重算法。
如果說(shuō)爬蟲(chóng)亮钦，因?yàn)榕廊〉檬蔷W(wǎng)頁(yè)URL馆截，String類型，與數(shù)字類型不一樣蜂莉，因?yàn)椴煌瑂tring蜡娶，hashCode可能相同，所有不能直接使用單個(gè)bitmap就來(lái)判斷2個(gè)url是否相同映穗。

映射流程：（bloomFilter只需要一個(gè)bitMap窖张，但是一個(gè)key多次要映射）

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

誤判幾率：

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

決策樹(shù)算法

樹(shù)是一種很重要的數(shù)據(jù)結(jié)構(gòu)，可以為我們縮小問(wèn)題規(guī)模速梗，實(shí)現(xiàn)高效的查找。
背景：猜人名游戲襟齿。游戲中姻锁，出題者寫(xiě)下一個(gè)明星的名字，其他人需要猜出這個(gè)人是誰(shuí)猜欺。當(dāng)然位隶，如果游戲規(guī)則僅此而已的話，幾乎是無(wú)法猜出來(lái)的开皿，因?yàn)閱?wèn)題的規(guī)模太大了涧黄。為了降低游戲的難度，答題者可以向出題者問(wèn)問(wèn)題赋荆，而出題者必須準(zhǔn)確回答是或者否笋妥，答題者依據(jù)回答提出下一個(gè)問(wèn)題，如果能夠在指定次數(shù)內(nèi)確定謎底窄潭，即為勝出春宣，

• 是男的嗎？Y
• 是亞洲人嗎？Y
• 是中國(guó)人嗎月帝？N
• 是印度人嗎躏惋？Y
• ……

decision tree snapshot

算法思想：

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

最重要的是第一步，即需要想出一個(gè)重要的策略嚷辅，即選擇什么樣的特征可以實(shí)現(xiàn)最好的分類效果簿姨。使用純凈度來(lái)評(píng)價(jià)分類效果，熵來(lái)量化純凈度簸搞。
熵表示一個(gè)系統(tǒng)的混亂程度款熬，熵越大，說(shuō)明數(shù)據(jù)集純凈度越低攘乒；當(dāng)數(shù)據(jù)集都是同一個(gè)類別的時(shí)候贤牛，此時(shí)熵是0。目標(biāo)就是使得熵最低则酝。

6組樣本

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

6組樣本的決策樹(shù)

使用上述決策樹(shù)來(lái)判斷一個(gè)新晉用戶（需要將該用戶的4個(gè)特征都拿到）是否會(huì)購(gòu)買該產(chǎn)品挚瘟。

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

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

a star algorithm snapshot

起點(diǎn)(1,2)析苫，終點(diǎn)(5,2)。過(guò)程穿扳，

1. 計(jì)算當(dāng)期點(diǎn)的可達(dá)點(diǎn)
2. Fmin是(2,2)衩侥，所以將其加入移出openList，加入closeList
3. 看當(dāng)前格子(2,2)的上下左右矛物，是否在openlist當(dāng)中茫死，如果不在，加入openList泽谨，并計(jì)算F

Base64算法

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

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

base64 encode

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

對(duì)稱加密 vs 非對(duì)稱加密 vs hash

對(duì)稱加密，一方通過(guò)密鑰將信息加密后搓蚪，把密文傳給另一方蛤售，另一方通過(guò)這個(gè)相同的密鑰將密文解密，轉(zhuǎn)換成可以理解的明文妒潭，這類算法在加密和解密時(shí)使用相同的密鑰悴能，這組密鑰成為在兩個(gè)或多個(gè)成員間的共同秘密，
指加密和解密使用相同密鑰的加密算法

明文 <-> 密鑰 <-> 密文
常見(jiàn)的對(duì)稱加密算法有DES雳灾、3DES漠酿、Blowfish、IDEA谎亩、RC4炒嘲、RC5、RC6和AES

非對(duì)稱加密匈庭，首先要有一對(duì)key夫凸，一個(gè)被稱為private key私鑰，一個(gè)成為public key公鑰阱持，然后可以把你的public key分發(fā)給想給你傳密文的用戶夭拌，然后這些用戶使用該public key加密過(guò)的密文，只有使用你的private key才能解密衷咽。也就是說(shuō)鸽扁，只要你自己保存好你的private key，就能確保兵罢，別人想給你發(fā)的密文不被破解献烦，所以你不用擔(dān)心盟友的密鑰被盜，
指加密和解密使用不同密鑰的加密算法卖词，也稱為公私鑰加密

常見(jiàn)的非對(duì)稱加密算法有：RSA、ECC（移動(dòng)設(shè)備用）吏夯、Diffie-Hellman此蜈、El Gamal、DSA（數(shù)字簽名用）
SSH的加密原理中噪生，使用到了RSA非對(duì)稱加密算法

hash算法裆赵，Hash算法特別的地方在于它是一種單向算法，用戶可以通過(guò)Hash算法對(duì)目標(biāo)信息生成一段特定長(zhǎng)度的唯一的Hash值跺嗽，卻不能通過(guò)這個(gè)Hash值重新獲得目標(biāo)信息战授。因此Hash算法常用在不可還原的密碼存儲(chǔ)页藻、信息完整性校驗(yàn)等。

常見(jiàn)的Hash算法有MD2植兰、MD4份帐、MD5楣导、HAVAL毡咏、SHA

消息安全傳輸
用戶甲乙之間先建立安全通信信道臊旭，再開(kāi)始傳輸具體消息，

1. 甲生成pk1(public key奸鸯，公鑰)和sk1(secret key蓄拣，私鑰)
2. 甲在Internet中傳輸pk1給乙（黑客可以截取到pk）
3. 乙接收到pk1后咽斧，乙生成非對(duì)稱加密(pk2, sk2)
4. 乙用pk1對(duì)pk2加密岭洲，并傳給甲（pk1加密的只有sk1能加密）（黑客可以截取pk1加密過(guò)的pk2）
5. 甲收到pk1加密過(guò)的pk2后碑诉，用sk1解密快毛，得到pk2
6. 甲用pk2對(duì)對(duì)稱密鑰keyX加密贴铜，然后傳給乙（可截取）
7. 乙用sk2解密得到keyX
8. 后續(xù)甲乙雙方就基于keyX來(lái)通信（先非對(duì)稱加密玖详，再對(duì)稱加密）

一次一密安全傳輸

MD5算法, message digest algorithm

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

生成：

md5 generation

傳輸：

md5 transmission

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

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

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

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

彩虹表例子，

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

SHA算法

哈希摘要算法
和MD5算法類似已卷，SHA(secure hash algorithm)也是一種生成信息摘要的算法梧田。
SHA-1,SHA-2,SHA-256，第一位數(shù)字大版本號(hào)悼尾，第二位數(shù)字是子版本號(hào)柿扣。
SHA-1摘要長(zhǎng)度160bit；而MD5的摘要長(zhǎng)度是128bit闺魏，但MD5生成摘要的性能比SHA-1好未状。
SHA-256：可以生成長(zhǎng)度256bit的信息摘要。

AES算法析桥，advanced encryption standard

對(duì)稱加密算法

• 摘要算法是不可逆的司草，它的主要作用是對(duì)信息一致性和完整性的校驗(yàn)
• 對(duì)稱加密算法是可逆的，它的主要作用是保證私密信息不被泄露

AES128, AES192, AES256泡仗，指的是AES算法對(duì)不同長(zhǎng)度密鑰的使用埋虹。特點(diǎn)，

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

AES

java code example

其中境输，

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

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

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

AES的分組長(zhǎng)度對(duì)應(yīng)的輪數(shù)如下亏钩，

1. AES128，10輪欺旧，N=8
2. AES192姑丑，12輪
3. AES256，14輪

不同截?cái)嗟膔ound有不同的處理步驟辞友，
初始輪栅哀，

1. 加輪密鑰 addRoundKey

普通輪，

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

最終輪，

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

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

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

AES ori

AES+salt

紅黑樹(shù)

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

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

二叉查找樹(shù)BST snapshot1

BST snapshot2

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

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

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

1. 變色，紅黑互換
2. 左旋贺奠，要符合BST的規(guī)則霜旧，就很容易理解b這個(gè)節(jié)點(diǎn)該放在哪個(gè)位置，因?yàn)閅要上來(lái)儡率，但是x < b < y吐绵，所以b要在x的右節(jié)點(diǎn)朴则，x又要在y的左節(jié)點(diǎn)。
3. 右旋，y < c < x

左旋

右旋

RBT before adjust

RBT insert 21 and adjust

HashMap

HashMap是一個(gè)用于存儲(chǔ)Key-Value pair 鍵值對(duì)的集合蔓涧，每一個(gè)鍵值對(duì)pairs也叫Entry。這個(gè)Entry分散存儲(chǔ)在一個(gè)數(shù)組當(dāng)中渐苏，這個(gè)數(shù)組就是HashMap的主干技健。

hashmap snapshot1

index = Hash("apple") = 2

hashmap snapshot2

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

hashmap snapshot3

put(k, v), 存儲(chǔ)某個(gè)(key, value)時(shí)死遭，調(diào)用Entry(k, v)的hashcode計(jì)算hash從而得到index广恢，然后將Entry放入其中。

get(key), 查找某個(gè)key的value殃姓，步驟如下袁波，

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

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

2的冪

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

summary

cocurrentHashmap

在jdk8之前，concurrentHashmap使用了分段鎖segment來(lái)實(shí)現(xiàn)并發(fā)羹令。
concurrentHashmap當(dāng)中每個(gè)segment各自持有一把鎖鲤屡，在保證線程安全的同時(shí)降低了鎖的粒度，讓并發(fā)操作效果更高特恬。
讀寫(xiě)過(guò)程执俩，
Get方法，

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

Put方法显拜，

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

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

返回concurrentHashmap的總元素?cái)?shù)量的size()函數(shù)档址，大體邏輯，

1. 遍歷所有segment
2. 把segment的元素?cái)?shù)量累加起來(lái)邻梆，S1
3. 把segment的修改次數(shù)累加起來(lái)守伸，S2
4. 判斷所有segment的總修改次數(shù)是否大于上一次的總修改次數(shù)
   1. 如果大于，說(shuō)明統(tǒng)計(jì)過(guò)程中有修改浦妄，重新統(tǒng)計(jì)尼摹，嘗試次數(shù)+1
   2. 如果沒(méi)有修改见芹，統(tǒng)計(jì)結(jié)束
5. 如果嘗試次數(shù)超過(guò)閾值(=2)，則對(duì)每一個(gè)segment加鎖蠢涝，再重新統(tǒng)計(jì)
6. 再次判斷所有segment的總修改次數(shù)是否大于上一次的總修改次數(shù)玄呛。由于已經(jīng)加鎖，次數(shù)一定和上次相等
7. 釋放鎖和二，統(tǒng)計(jì)結(jié)束

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

單例

1. 雙重鎖檢測(cè)

public class Singleton {

    private volatile static Singleton instance = null; //單例對(duì)象

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

    public static Singleton getInstance() {
        if (instance == null) { //雙重檢測(cè)機(jī)制
            synchronized (Singleton.class) { //同步鎖,要類級(jí)別的,不能是對(duì)象鎖
                if (instance == null) { //雙重檢測(cè)機(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)定的养晋，變化無(wú)常的衬吆，所以需要被時(shí)刻關(guān)注著。
其大概作用绳泉，

1. 保證一個(gè)變量在線程之間的可見(jiàn)性逊抡，表現(xiàn)為即時(shí)更新變量值到主內(nèi)存×憷遥基于CPU的內(nèi)存屏障指令是可見(jiàn)性的保證冒嫡，happen-before原則
2. 阻止編譯時(shí)和運(yùn)行時(shí)的指令重排。編譯時(shí)依靠?jī)?nèi)存屏障來(lái)阻止JVM編譯器對(duì)指令的重排四苇；運(yùn)行時(shí)依靠CPU屏障指令來(lái)阻止重排
3. 64位long/double安全讀取孝凌，因?yàn)?Java 中讀取 long 類型變量不是原子的

線程間的可見(jiàn)性

指令重排

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

Netty

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

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

   1. 阻塞IO，blocking io穆碎，一個(gè)線程對(duì)應(yīng)一個(gè)socket

      
      
      BIO

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

      
      
      NIO

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

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

單體架構(gòu)優(yōu)點(diǎn)耿焊，

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

但是當(dāng)其產(chǎn)品規(guī)模越來(lái)越大時(shí)遍搞，缺點(diǎn)就更為突出罗侯，

1. 項(xiàng)目過(guò)于臃腫，當(dāng)大大小小的功能模塊都集中在同一項(xiàng)目的時(shí)候溪猿，整個(gè)項(xiàng)目必然會(huì)變得臃腫钩杰，讓開(kāi)發(fā)者難以維護(hù)
2. 資源無(wú)法隔離，整個(gè)單體系統(tǒng)的各個(gè)功能模塊都依賴于同樣的數(shù)據(jù)庫(kù)再愈、內(nèi)存榜苫、IO等資源，一旦某個(gè)功能模塊對(duì)資源使用不當(dāng)翎冲，整個(gè)系統(tǒng)的其他功能都會(huì)被拖垮
3. 無(wú)法靈活擴(kuò)展垂睬，當(dāng)系統(tǒng)的訪問(wèn)量越來(lái)越大的時(shí)候，單體系統(tǒng)固然可以進(jìn)行水平擴(kuò)展（多個(gè)實(shí)例）抗悍，部署在多臺(tái)機(jī)器上組成集群驹饺。但是這種擴(kuò)展并非靈活的擴(kuò)展。比如我們現(xiàn)在的性能瓶頸是支付模塊缴渊，希望只針對(duì)支付模塊做水平擴(kuò)展赏壹，這一點(diǎn)在單體系統(tǒng)是做不到的（因?yàn)椴渴鹗钦麄€(gè)項(xiàng)目的部署，而整個(gè)項(xiàng)目不僅僅包含支付模塊）

單體架構(gòu)

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

微服務(wù)架構(gòu)是為了解決上述臃腫單項(xiàng)目問(wèn)題衔沼，將單項(xiàng)目拆開(kāi)成多個(gè)獨(dú)立的服務(wù)蝌借，然后各自調(diào)用昔瞧，特點(diǎn)如下，

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

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

2. 資源的有效隔離，每一個(gè)微服務(wù)擁有獨(dú)立的數(shù)據(jù)源瞧哟，假如微服務(wù)A想要讀寫(xiě)微服務(wù)B的數(shù)據(jù)庫(kù)混巧，只能調(diào)用微服務(wù)B對(duì)外暴露的接口來(lái)完成。這樣有效避免了服務(wù)之間爭(zhēng)用數(shù)據(jù)庫(kù)和緩存資源所帶來(lái)的問(wèn)題

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

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

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

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

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

總而言之陨亡，微服務(wù)架構(gòu)的核心思想是凿傅，一個(gè)應(yīng)用是由多個(gè)小的、相互獨(dú)立的数苫、微服務(wù)組成，這些服務(wù)運(yùn)行在自己的進(jìn)程中辨液，開(kāi)發(fā)和發(fā)布都沒(méi)有依賴虐急。不同服務(wù)通過(guò)一些輕量級(jí)交互機(jī)制來(lái)通信，例如 RPC滔迈、HTTP 等止吁，服務(wù)可獨(dú)立擴(kuò)展伸縮，每個(gè)服務(wù)定義了明確的邊界燎悍，不同的服務(wù)甚至可以采用不同的編程語(yǔ)言來(lái)實(shí)現(xiàn)敬惦，由獨(dú)立的團(tuán)隊(duì)來(lái)維護(hù)。

SOA vs 微服務(wù)

• SOA谈山，粗粒度俄删，系統(tǒng)之間的服務(wù)調(diào)用。合奏路，把很多系統(tǒng)串聯(lián)在一起
• 微服務(wù)畴椰，細(xì)粒度，按業(yè)務(wù)拆分成不同的服務(wù)鸽粉。拆斜脂，把很多功能模塊拆分出來(lái)提供服務(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醋粟，且等待隊(duì)列未滿靡菇，則進(jìn)入等待隊(duì)列
3. 如果curPoolSize > corePoolSize，且等待隊(duì)列已滿米愿，且小于maximumPoolSize厦凤，則創(chuàng)建新線程執(zhí)行任務(wù)
4. 如果curPoolSize > corePoolSize，且等待隊(duì)列已滿育苟，且大于maximumPoolSize较鼓，則調(diào)用飽和策略來(lái)處理該任務(wù)
5. 線程池里的每個(gè)線程執(zhí)行完任務(wù)后不會(huì)立刻退出，而是會(huì)去檢查下等待隊(duì)列里是否還有線程任務(wù)需要執(zhí)行违柏，如果在keepAliveTime里等不到新的任務(wù)了博烂，那么線程就會(huì)退出，直至baseline = corePoolSize條

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

• FixedThreadPool

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

• CachedThreadPool

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

• SingleThreadExecutor

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

• ScheduledThreadPool

//定時(shí)或者周期性運(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());
    }
//等待隊(duì)列DelayedWorkQueue是無(wú)界的，所以maximumPoolSize參數(shù)無(wú)效