1 棧

棧，操作受限的線性表否彩，F(xiàn)ILO锚国，棧頂插入和刪除，只有兩種操作骚烧，入棧Push(插入)、出棧POP(刪除)闰围。

棧

2 隊(duì)列

隊(duì)列赃绊，操作受限的線性表，F(xiàn)IFO羡榴，隊(duì)尾入隊(duì)(插入)碧查，隊(duì)首出隊(duì)(刪除)。

隊(duì)列

3 鏈表

鏈表跟數(shù)組同級(jí)別的數(shù)據(jù)結(jié)構(gòu)校仑，數(shù)組遍歷效率高忠售，插入刪除效率低，鏈表插入刪除效率高迄沫、遍歷效率低稻扬。ArrayList底層實(shí)現(xiàn)是數(shù)組，LinkedList底層實(shí)現(xiàn)是鏈表邢滑。

鏈表

4 散列表/哈希表

4.1 hash定義

• 哈希表又叫散列表或者Hash table腐螟，它通過把關(guān)鍵碼值key通過一個(gè)函數(shù)f(key)映射到表中一個(gè)位置來(lái)訪問記錄愿汰，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)/哈希函數(shù)乐纸，存放記錄的數(shù)組叫做哈希表/散列表/hashtable衬廷。
• 任意key經(jīng)過哈希函數(shù)映射到數(shù)組中的任何一個(gè)地址的概率相等，這樣的散列函數(shù)為均勻散列函數(shù)汽绢。
• 存在k1不等于k2吗跋，使得f(key1)=f(key2)，就叫哈希沖突宁昭。哈希沖突理論上不可能完全消除跌宛，但是應(yīng)該盡量避免。

4.2 為什么理想情況下hash表的時(shí)間復(fù)雜度是O(1)积仗？

• hash表物理存儲(chǔ)是個(gè)數(shù)組疆拘，極端情況下，如果所有key都發(fā)生了哈希沖突寂曹，則數(shù)組退化成鏈表哎迄，時(shí)間復(fù)雜度為O(n)。
• 如果不考慮哈希沖突隆圆，key可以通過哈希函數(shù)快速定位到數(shù)組下標(biāo)找到記錄value漱挚，時(shí)間復(fù)雜度為O(1)。

4.3 hash函數(shù)&hashcode

• hash函數(shù)(哈希)渺氧，也叫散列/雜湊函數(shù)旨涝，將任意長(zhǎng)度的輸入轉(zhuǎn)換為固定長(zhǎng)度的輸出，該輸出就是散列值侣背。這種轉(zhuǎn)換是一種壓縮映射白华，散列值的空間通常小于輸入空間，不同的輸入可能得到相同的輸出秃踩。

• hash函數(shù)的基礎(chǔ)是hash算法衬鱼，hash算法也可以認(rèn)為是一種思想，沒有固定的公式憔杨，只要符合散列思想的算法都可以成為hash算法，hash算法很難找到逆向規(guī)律蒜胖，可以提高空間利用率消别，提高數(shù)據(jù)查詢效率，常用于數(shù)字簽名台谢。

• hashcode寻狂，哈希碼，Java的Object.hashCode()記錄在Markword中朋沮，Hotspot虛擬機(jī)由xor-shift算法(異或和移位)實(shí)現(xiàn)蛇券，用于哈希表的查找

4.4 構(gòu)造hash函數(shù)的方法

• 直接定址法

  • H(key) = a·key + b，其中a和b為常數(shù)，這種線性散列函數(shù)也叫做自身函數(shù)
  • 此法僅適合于：地址集合的大小 = = 關(guān)鍵字集合的大小纠亚，其中a和b為常數(shù)塘慕。
  • 實(shí)際生活中，關(guān)鍵字的元素很少是連續(xù)的蒂胞。用該方法產(chǎn)生的哈希表會(huì)造成空間大量的浪費(fèi)图呢，因此這種方法適應(yīng)性并不強(qiáng)。

• 數(shù)字分析法

  • 因此數(shù)字分析法就是找出數(shù)字的規(guī)律骗随，盡可能利用這些數(shù)據(jù)來(lái)構(gòu)造沖突幾率較低的散列地址蛤织。
  • 此法適于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

• 平方取中法

  • 因?yàn)檫@種方法的原理是通過取平方擴(kuò)大差別鸿染，平方值的中間幾位和這個(gè)數(shù)的每一位都相關(guān)指蚜，則對(duì)不同的關(guān)鍵字得到的哈希函數(shù)值不易產(chǎn)生沖突，由此產(chǎn)生的哈希地址也較為均勻涨椒。
  • 此法適于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象姚炕。

• 折疊法

  • 將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）丢烘，這方法稱為折疊法柱宦。
  • 這種方法適用于關(guān)鍵字位數(shù)較多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況播瞳。
  • 數(shù)位疊加可以有移位疊加和間界疊加兩種方法：
    • 移位疊加是將分割后的每一部分的最低位對(duì)齊掸刊，然后相加；
    • 間界疊加是從一端向另一端沿分割界來(lái)回折疊赢乓，然后對(duì)齊相加忧侧。

• 隨機(jī)數(shù)法

  • 設(shè)定哈希函數(shù)為:H(key) = Random(key)其中，Random 為偽隨機(jī)函數(shù)
  • 此法適于：對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)牌芋。

• 除留余數(shù)法

  • 取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址蚓炬。即 H(key) = key MOD p,p<=m。不僅可以對(duì)關(guān)鍵字直接取模躺屁，也可在折疊肯夏、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要犀暑，除留余數(shù)法的模p取不大于表長(zhǎng)且最接近表長(zhǎng)m素?cái)?shù)時(shí)效果最好驯击，且p最好取1.1n～1.7n之間的一個(gè)素?cái)?shù)(n為存在的數(shù)據(jù)元素個(gè)數(shù))，若p選的不好耐亏，容易產(chǎn)生同義詞徊都。

• 基數(shù)轉(zhuǎn)換法

  • 將十進(jìn)制數(shù)X看作其他進(jìn)制，比如十三進(jìn)制广辰，再按照十三進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)暇矫，提取其中若干為作為X的哈希值主之。一般取大于原來(lái)基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)應(yīng)該是互素的李根。
  • 為了獲得良好的哈希函數(shù)槽奕，可以將幾種方法聯(lián)合起來(lái)使用，比如先變基朱巨，再折疊或平方取中等等史翘，只要散列均勻，就可以隨意拼湊冀续。

• 隨機(jī)乘數(shù)法

  • 亦稱為“乘余取整法”琼讽。隨機(jī)乘數(shù)法使用一個(gè)隨機(jī)實(shí)數(shù)f,0≤f<1,乘積fk的分?jǐn)?shù)部分在0～1之間，用這個(gè)分?jǐn)?shù)部分的值與n（哈希表的長(zhǎng)度）相乘洪唐，乘積的整數(shù)部分就是對(duì)應(yīng)的哈希值钻蹬，顯然這個(gè)哈希值落在0～n-1之間。其表達(dá)公式為：Hash(k)=「n(fk%1)」其中“fk%1”表示fk 的小數(shù)部分凭需，即fk%1=fk-「fk」
  • 此方法的優(yōu)點(diǎn)是對(duì)n的選擇不很關(guān)鍵问欠。通常若地址空間為p位就是選n=2p.Knuth對(duì)常數(shù)f的取法做了仔細(xì)的研究，他認(rèn)為f取任何值都可以粒蜈，但某些值效果更好顺献。如f=（-1）/2=0.6180329...比較理想。

• 字符串?dāng)?shù)值哈希法

  • 把字符串的前10個(gè)字符的ASCⅡ值之和對(duì)N取摸作為Hash地址枯怖，只要N較小注整，Hash地址將較均勻分布[0，N]區(qū)間內(nèi)度硝。

• 旋轉(zhuǎn)法

  • 旋轉(zhuǎn)法是將數(shù)據(jù)的鍵值中進(jìn)行旋轉(zhuǎn)肿轨。旋轉(zhuǎn)法通常并不直接使用在哈希函數(shù)上，而是搭配其他哈希函數(shù)使用蕊程。

• 減去法

  • 減去法是數(shù)據(jù)的鍵值減去一個(gè)特定的數(shù)值以求得數(shù)據(jù)存儲(chǔ)的位置椒袍。

4.5 解決hash沖突的方法

• 開放定址法(封閉散列)

  • Hi=(H(key) + di) MOD m,i=1,2，…藻茂，k(k<=m-1）驹暑，其中H(key)為散列函數(shù)，m為散列表長(zhǎng)捌治，di為增量序列岗钩，可有下列三種取法：
    • 線性探測(cè)再散列：di=1,2,3，…肖油，m-1；
    • 二次探測(cè)再散列：di=1^2,-12,2^2,-22臂港，⑶^{2森枪，…视搏，±（k)}2,(k<=m/2）；
    • 偽隨機(jī)探測(cè)再散列：di=偽隨機(jī)數(shù)序列县袱。
  • 優(yōu)點(diǎn)：
    • 記錄更容易進(jìn)行序列化（serialize）操作
    • 如果記錄總數(shù)可以預(yù)知浑娜，可以創(chuàng)建完美哈希函數(shù)，此時(shí)處理數(shù)據(jù)的效率是非常高的
  • 缺點(diǎn)：
    • 存儲(chǔ)記錄的數(shù)目不能超過桶數(shù)組的長(zhǎng)度式散，如果超過就需要擴(kuò)容筋遭，而擴(kuò)容會(huì)導(dǎo)致某次操作的時(shí)間成本飆升，這在實(shí)時(shí)或者交互式應(yīng)用中可能會(huì)是一個(gè)嚴(yán)重的缺陷暴拄；
    • 使用探測(cè)序列漓滔，有可能其計(jì)算的時(shí)間成本過高，導(dǎo)致哈希表的處理性能降低乖篷；
    • 由于記錄是存放在桶數(shù)組中的响驴，而桶數(shù)組必然存在空槽，所以當(dāng)記錄本身尺寸（size）很大并且記錄總數(shù)規(guī)模很大時(shí)撕蔼，空槽占用的空間會(huì)導(dǎo)致明顯的內(nèi)存浪費(fèi)豁鲤；
    • 刪除記錄時(shí)，比較麻煩鲸沮。比如需要?jiǎng)h除記錄a琳骡，記錄b是在a之后插入桶數(shù)組的，但是和記錄a有沖突讼溺，是通過探測(cè)序列再次跳轉(zhuǎn)找到的地址楣号，所以如果直接刪除a，a的位置變?yōu)榭詹凵隹瑁詹凼遣樵冇涗浭〉慕K止條件竖席，這樣會(huì)導(dǎo)致記錄b在a的位置重新插入數(shù)據(jù)前不可見，所以不能直接刪除a敬肚，而是設(shè)置刪除標(biāo)記毕荐。這就需要額外的空間和操作。

• 再散列法

  • Hi=RHi(key),i=1,2艳馒，…憎亚，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址弄慰，直到?jīng)_突不再發(fā)生第美，這種方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間陆爽。

• 鏈地址法/拉鏈法(開放散列)

  • 鏈地址法的基本思想是：每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next指針什往，多個(gè)哈希表節(jié)點(diǎn)可以用next指針構(gòu)成一個(gè)單向鏈表，被分配到同一個(gè)索引上的多個(gè)節(jié)點(diǎn)可以用這個(gè)單向鏈表連接起來(lái)慌闭。
  • 這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表别威，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中躯舔，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行省古。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況粥庄。
  • 優(yōu)點(diǎn)：
    • 對(duì)于記錄總數(shù)頻繁可變的情況，處理的比較好（也就是避免了動(dòng)態(tài)調(diào)整的開銷)豺妓；
    • 由于記錄存儲(chǔ)在結(jié)點(diǎn)中惜互，而結(jié)點(diǎn)是動(dòng)態(tài)分配，不會(huì)造成內(nèi)存的浪費(fèi)琳拭，所以尤其適合那種記錄本身尺寸（size）很大的情況训堆，因?yàn)榇藭r(shí)指針的開銷可以忽略不計(jì)了；
    • 刪除記錄時(shí)臀栈，比較方便蔫慧，直接通過指針操作即可。
  • 缺點(diǎn)：
    • 存儲(chǔ)的記錄是隨機(jī)分布在內(nèi)存中的权薯，這樣在查詢記錄時(shí)姑躲，相比結(jié)構(gòu)緊湊的數(shù)據(jù)類型（比如數(shù)組），哈希表的跳轉(zhuǎn)訪問會(huì)帶來(lái)額外的時(shí)間開銷盟蚣；
    • 如果所有的 key-value 對(duì)是可以提前預(yù)知黍析，并之后不會(huì)發(fā)生變化時(shí)（即不允許插入和刪除），可以人為創(chuàng)建一個(gè)不會(huì)產(chǎn)生沖突的完美哈希函數(shù)（perfect hash function）屎开，此時(shí)封閉散列的性能將遠(yuǎn)高于開放散列阐枣；
    • 由于使用指針，記錄不容易進(jìn)行序列化（serialize）操作奄抽。

• 建立一個(gè)公共溢出區(qū)

  • 這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分蔼两，凡是和基本表發(fā)生沖突的元素，一律填入溢出表逞度。

4.6 hash表的查找性能

查找過程中额划，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少档泽，產(chǎn)生的沖突少俊戳，查找效率就高，產(chǎn)生的沖突多馆匿，查找效率就低抑胎。因此，影響產(chǎn)生沖突多少的因素渐北，也就是影響查找效率的因素阿逃。影響產(chǎn)生沖突多少有以下三個(gè)因素：

• 散列函數(shù)是否均勻；
• 處理沖突的方法；
• 散列表的裝填因子盆昙。
  • 散列表的裝填因子定義為：α= 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度
  • α是散列表裝滿程度的標(biāo)志因子羽历。由于表長(zhǎng)是定值焊虏，α與“填入表中的元素個(gè)數(shù)”成正比淡喜，所以，α越大诵闭，填入表中的元素較多炼团，產(chǎn)生沖突的可能性就越大；α越小疏尿，填入表中的元素較少瘟芝，產(chǎn)生沖突的可能性就越小。

4.7 著名的hash算法

MD5 和 SHA-1 可以說是目前應(yīng)用最廣泛的Hash算法褥琐，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的锌俱。

• MD4

MD4(RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫敌呈。它適用在32位字長(zhǎng)的處理器上用高速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作來(lái)實(shí)現(xiàn)的贸宏。

• MD5

MD5(RFC 1321）是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組磕洪，其輸出是4個(gè)32位字的級(jí)聯(lián)吭练，與 MD4 相同。MD5比MD4來(lái)得復(fù)雜析显，并且速度較之要慢一點(diǎn)鲫咽，但更安全，在抗分析和抗差分方面表現(xiàn)更好

• SHA-1 及其他

SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的谷异，它對(duì)長(zhǎng)度小于264的輸入分尸，產(chǎn)生長(zhǎng)度為160bit的散列值，因此抗窮舉（brute-force）性更好歹嘹。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理箩绍，并且模仿了該算法。

4.8 hash算法在信息安全方面的應(yīng)用

• 文件校驗(yàn)

  • 我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)荞下，這2種校驗(yàn)并沒有抗數(shù)據(jù)篡改的能力伶选，它們一定程度上能檢測(cè)出數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對(duì)數(shù)據(jù)的惡意破壞尖昏。
  • MD5 Hash算法的"數(shù)字指紋"特性仰税，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗(yàn)和（Checksum）算法，不少Unix系統(tǒng)有提供計(jì)算md5 checksum的命令抽诉。

• 數(shù)字簽名

  • Hash 算法也是現(xiàn)代密碼體系中的一個(gè)重要組成部分陨簇。由于非對(duì)稱算法的運(yùn)算速度較慢，所以在數(shù)字簽名協(xié)議中迹淌，單向散列函數(shù)扮演了一個(gè)重要的角色河绽。對(duì) Hash 值己单，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名，在統(tǒng)計(jì)上可以認(rèn)為與對(duì)文件本身進(jìn)行數(shù)字簽名是等效的耙饰。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)纹笼。

• 鑒權(quán)協(xié)議

  • 如下的鑒權(quán)協(xié)議又被稱作挑戰(zhàn)--認(rèn)證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下苟跪，這是一種簡(jiǎn)單而安全的方法廷痘。

5 二叉樹

• 每個(gè)節(jié)點(diǎn)最多只有2個(gè)子樹的樹結(jié)構(gòu)叫二叉樹。二叉樹有五種基本形態(tài)件已。
• 二叉樹4大性質(zhì)：
  • 二叉樹的第i層上的結(jié)點(diǎn)數(shù)目最多為2(i-1)笋额，i>=1
  • 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)，k>=1
  • 包含n個(gè)結(jié)點(diǎn)的二叉樹的高度至少為log2(n+1)
  • 度為0的結(jié)點(diǎn)數(shù)為n0篷扩，度為2的結(jié)點(diǎn)數(shù)為n2兄猩，則n0=n2+1

二叉樹

二叉樹的五種基本形態(tài)

6 BST樹

• BST樹，Binary Search Tree鉴未，二叉查找樹枢冤、二叉搜索樹、排序二叉樹歼狼。

  • 左子樹所有結(jié)點(diǎn)值小于根結(jié)點(diǎn)值掏导，右子樹所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)值；
  • 任意結(jié)點(diǎn)的左右子樹都是BST樹羽峰；
  • 沒有鍵值相等的結(jié)點(diǎn)趟咆。

• BST插入操作(從根節(jié)點(diǎn)開始遞歸)：

  • 新插入的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)比較，相同則說明已存在不用重復(fù)插入梅屉；
  • 新插入的節(jié)點(diǎn) < 當(dāng)前節(jié)點(diǎn)值纱，則到當(dāng)前節(jié)點(diǎn)左子樹比較，直到插入成功坯汤；
  • 新插入的節(jié)點(diǎn) > 當(dāng)前節(jié)點(diǎn)虐唠，則到當(dāng)前節(jié)點(diǎn)右子樹比較，直到插入成功惰聂。

• BST刪除操作(從根節(jié)點(diǎn)開始遞歸)：

  • 待刪除節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)疆偿，則直接刪除；
  • 待刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)搓幌，則直接刪除杆故；
  • 待刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則先找到待刪除節(jié)點(diǎn)的替代節(jié)點(diǎn)(右子樹的最小節(jié)點(diǎn))溉愁，然后替換節(jié)點(diǎn)处铛，再刪除替換節(jié)點(diǎn)。

• BST查詢操作(遞歸遍歷)：

  • 深度優(yōu)先遍歷
    • 前序遍歷：最常見，根左右
    • 中序遍歷：左根右撤蟆，整棵BST樹采用中序遍歷即從小到大排序
    • 后序遍歷：左右根
  • 廣度優(yōu)先遍歷/層序遍歷：從上層到下層奕塑，每層從左到右

BST刪除任意節(jié)點(diǎn)-后繼

BST刪除任意節(jié)點(diǎn)-前驅(qū)

BST前序遍歷-根左右

BST中序遍歷-左根右

BST后序遍歷-左右根

7 AVL樹

• AVL樹是平衡的BST，在BST的特點(diǎn)上還有如下特點(diǎn)：

  • AVL樹的左右子樹高度之差的絕對(duì)值不超過1家肯；
  • AVL樹的左右子樹都是AVL樹
  • AVL樹任意節(jié)點(diǎn)的平衡因子只能是-1/0/1龄砰，平衡因子=右子樹高度-左子樹高度

• AVL樹經(jīng)歷插入或刪除操作后，如果平衡條件被破壞息楔，需要進(jìn)行旋轉(zhuǎn)操作來(lái)恢復(fù)平衡寝贡。

平衡因子=右子樹高度-左子樹高度

8 紅黑樹

• 紅黑樹是自平衡的BST。紅黑樹有5大特點(diǎn)：

  • 節(jié)點(diǎn)有紅色或黑色值依；
  • 根節(jié)點(diǎn)是黑色；
  • 葉子結(jié)點(diǎn)是黑色碟案；
  • 每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色愿险；
  • 從任意節(jié)點(diǎn)到其葉子結(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

• 紅黑樹通過變色价说、左旋辆亏、右旋來(lái)保持平衡，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決鳖目。

• 紅黑樹通過為節(jié)點(diǎn)增加顏色換取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低扮叨，AVL樹旋轉(zhuǎn)次數(shù)比紅黑樹要多，紅黑樹的插入效率更高领迈。

• 紅黑樹的左旋操作(左比右低)

左旋

• 紅黑樹的右旋操作(左比右高)

右旋

• 紅黑樹增加節(jié)點(diǎn)：

  • 按照BST的方式彻磁，將節(jié)點(diǎn)插入；

  • 將插入的節(jié)點(diǎn)著色為紅色

    • 插入的節(jié)點(diǎn)是根節(jié)點(diǎn)：直接涂為黑色
    • 插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色：什么也不做
    • 插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色：說明插入節(jié)點(diǎn)存在非空祖父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)狸捅，分3種情況討論
      • 紅黑樹-增加節(jié)點(diǎn)

  • 一系列旋轉(zhuǎn)和著色衷蜓，使之成為一顆紅黑樹。

• 紅黑樹刪除節(jié)點(diǎn)：

  • 按照BST的方式置吓，將節(jié)點(diǎn)刪除衍锚；
  • 一系列旋轉(zhuǎn)和著色，使之成為一顆紅黑樹：
    • 被刪除節(jié)點(diǎn)是紅+黑：直接涂為黑色斗埂；
    • 被刪除節(jié)點(diǎn)是黑+黑，且是根節(jié)點(diǎn)：什么都不做
    • 被刪除節(jié)點(diǎn)是黑+黑，且不是根節(jié)點(diǎn)：分4種情況討論崭捍。
      • 紅黑樹-刪除節(jié)點(diǎn)

9 B Tree

• 數(shù)據(jù)庫(kù)索引文件存儲(chǔ)在磁盤上粒梦，當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引文件很大，不能一次性裝載到內(nèi)存，只能每次裝載磁盤頁(yè)夫植，磁盤頁(yè)里面就是索引樹的節(jié)點(diǎn)陌兑。
• 每次磁盤IO就是將樹的節(jié)點(diǎn)裝載到磁盤頁(yè)加載到內(nèi)存狞玛，BST在最壞情況下，磁盤IO次數(shù)等于索引樹的高度。
• 為了減少磁盤IO次數(shù)，要把樹從"瘦高"變得"矮胖"，BST是二叉查找樹著淆，B樹是多路平衡查找樹。B樹的比較次數(shù)不比BST少，但是相對(duì)磁盤IO的速度，內(nèi)存中比較耗時(shí)幾乎可以忽略，只要樹的高度足夠低，磁盤IO次數(shù)足夠小，就可以提升查找性能亩鬼。
• B樹每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子阿蝶，m稱為B樹的階雳锋，m的大小取決于磁盤頁(yè)的大小魄缚。一個(gè)m階的B樹具有如下幾個(gè)特征：
  • 根節(jié)點(diǎn)至少有兩個(gè)孩子；
  • 每個(gè)葉子結(jié)點(diǎn)都包含k-1個(gè)元素，其中k取值[m/2卧檐，m]盈罐；
  • 所有的葉子結(jié)點(diǎn)都處于同一層；
  • 每個(gè)節(jié)點(diǎn)中的元素從小到大排列闪唆；
  • 每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子票顾，其中k取值[m/2，m]笼吟；

10 B+ Tree

• B+樹是B樹的變體库物，比B樹有更高的查詢性能，在B樹基礎(chǔ)上還有如下特點(diǎn)：
  • 非葉子結(jié)點(diǎn)不保存數(shù)據(jù)只用于索引贷帮，所有數(shù)據(jù)都保存在葉子結(jié)點(diǎn)戚揭，葉子結(jié)點(diǎn)之間指針相連，葉子結(jié)點(diǎn)元素從小到大排序撵枢；
  • 有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素(B樹中是k-1個(gè)元素)民晒；
• B+樹中間節(jié)點(diǎn)只用來(lái)索引精居，所以同樣大小的磁盤頁(yè)可以容納更多的節(jié)點(diǎn)元素，數(shù)據(jù)量相同情況下潜必，B+樹的結(jié)構(gòu)比B-樹更加"矮胖"靴姿，因此查詢時(shí)IO次數(shù)更少，查詢效率更高磁滚。
• B+樹每次查詢必須到葉子結(jié)點(diǎn)結(jié)束佛吓，B樹只要匹配到元素即可，因此B+樹的查找比B樹更穩(wěn)定垂攘。
• B+樹所有葉子節(jié)點(diǎn)形成有序鏈表维雇，便于范圍查詢。

11 線段樹

線段樹使用場(chǎng)景-區(qū)間染色

線段樹是使用場(chǎng)景-區(qū)間查詢

線段樹區(qū)間查詢時(shí)間復(fù)雜度

線段樹

滿二叉樹節(jié)點(diǎn)數(shù)量和層數(shù)關(guān)系

12 Trie Tree(字典樹)

Trie樹使用場(chǎng)景

Trie樹/字典樹/前綴樹

13 并查集(Union Find)

并查集使用場(chǎng)景

并查集Union Find

14 SkipList(跳表)

• SkipList晒他，跳表/跳躍表吱型，是一種空間換時(shí)間的算法，是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)陨仅，跳表的原理比較簡(jiǎn)單津滞，但是效率和紅黑樹及AVL樹不相上下，開源軟件Redis和LevelDB都有使用到跳表灼伤。

  • 跳表由很多層結(jié)構(gòu)組成触徐；
  • 每一層都是一個(gè)有序的鏈表；
  • 最底層(Level 1)鏈表包含所有的元素狐赡；
  • 如果一個(gè)元素出現(xiàn)在Level i的鏈表中锌介，則它一定也會(huì)出現(xiàn)在Level i下層的鏈表中；
  • 每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針猾警，一個(gè)指向同一層鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素隆敢。

• 丟硬幣決定K发皿，隨機(jī)變量K滿足參數(shù)為p=1/2的幾何分布，K的期望值為2層拂蝎。

• 跳表的高度等于n次實(shí)驗(yàn)中產(chǎn)生的最大K

• 跳表的空間復(fù)雜度：每個(gè)元素的期望高度是2穴墅，一個(gè)大小為n的跳表，其節(jié)點(diǎn)數(shù)目的期望值是2n

• 跳表的查詢

  • 從top層開始温自，依次跟鏈表中元素比較玄货；
  • 待查找元素比當(dāng)前節(jié)點(diǎn)大，同時(shí)比鏈表中最大值小的時(shí)候悼泌，跳到下一層繼續(xù)比較松捉，依次進(jìn)行；
  • 最壞情況會(huì)到Level 1層比較馆里，直到查找到所需元素隘世，否則沒有此元素。

• 跳表的插入

  • 先確定待插入元素會(huì)插入到第K層，K是丟硬幣隨機(jī)決定的唱较；
  • 然后在第K層的以下各層都插入該元素悬秉；
  • 如果K大于跳表的層數(shù)，則要添加新的層械媒。

• 跳表的刪除

  • 先在每一層查找到待刪除的節(jié)點(diǎn)目锭；
  • 然后在每一層使用鏈表中刪除節(jié)點(diǎn)的方式刪除該節(jié)點(diǎn)。

15 位圖(bitmap)

• 位圖通撤桌蹋基于數(shù)組來(lái)實(shí)現(xiàn)痢虹，數(shù)組每個(gè)元素存儲(chǔ)一個(gè)數(shù)據(jù)，該元素只占一個(gè)bit位兰绣，用一個(gè)bit標(biāo)識(shí)該元素是否存在世分，可以大大節(jié)省內(nèi)存空間。

• 位圖常用業(yè)務(wù)場(chǎng)景：

  • 布隆過濾器bloom filter
  • 快速去重
  • 快速排序
  • 快速查詢

• Bitmap實(shí)現(xiàn)快速去重

  • 2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)缀辩，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)臭埋。 首先，根據(jù)“內(nèi)存空間不
    足以容納這2.5億個(gè)整數(shù)”我們可以快速的聯(lián)想到Bit-map臀玄。
  • 下邊關(guān)鍵的問題就是怎么設(shè)計(jì)我們的Bit-map來(lái)表示這2.5億個(gè)數(shù)字的狀態(tài)了瓢阴。其實(shí)這個(gè)問題很簡(jiǎn)單，一個(gè)數(shù)字的狀態(tài)只有三種健无，分別為不存在荣恐，只有一個(gè)，有重復(fù)累贤。因此叠穆，我們只需要2bits就可以對(duì)一個(gè)數(shù)字的狀態(tài)進(jìn)行存儲(chǔ)了，假設(shè)我們?cè)O(shè)定一個(gè)數(shù)字不存在為00臼膏，存在一次01硼被，存在兩次及其以上為11。那我們大概需要存儲(chǔ)空間幾十兆左右渗磅。 接下來(lái)的任務(wù)就是遍歷一次這2.5億個(gè)數(shù)字嚷硫，如果對(duì)應(yīng)的狀態(tài)位為00，則將其變?yōu)?1始鱼；如果對(duì)應(yīng)的狀態(tài)位為01仔掸，則將其變?yōu)?1；如果為11医清，,對(duì)應(yīng)的轉(zhuǎn)態(tài)位保持不變起暮。
  • 最后，我們將狀態(tài)位為01的進(jìn)行統(tǒng)計(jì)状勤，就得到了不重復(fù)的數(shù)字個(gè)數(shù)鞋怀，時(shí)間復(fù)雜度為O(n)双泪。

• Bitmap實(shí)現(xiàn)快速排序

  • 假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）,我們就可以采用Bit-map的方法來(lái)達(dá)到排序的目的。要表示8個(gè)數(shù)密似，我們就只需要8個(gè)Bit（1Bytes）焙矛，首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0残腌， 對(duì)應(yīng)位設(shè)置為1:
  • 遍歷一遍Bit區(qū)域村斟，將該位是一的位的編號(hào)輸出（2，3抛猫，4蟆盹，5，7）闺金，這樣就達(dá)到了排序的目的逾滥，時(shí)間復(fù)雜度O(n)。
  • 優(yōu)點(diǎn)： 運(yùn)算效率高败匹，不需要進(jìn)行比較和移位寨昙；占用內(nèi)存少，比如N=10000000掀亩；只需占用內(nèi)存為N/8=1250000Byte=1.25M舔哪。
  • 缺點(diǎn)： 所有的數(shù)據(jù)不能重復(fù)。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找槽棍。

• Bitmap實(shí)現(xiàn)快速查詢

  • 利用Bit-map也可以進(jìn)行快速查詢捉蚤，這種情況下對(duì)于一個(gè)數(shù)字只需要一個(gè)bit位就可以了，0表示不
    存在炼七，1表示存在缆巧。假設(shè)上述的題目改為，如何快速判斷一個(gè)數(shù)字是夠存在于上述的2.5億個(gè)數(shù)字集合中豌拙。
  • 首先我們先對(duì)所有的數(shù)字進(jìn)行一次遍歷盅蝗，然后將相應(yīng)的轉(zhuǎn)態(tài)位改為1。遍歷完以后就是查詢姆蘸，由于我們的Bit-map采取的是連續(xù)存儲(chǔ)（整型數(shù)組形式，一個(gè)數(shù)組元素對(duì)應(yīng)32bits）芙委，我們實(shí)際上是采用了一種分桶的思想逞敷。一個(gè)數(shù)組元素可以存儲(chǔ)32個(gè)狀態(tài)位，那將待查詢的數(shù)字除以32灌侣，定位到對(duì)應(yīng)的數(shù)組元素（桶）推捐，然后再求余（%32），就可以定位到相應(yīng)的狀態(tài)位侧啼。如果為1牛柒，則代表改數(shù)字存在堪簿；否則，該數(shù)字不存在皮壁。

• Bitmap實(shí)現(xiàn)布隆過濾器(Bloom Filter)

  • Bloom Filter減少誤判概率方法：
    • 讓Bitmap的空間更大椭更，hash次數(shù)更大(一般是8次)，空間和準(zhǔn)確率上折中蛾魄；
    • 加一個(gè)白名單虑瀑，專門存儲(chǔ)誤判的URL或郵箱等數(shù)據(jù)。