????1哈希算法（上）

? ? ? ? 將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串翩迈，這個映射的規(guī)則就是哈希算法持灰。通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值。

? ? ? ? 如：

? ? ? ? 這節(jié)課的內(nèi)容比較偏實(shí)戰(zhàn)负饲，了解了哈希算法的四個應(yīng)用場景堤魁，分別是：

? ? ? ? 1.安全加密。我們講到任何哈希算法都會出現(xiàn)散列沖突返十，但是這個沖突概率非常小妥泉。越是復(fù)雜的哈希算法越難破解，但是同樣的它的計(jì)算時(shí)間也會比較長洞坑。所以選擇哈希算法的時(shí)候盲链，要權(quán)衡一下安全性和計(jì)算時(shí)間來決定使用哪種哈希算法。

? ? ? ? 2.唯一標(biāo)識迟杂。哈希算法可以對大數(shù)據(jù)做信息摘要刽沾，通過一個較短的二進(jìn)制編碼來表示很大的數(shù)據(jù)。

? ? ? ? 3.數(shù)據(jù)校驗(yàn)排拷。用于校驗(yàn)數(shù)據(jù)的完整性和正確性侧漓。

? ? ? ? 4.散列函數(shù)。我們前面講的散列函數(shù)也是哈希算法的一種應(yīng)用监氢，它對哈希算法的要求非常特別布蔗，更加看重的是散列的平均性和哈希算法的執(zhí)行效率。

? ? 2哈希算法（下）

? ? ? ? 上節(jié)課講了哈希算法的四個應(yīng)用浪腐，這節(jié)課再補(bǔ)充三個應(yīng)用何鸡，但是它們和上節(jié)課的應(yīng)用稍稍有些不同，因?yàn)檫@節(jié)課的三個應(yīng)用都和分布式系統(tǒng)有關(guān)牛欢。

? ? ? ? 5.負(fù)載均衡骡男。通過哈希算法，對客戶端IP地址或者會話ID計(jì)算哈希值傍睹，將取得的哈希值與服務(wù)器列表的大小進(jìn)行進(jìn)行取模運(yùn)算隔盛，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號犹菱。

????????利用哈希算法替代映射表，可以實(shí)現(xiàn)一個會話粘滯的負(fù)載均衡策略吮炕。

? ? ? ? （會話粘滯我理解為同一個客戶端請求服務(wù)時(shí)都路由到同一個服務(wù)器上）

? ? ? ? 6.數(shù)據(jù)分片腊脱。

? ? ? ? 數(shù)據(jù)分片這里舉了兩個例子，一個是統(tǒng)計(jì)“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)：我們可以先對數(shù)據(jù)進(jìn)行分片龙亲，然后采用多臺機(jī)器處理的方法陕凹，來提高處理速度；另一個是快速判斷圖片是否在庫中：通過哈希算法計(jì)算這個圖片的唯一標(biāo)識鳄炉，然后與機(jī)器個數(shù)n求余取模杜耙，得到對應(yīng)的機(jī)器編號。

????????通過哈希算法對處理的海量數(shù)據(jù)進(jìn)行分片拂盯，多機(jī)分布式處理佑女，可以突破單機(jī)資源的限制。

? ? ? ? 7.分布式存儲谈竿。現(xiàn)在互聯(lián)網(wǎng)面對的都是海量的數(shù)據(jù)团驱、海量的用戶，我們?yōu)榱颂岣邤?shù)據(jù)的讀取空凸、寫入能力嚎花，一般都采用分布式的方式來存儲數(shù)據(jù)。和前面的思想一樣呀洲，通過哈希算法對數(shù)據(jù)取哈希值紊选，然后對機(jī)器個數(shù)取模，這個最終值就是應(yīng)該存儲的緩存機(jī)器編號两嘴。

? ? ? ? ?但是此時(shí)出現(xiàn)了一個問題，如果數(shù)據(jù)增多到原先的10個（假如它是10個）已經(jīng)無法承受了族壳，我們就需要擴(kuò)容憔辫，比如擴(kuò)到11個機(jī)器，那么現(xiàn)在哈希值與機(jī)器個數(shù)取模得到的結(jié)果和之前計(jì)算的結(jié)果就不一致了仿荆。

? ? ? ? 這里引入了一致性哈希算法：假如我們有k個機(jī)器贰您，數(shù)據(jù)的哈希值的范圍是[0，MAX]拢操。我們將整個范圍劃分成m個小區(qū)間（m遠(yuǎn)大于k）锦亦，每個機(jī)器負(fù)責(zé)m/k個小區(qū)間。當(dāng)有新機(jī)器加入的時(shí)候令境，我們就將某幾個小區(qū)間的數(shù)據(jù)杠园，從原來的機(jī)器中搬移到新的機(jī)器中。這樣舔庶，既不用全部重新哈希抛蚁、搬移數(shù)據(jù)陈醒，也保持了各個機(jī)器上數(shù)據(jù)數(shù)量的均衡。

? ? ? ? 利用一致性哈希算法瞧甩，可以解決緩存等分布式系統(tǒng)的擴(kuò)容钉跷、縮容導(dǎo)致的數(shù)據(jù)大量搬移的難題。

? ? 3二叉樹（上）

????????前面我們學(xué)習(xí)的都是線性表結(jié)構(gòu)肚逸，棧爷辙、隊(duì)列等等。今天我們學(xué)習(xí)一種非線性表結(jié)構(gòu)——樹朦促。

? ? ? ? 話不多說膝晾，看圖：

????????注意弄清楚樹中的父節(jié)點(diǎn)、子節(jié)點(diǎn)思灰、兄弟節(jié)點(diǎn)玷犹、葉節(jié)點(diǎn)的概念。

? ? ? ? 另外幾個比較重要的概念就是高度（Height）洒疚、深度（Depth）歹颓、層（Level），注意不要弄混哦：

? ? ? ? 可以參考下面這張圖更好的理解它們?nèi)齻€的不同：

? ? ? ? 樹的結(jié)構(gòu)很多樣油湖，但我們最常用的還是二叉樹：每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)巍扛，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。（但是并不要求每個節(jié)點(diǎn)都必須有兩個子節(jié)點(diǎn)哦）

? ? ? ? 注意有兩種比較特殊的二叉樹乏德。

? ? ? ? 1.滿二叉樹撤奸。即上圖中的編號為2的二叉樹。

? ? ? ? 2.完全二叉樹喊括。即上圖中的編號為3的二叉樹胧瓜。注意區(qū)分完全二叉樹和非完全二叉樹哦，這個比較容易弄混郑什。其實(shí)滿二叉樹就是完全二叉樹的一種特殊形式府喳。

? ? ? ? 想要存儲一顆二叉樹，有兩種辦法：1.基于指針或者引用的二叉鏈?zhǔn)酱鎯Ψ?/b>蘑拯，2.基于數(shù)組的順序存儲法钝满。

? ? ? ? 鏈?zhǔn)酱鎯Ψǎ?/p>

? ? ? ? 順序存儲法：

? ? ? ? 重點(diǎn)理解一下順序存儲法，完全二叉樹就是因?yàn)轫樞虼鎯Ψǘ灰錾昃剑诖鎯ν耆鏄涞臅r(shí)候非常節(jié)省空間弯蚜。

? ? ? ? 二叉樹的遍歷方式有：前序遍歷、中序遍歷剃法、后續(xù)遍歷碎捺，注意它們的不同：

? ? ? ? 這三種遍歷方式都是通過遞歸實(shí)現(xiàn)哦，并且遍歷的復(fù)雜度都為O(n)。

? ? 4二叉樹（下）

? ? ? ? 這節(jié)課學(xué)習(xí)了一種特殊的二叉樹牵寺，二叉查找樹悍引，它支持快速地查找、插入帽氓、刪除操作趣斤。（要掌握這三種操作的實(shí)現(xiàn)方式哦）

? ? ? ? 二叉查找樹中，每個節(jié)點(diǎn)的值都大于左子樹節(jié)點(diǎn)的值黎休，小于右子樹節(jié)點(diǎn)的值浓领。不過，這只是針對沒有重復(fù)數(shù)的情況势腮。

? ? ? ? 對于存在重復(fù)數(shù)據(jù)的二叉查找樹联贩，有兩種解決方法：1.讓每個節(jié)點(diǎn)存儲多個值相同的數(shù)據(jù)，2.每個節(jié)點(diǎn)中存儲一個數(shù)據(jù)捎拯，將值相同的數(shù)據(jù)存儲在它的右子樹中泪幌。

? ? ? ? 在二叉查找樹中，查找署照、插入祸泪、刪除等很多操作的時(shí)間復(fù)雜度都跟樹的高度成正比，兩個極端情況的時(shí)間復(fù)雜度分別是O(n)和O(logn)建芙，分別對應(yīng)二叉樹退化成鏈表的情況和完全二叉樹没隘。

? ? ? ? 為了避免時(shí)間復(fù)雜度的退化，針對二叉查找樹禁荸，又設(shè)計(jì)了一種更加復(fù)雜的樹——平衡二叉查找樹右蒲，時(shí)間復(fù)雜度可以做到穩(wěn)定的O(logn)，這就是我們下節(jié)課的內(nèi)容啦~

? ? ? ? 另外有一點(diǎn)要注意的是赶熟，為什么有的時(shí)候會用平衡二叉查找樹而不是用散列表瑰妄，也就是平衡二叉查找樹相對散列表的優(yōu)勢（當(dāng)然散列表也是有自己優(yōu)勢噠，它們各自都有自己的閃光點(diǎn)~）映砖。

? ? 5紅黑樹（上）

? ? ? ? 平衡二叉樹：二叉樹中任意一個節(jié)點(diǎn)的左右子樹的高度相差不能大于1间坐。（這樣說來其實(shí)我們之前說的滿二叉樹、完全二叉樹都是平衡二叉樹啊央。但是非完全二叉樹也有可能是平衡二叉樹哦~）

? ? ? ? 平衡二叉查找樹：同時(shí)滿足平衡二叉樹和二叉查找樹的特點(diǎn)眶诈。

? ? ? ? 紅黑樹（R-B Tree）：樹中的節(jié)點(diǎn)一類被標(biāo)記為黑色涨醋，一類被標(biāo)記為紅色瓜饥，除此之外還有幾個需要滿足的小條件，此處略浴骂。

? ? ? ? 紅黑樹是“近似平衡”的乓土，它做到了性能不會退化的太嚴(yán)重。其實(shí)紅黑樹并不是嚴(yán)格意義上的平衡查找二叉樹，它沒有完全符合左右子樹相差不能大于1這個條件趣苏，但是我們把“平衡”理解為時(shí)間復(fù)雜度退化不要太嚴(yán)重的時(shí)候狡相，它依然是一棵合格的平衡二叉查找樹。紅黑樹的高度接近logn食磕，所以它是近似平衡尽棕，插入、刪除彬伦、查找操作的時(shí)間復(fù)雜度都是O(logn)滔悉。

? ? ? ? 紅黑樹的實(shí)現(xiàn)很難。但我們其實(shí)不應(yīng)該把重點(diǎn)放在它的實(shí)現(xiàn)上单绑。我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法回官，要學(xué)習(xí)它的由來、特性搂橙、適用的場景以及它能解決的問題歉提。

????????因?yàn)榧t黑樹是一種性能非常穩(wěn)定的二叉查找樹，所以在工程中区转，但凡是用到動態(tài)插入苔巨、刪除、查找數(shù)據(jù)的場景蜗帜，都可以用到它恋拷。

? ? ? ? 但它實(shí)現(xiàn)起來比較難，如果要自己寫代碼來實(shí)現(xiàn)厅缺，我們更傾向于用跳表來代替它蔬顾。

? ? ? ? 另外注意要知道，為什么工程中都喜歡用紅黑樹湘捎，而不是其他平衡二叉查找樹（如Treap诀豁、Splay Tree、AVL數(shù)等）呢窥妇？

? ? 6紅黑樹（下）

? ? ? ? 這節(jié)課講了紅黑樹的實(shí)現(xiàn)方法舷胜，其實(shí)我有偷懶沒有認(rèn)真去看它的細(xì)節(jié)，因?yàn)槟壳皝碚f我不太需要掌握這些細(xì)節(jié)活翩，畢竟面試官也不會考我手寫紅黑樹的代碼烹骨，哈哈~當(dāng)然如果我真的需要去實(shí)現(xiàn)的時(shí)候，就需要跟著這些步驟把每個細(xì)節(jié)搞清楚然后一步一步去實(shí)現(xiàn)材泄。

? ? ? ? 上節(jié)課有說紅黑樹的定義沮焕，它還有一些小的要求，我當(dāng)時(shí)沒有寫出來拉宗，現(xiàn)在寫出來看一看：

? ? ? ? 1.根節(jié)點(diǎn)是黑色的峦树；

? ? ? ? 2.每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL）辣辫，也就是說，葉子節(jié)點(diǎn)不存儲數(shù)據(jù)魁巩；

? ? ? ? 3.任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色急灭，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的谷遂；

? ? ? ? 4.每個節(jié)點(diǎn)葬馋，從該節(jié)點(diǎn)到達(dá)其可達(dá)子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)肾扰。

? ? ? ? 而在插入点楼、刪除節(jié)點(diǎn)的過程中，第三白对、第四點(diǎn)要求可能會被破壞掠廓，而我們在實(shí)現(xiàn)紅黑樹的時(shí)候，關(guān)鍵點(diǎn)就在于在插入和刪除的過程中進(jìn)行“平衡調(diào)整”甩恼，實(shí)際上就是要把被破壞的第三蟀瞧、四點(diǎn)恢復(fù)過來。

? ? ? ? 在這個過程中需要用到的操作有：左旋（rotate left）条摸、右旋(rotate right)悦污、改變顏色，左旋右旋有它們的定義钉蒲，這里不作贅述切端。正在處理的節(jié)點(diǎn)叫做關(guān)注節(jié)點(diǎn)。

? ? ? ? 如果需要實(shí)現(xiàn)顷啼，我們可以跟著步驟一步一步來做踏枣，需要注意以下三點(diǎn)：

? ? ? ? 1.把紅黑樹的平衡調(diào)整的過程比作魔方復(fù)原，不要過于深究這個算法的正確性钙蒙，只要按照固定的操作步驟進(jìn)行就OK了茵瀑。

? ? ? ? 2.找準(zhǔn)關(guān)注節(jié)點(diǎn)，不要搞丟躬厌、搞錯關(guān)注節(jié)點(diǎn)马昨。

? ? ? ? 3.插入操作的平衡調(diào)整比較簡單，但是刪除操作就比較復(fù)雜扛施。

? ??????