本筆記來自極客時(shí)間王爭的課程，原文包含更多細(xì)節(jié)内贮，強(qiáng)烈推薦！
筆記1鏈接：http://www.reibang.com/p/5c2456f38aad

六鹃操、排序

1）各種排序算法的時(shí)間復(fù)雜度對比

image.jpeg

2）如何分析一個(gè)排序算法

a.算法的執(zhí)行效率

• 最好情況雪隧、最壞情況、平均情況（以及其需要排序的原始數(shù)據(jù)是什么樣子的）
• 時(shí)間復(fù)雜度的系數(shù)悬蔽、常數(shù)、低階
• 比較次數(shù)和交換（或移動的次數(shù)）
  b.算法的內(nèi)存消耗
• 原地排序算法：指空間復(fù)雜度是O(1)的排序算法
  c.排序算法的穩(wěn)定性
• 穩(wěn)定性捉兴。這個(gè)概念是說蝎困，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后倍啥，相等元素之間原有的先后順序不變禾乘。

3）電商系統(tǒng)中，訂單時(shí)間和金額的排序問題

背景：我們現(xiàn)在要給電商交易系統(tǒng)中的“訂單”排序虽缕。訂單有兩個(gè)屬性始藕，一個(gè)是下單時(shí)間，另一個(gè)是訂單金額氮趋。如果我們現(xiàn)在有 10 萬條訂單數(shù)據(jù)伍派，我們希望按照金額從小到大對訂單數(shù)據(jù)排序。對于金額相同的訂單剩胁，我們希望按照下單時(shí)間從早到晚有序诉植。對于這樣一個(gè)排序需求，我們怎么來做呢昵观？
答：我們先按照下單時(shí)間給訂單排序晾腔，注意是按照下單時(shí)間舌稀，不是金額。排序完成之后灼擂，我們用穩(wěn)定排序算法壁查，按照訂單金額重新排序。兩遍排序之后剔应，我們得到的訂單數(shù)據(jù)就是按照金額從小到大排序睡腿，金額相同的訂單按照下單時(shí)間從早到晚排序的。

4）有序度和逆序度的概念
有序度是數(shù)組中具有有序關(guān)系的元素對的個(gè)數(shù)领斥。有序元素對用數(shù)學(xué)表達(dá)式表示：a[i] <= a[j], 如果i < j嫉到。
滿有序度，完全有序的數(shù)組的有序度月洛。
逆序度 = 滿有序度 - 有序度
例子1：對于一個(gè)倒序排列的數(shù)組何恶，比如 6，5嚼黔，4细层，3，2唬涧，1疫赎，有序度是 0；對于一個(gè)完全有序的數(shù)組碎节，比如 1捧搞，2，3狮荔，4胎撇，5，6殖氏，有序度就是 n(n-1)/2晚树，也就是 15。
例子2：冒泡排序包含兩個(gè)操作原子雅采，比較和交換爵憎。每交換一次，有序度就加 1婚瓜。不管算法怎么改進(jìn)宝鼓，交換次數(shù)總是確定的，即為逆序度巴刻，也就是n(n-1)/2–初始有序度席函。

5）插入排序和冒泡排序的時(shí)間復(fù)雜度相同，都是 O(n2)冈涧，在實(shí)際的軟件開發(fā)里茂附，為什么我們更傾向于使用插入排序算法而不是冒泡排序算法呢正蛙？

冒泡排序不管怎么優(yōu)化，元素交換的次數(shù)是一個(gè)固定值营曼，是原始數(shù)據(jù)的逆序度乒验。插入排序是同樣的，不管怎么優(yōu)化蒂阱，元素移動的次數(shù)也等于原始數(shù)據(jù)的逆序度锻全。但是，從代碼實(shí)現(xiàn)上來看录煤，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復(fù)雜鳄厌，冒泡排序需要 3 個(gè)賦值操作，而插入排序只需要 1 個(gè)妈踊。我們來看這段操作：

//冒泡排序中數(shù)據(jù)的交換操作：
if (a[j] > a[j+1]) { // 交換
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

//插入排序中數(shù)據(jù)的移動操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 數(shù)據(jù)移動
} else {
  break;
}

我們把執(zhí)行一個(gè)賦值語句的時(shí)間粗略地計(jì)為單位時(shí)間（unit_time）了嚎，然后分別用冒泡排序和插入排序?qū)ν粋€(gè)逆序度是 K 的數(shù)組進(jìn)行排序。用冒泡排序廊营，需要 K 次交換操作歪泳，每次需要 3 個(gè)賦值語句，所以交換操作總耗時(shí)就是 3*K 單位時(shí)間露筒。而插入排序中數(shù)據(jù)移動操作只需要 K 個(gè)單位時(shí)間呐伞。

6）如何用有限的內(nèi)存對10個(gè)文件進(jìn)行排序

問題：現(xiàn)在你有 10 個(gè)接口訪問日志文件，每個(gè)日志文件大小約 300MB慎式，每個(gè)文件里的日志都是按照時(shí)間戳從小到大排序的伶氢。你希望將這 10 個(gè)較小的日志文件，合并為 1 個(gè)日志文件瘪吏，合并之后的日志仍然按照時(shí)間戳從小到大排列鞍历。如果處理上述排序任務(wù)的機(jī)器內(nèi)存只有 1GB，你有什么好的解決思路肪虎，能“快速”地將這 10 個(gè)日志文件合并嗎？
參考1：先取得十個(gè)文件時(shí)間戳的最小值數(shù)組的最小值a惧蛹，和最大值數(shù)組的最大值b扇救。然后取mid=(a+b)/2，然后把每個(gè)文件按照mid分割香嗓，取所有前面部分之和迅腔，如果小于1g就可以讀入內(nèi)存快排生成中間文件，否則繼續(xù)取時(shí)間戳的中間值分割文件靠娱，直到區(qū)間內(nèi)文件之和小于1g沧烈。同理對所有區(qū)間都做同樣處理。最終把生成的中間文件按照分割的時(shí)間區(qū)間的次序直接連起來即可像云。
參考2：參考1最大好處是充分利用了內(nèi)存锌雀。
但是我還是會這么做：
1.申請10個(gè)40M的數(shù)組和一個(gè)400M的數(shù)組蚂夕。
2.每個(gè)文件都讀40M，取各數(shù)組中最大時(shí)間戳中的最小值腋逆。
3.然后利用二分查找婿牍，在其他數(shù)組中快速定位到小于/等于該時(shí)間戳的位置，并做標(biāo)記惩歉。
4.再把各數(shù)組中標(biāo)記位置之前的數(shù)據(jù)全部放在申請的400M內(nèi)存中等脂，
5.在原來的40M數(shù)組中清除已參加排序的數(shù)據(jù)。[可優(yōu)化成不挪動數(shù)據(jù)撑蚌，只是用兩個(gè)索引標(biāo)記有效數(shù)據(jù)的起始和截止位置]
6.對400M內(nèi)存中的有效數(shù)據(jù)[沒裝滿]做快排上遥。
將排好序的直接寫文件。
7.再把每個(gè)數(shù)組盡量填充滿争涌。從第2步開始繼續(xù)粉楚，知道各個(gè)文件都讀區(qū)完畢。
這么做的好處有：
1.每個(gè)文件的內(nèi)容只讀區(qū)一次第煮，且是批量讀區(qū)解幼。比每次只取一條快得多。
2.充分利用了讀區(qū)到內(nèi)存中的數(shù)據(jù)包警。曹源 同學(xué)在文件中查找那個(gè)中間數(shù)是會比較困難的撵摆。
3.每個(gè)拷貝到400M大數(shù)組中參加快排的數(shù)據(jù)都被寫到了文件中，這樣每個(gè)數(shù)只參加了一次快排害晦。

7）如何根據(jù)年齡給100萬用戶數(shù)據(jù)排序特铝？

根據(jù)年齡給 100 萬用戶排序，就類似按照成績給 50 萬考生排序壹瘟。我們假設(shè)年齡的范圍最小 1 歲鲫剿，最大不超過 120 歲。我們可以遍歷這 100 萬用戶稻轨，根據(jù)年齡將其劃分到這 120 個(gè)桶里灵莲，然后依次順序遍歷這 120 個(gè)桶中的元素。這樣就得到了按照年齡排序的 100 萬用戶數(shù)據(jù)殴俱。
（桶排序：核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里政冻，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序。桶內(nèi)排完序之后线欲，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出明场，組成的序列就是有序的了。）

leetcode
https://leetcode-cn.com/problems/third-maximum-number/ 第三大的元素
https://leetcode-cn.com/problems/merge-sorted-array/ 合并兩個(gè)有序數(shù)組

七李丰、查找

1）二分查找應(yīng)用的局限性

首先苦锨，二分查找依賴的是順序表結(jié)構(gòu)，簡單點(diǎn)說就是數(shù)組。（二分查找依賴下標(biāo)隨機(jī)訪問元素）
其次舟舒，二分查找針對的是有序數(shù)據(jù)拉庶。
再次，數(shù)據(jù)量太小不適合二分查找魏蔗。
最后砍的，數(shù)據(jù)量太大也不適合二分查找。

2）二分查找的經(jīng)典變體

查找第一個(gè)值等于給定值的元素莺治； 測試用例[1,3,4,5,6,8,8,8,11,18]
查找最后一個(gè)值等于給定值的元素;
查找第一個(gè)大于給定值的元素
查找最后一個(gè)小于等于給定值的元素

3）如何快速定位IP對應(yīng)的省份地址廓鞠？

背景：我們維護(hù)一個(gè)很大的 IP 地址庫來實(shí)現(xiàn)的。地址庫中包括 IP 地址范圍和歸屬地的對應(yīng)關(guān)系谣旁。
例子：當(dāng)我們想要查詢 202.102.133.13 這個(gè) IP 地址的歸屬地時(shí)床佳，我們就在地址庫中搜索，發(fā)現(xiàn)這個(gè) IP 地址落在[202.102.133.0, 202.102.133.255]這個(gè)地址范圍內(nèi)榄审，那我們就可以將這個(gè) IP 地址范圍對應(yīng)的歸屬地“山東東營市”顯示給用戶了砌们。

[202.102.133.0, 202.102.133.255] 山東東營市 
[202.102.135.0, 202.102.136.255] 山東煙臺 
[202.102.156.34, 202.102.157.255] 山東青島 
[202.102.48.0, 202.102.48.255] 江蘇宿遷 
[202.102.49.15, 202.102.51.251] 江蘇泰州 
[202.102.56.0, 202.102.56.255] 江蘇連云港

問題：假設(shè)我們有 12 萬條這樣的 IP 區(qū)間與歸屬地的對應(yīng)關(guān)系，如何快速定位出一個(gè) IP 地址的歸屬地呢搁进？
（在龐大的地址庫中逐一比對 IP 地址所在的區(qū)間浪感，是非常耗時(shí)的。）
答：
如果 IP 區(qū)間與歸屬地的對應(yīng)關(guān)系不經(jīng)常更新饼问，我們可以先預(yù)處理這 12 萬條數(shù)據(jù)影兽，讓其按照起始 IP 從小到大排序。如何來排序呢莱革？我們知道峻堰，IP 地址可以轉(zhuǎn)化為 32 位的整型數(shù)。所以，我們可以將起始地址，按照對應(yīng)的整型值的大小關(guān)系烘跺，從小到大進(jìn)行排序。
然后镶蹋，這個(gè)問題就可以轉(zhuǎn)化為我剛講的第四種變形問題“在有序數(shù)組中，查找最后一個(gè)小于等于某個(gè)給定值的元素”了赏半。當(dāng)我們要查詢某個(gè) IP 歸屬地時(shí)贺归，我們可以先通過二分查找，找到最后一個(gè)起始 IP 小于等于這個(gè) IP 的 IP 區(qū)間除破，然后，檢查這個(gè) IP 是否在這個(gè) IP 區(qū)間內(nèi)琼腔，如果在瑰枫，我們就取出對應(yīng)的歸屬地顯示；如果不在，就返回未查找到光坝。

leetcode

https://leetcode-cn.com/problems/sqrtx/ x的平方根
進(jìn)階：求x的平方根且精確到小數(shù)點(diǎn)后6位

def sqrt(x):
    '''
    求平方根尸诽，精確到小數(shù)點(diǎn)后6位
    '''
    low = 0
    mid = x / 2
    high = x
    while abs(mid ** 2 - x) > 0.000001:
        if mid ** 2 < x:
            low = mid
        else:
            high = mid
        mid = (low + high) / 2
    return mid

八、跳表

1）跳表是什么盯另？

鏈表加多級索引的結(jié)構(gòu)性含，就是跳表。
例子：從圖中我們可以看出鸳惯，原來沒有索引的時(shí)候商蕴，查找 62 需要遍歷 62 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 11 個(gè)結(jié)點(diǎn)芝发，速度提高了很多

image.jpeg

image.jpeg

2）跳表的時(shí)間復(fù)雜度與空間

時(shí)間復(fù)雜度為O(logn)绪商、空間復(fù)雜度為O(n)。推理過程見原文辅鲸。

3）為什么Redis要用跳表來實(shí)現(xiàn)有序集合格郁？（跳表vs紅黑樹）

Redis中的有序集合支持的核心操作主要有：插入一個(gè)數(shù)據(jù)；刪除一個(gè)數(shù)據(jù)独悴；查找一個(gè)數(shù)據(jù)例书；按照區(qū)間查找數(shù)據(jù)（比如查找值在[100, 356]之間的數(shù)據(jù)）；迭代輸出有序序列刻炒。

• 按照區(qū)間查找更高效：插入决采、刪除、查找以及迭代輸出有序序列這幾個(gè)操作落蝙，紅黑樹也可以完成织狐，時(shí)間復(fù)雜度跟跳表是一樣的。但是筏勒，按照區(qū)間來查找數(shù)據(jù)這個(gè)操作移迫，紅黑樹的效率沒有跳表高。對于按照區(qū)間查找數(shù)據(jù)這個(gè)操作管行，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)厨埋，然后在原始鏈表中順序往后遍歷就可以了。這樣做非常高效捐顷。
• 跳表更容易代碼實(shí)現(xiàn)
• 跳表更加靈活荡陷，它可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗迅涮。

九废赞、散列表

1)散列表是什么？

散列表用的就是數(shù)組支持按照下標(biāo)隨機(jī)訪問的時(shí)候叮姑，時(shí)間復(fù)雜度是 O(1) 的特性唉地。我們通過散列函數(shù)把元素的鍵值映射為下標(biāo)据悔，然后將數(shù)據(jù)存儲在數(shù)組中對應(yīng)下標(biāo)的位置。當(dāng)我們按照鍵值查詢元素時(shí)耘沼，我們用同樣的散列函數(shù)极颓，將鍵值轉(zhuǎn)化數(shù)組下標(biāo)，從對應(yīng)的數(shù)組下標(biāo)的位置取數(shù)據(jù)群嗤。

例子：假如我們有 89 名選手參加學(xué)校運(yùn)動會菠隆。為了方便記錄成績，每個(gè)選手胸前都會貼上自己的參賽號碼狂秘。這 89 名選手的編號依次是 1 到 89『Ь叮現(xiàn)在我們希望編程實(shí)現(xiàn)這樣一個(gè)功能，通過編號快速找到對應(yīng)的選手信息赃绊。你會怎么做呢既峡？我們可以把這 89 名選手的信息放在數(shù)組里。編號為 1 的選手碧查，我們放到數(shù)組中下標(biāo)為 1 的位置运敢；編號為 2 的選手，我們放到數(shù)組中下標(biāo)為 2 的位置忠售。以此類推传惠，編號為 k 的選手放到數(shù)組中下標(biāo)為 k 的位置。
參賽選手的編號我們叫做鍵（key）或者關(guān)鍵字稻扬。我們用它來標(biāo)識一個(gè)選手卦方。我們把參賽編號轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法就叫作散列函數(shù)（或“Hash 函數(shù)”“哈希函數(shù)”），而散列函數(shù)計(jì)算得到的值就叫作散列值（或“Hash 值”“哈希值”）泰佳。

image.jpeg

2）Word 文檔中單詞拼寫檢查功能是如何實(shí)現(xiàn)的盼砍？

常用的英文單詞有 20 萬個(gè)左右，假設(shè)單詞的平均長度是 10 個(gè)字母逝她，平均一個(gè)單詞占用 10 個(gè)字節(jié)的內(nèi)存空間浇坐，那 20 萬英文單詞大約占 2MB 的存儲空間，就算放大 10 倍也就是 20MB黔宛。對于現(xiàn)在的計(jì)算機(jī)來說近刘，這個(gè)大小完全可以放在內(nèi)存里面。所以我們可以用散列表來存儲整個(gè)英文單詞詞典臀晃。當(dāng)用戶輸入某個(gè)英文單詞時(shí)觉渴，我們拿用戶輸入的單詞去散列表中查找。如果查到徽惋，則說明拼寫正確案淋；如果沒有查到，則說明拼寫可能有誤险绘，給予提示踢京。借助散列表這種數(shù)據(jù)結(jié)構(gòu)回右，我們就可以輕松實(shí)現(xiàn)快速判斷是否存在拼寫錯(cuò)誤。

3）假設(shè)我們有 10 萬條 URL 訪問日志漱挚，如何按照訪問次數(shù)給 URL 排序？

遍歷 10 萬條數(shù)據(jù)渺氧，以 URL 為 key旨涝，訪問次數(shù)為 value，存入散列表侣背，同時(shí)記錄下訪問次數(shù)的最大值 K白华，時(shí)間復(fù)雜度 O(N)。

如果 K 不是很大贩耐，可以使用桶排序弧腥，時(shí)間復(fù)雜度 O(N)。如果 K 非常大（比如大于 10 萬）潮太，就使用快速排序管搪，復(fù)雜度 O(NlogN)。

4）有兩個(gè)字符串?dāng)?shù)組铡买，每個(gè)數(shù)組大約有 10 萬條字符串更鲁，如何快速找出兩個(gè)數(shù)組中相同的字符串？

以第一個(gè)字符串?dāng)?shù)組構(gòu)建散列表奇钞，key 為字符串澡为，value 為出現(xiàn)次數(shù)。再遍歷第二個(gè)字符串?dāng)?shù)組景埃，以字符串為 key 在散列表中查找媒至，如果 value 大于零，說明存在相同字符串谷徙。時(shí)間復(fù)雜度 O(N)拒啰。

leetcode

https://leetcode-cn.com/problems/design-hashset/submissions/705. 設(shè)計(jì)哈希集合

十、哈希算法

1）什么是哈希算法蒂胞？

將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串图呢，這個(gè)映射的規(guī)則就是哈希算法。而通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值骗随。（常用哈希算法MD5蛤织，SHA）

2）哈希算法要滿足的幾點(diǎn)要求

從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）；
對輸入數(shù)據(jù)非常敏感鸿染，哪怕原始數(shù)據(jù)只修改了一個(gè) Bit指蚜，最后得到的哈希值也大不相同；
散列沖突的概率要很小涨椒，對于不同的原始數(shù)據(jù)摊鸡，哈希值相同的概率非常姓烂健；
哈希算法的執(zhí)行效率要盡量高效免猾，針對較長的文本是辕，也能快速地計(jì)算出哈希值。

3）哈希算法的7個(gè)常見應(yīng)用

安全加密猎提、唯一標(biāo)識获三、數(shù)據(jù)校驗(yàn)、散列函數(shù)锨苏、負(fù)載均衡疙教、數(shù)據(jù)分片、分布式存儲伞租。

4）為什么哈希算法可以用于安全加密：

第一點(diǎn)是很難根據(jù)哈希值反向推導(dǎo)出原始數(shù)據(jù)贞谓，第二點(diǎn)是散列沖突的概率要很小。

5）唯一標(biāo)識：用哈希算法搜索一張圖是否在圖庫中存在

如果要在海量的圖庫中葵诈，搜索一張圖是否存在裸弦，我們不能單純地用圖片的元信息（比如圖片名稱）來比對，因?yàn)橛锌赡艽嬖诿Q相同但圖片內(nèi)容不同作喘，或者名稱不同圖片內(nèi)容相同的情況烁兰。那我們該如何搜索呢？
我們可以給每一個(gè)圖片取一個(gè)唯一標(biāo)識徊都，或者說信息摘要沪斟。比如，我們可以從圖片的二進(jìn)制碼串開頭取 100 個(gè)字節(jié)暇矫，從中間取 100 個(gè)字節(jié)主之，從最后再取 100 個(gè)字節(jié)，然后將這 300 個(gè)字節(jié)放到一塊李根，通過哈希算法（比如 MD5）槽奕，得到一個(gè)哈希字符串，用它作為圖片的唯一標(biāo)識房轿。通過這個(gè)唯一標(biāo)識來判定圖片是否在圖庫中粤攒，這樣就可以減少很多工作量。

6）數(shù)據(jù)校驗(yàn)：如何判斷文件下載過程中是否被篡改囱持？

背景：我們知道夯接，BT 下載的原理是基于 P2P 協(xié)議的。我們從多個(gè)機(jī)器上并行下載一個(gè) 2GB 的電影纷妆，這個(gè)電影文件可能會被分割成很多文件塊（比如可以分成 100 塊盔几，每塊大約 20MB）。等所有的文件塊都下載完成之后掩幢，再組裝成一個(gè)完整的電影文件就行了逊拍。如何校驗(yàn)文件下載中是否被宿主機(jī)器惡意修改過上鞠，又或者下載過程中出現(xiàn)了錯(cuò)誤？
哈希算法有一個(gè)特點(diǎn)芯丧，對數(shù)據(jù)很敏感芍阎。只要文件塊的內(nèi)容有一丁點(diǎn)兒的改變，最后計(jì)算出的哈希值就會完全不同缨恒。所以能曾，當(dāng)文件下載完成之后，我們可以通過相同的哈希算法肿轨，對下載好的文件求哈希值，然后跟種子文件中保存的哈希值比對蕊程。如果不同椒袍，說明這個(gè)文件塊不完整或者被篡改了，需要再重新從其他宿主機(jī)器上下載這個(gè)文件塊藻茂。

7）如何防止密碼被拖庫驹暑？

可以通過哈希算法，對用戶密碼進(jìn)行加密之后再存儲辨赐，不過最好選擇相對安全的加密算法优俘，比如 SHA 等（因?yàn)?MD5 已經(jīng)號稱被破解了）。我們可以引入一個(gè)鹽（salt）掀序，跟用戶的密碼組合在一起帆焕，增加密碼的復(fù)雜度。我們拿組合之后的字符串來做哈希算法加密不恭，將它存儲到數(shù)據(jù)庫中叶雹，進(jìn)一步增加破解的難度。

8）區(qū)塊鏈?zhǔn)褂玫氖悄姆N哈希算法换吧？是為了解決什么問題而使用的呢折晦？

區(qū)塊鏈?zhǔn)且粔K塊區(qū)塊組成的，每個(gè)區(qū)塊分為兩部分：區(qū)塊頭和區(qū)塊體沾瓦。
區(qū)塊頭保存著 自己區(qū)塊體 和 上一個(gè)區(qū)塊頭 的哈希值满着。
因?yàn)檫@種鏈?zhǔn)疥P(guān)系和哈希值的唯一性，只要區(qū)塊鏈上任意一個(gè)區(qū)塊被修改過贯莺，后面所有區(qū)塊保存的哈希值就不對了风喇。
區(qū)塊鏈?zhǔn)褂玫氖?SHA256 哈希算法，計(jì)算哈希值非常耗時(shí)缕探，如果要篡改一個(gè)區(qū)塊响驴，就必須重新計(jì)算該區(qū)塊后面所有的區(qū)塊的哈希值，短時(shí)間內(nèi)幾乎不可能做到撕蔼。

9）如何才能實(shí)現(xiàn)一個(gè)會話粘滯（session sticky）的負(fù)載均衡算法呢豁鲤？也就是說秽誊，我們需要在同一個(gè)客戶端上，在一次會話中的所有請求都路由到同一個(gè)服務(wù)器上琳骡。

可以通過哈希算法锅论，對客戶端 IP 地址或者會話 ID 計(jì)算哈希值，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算楣号，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號最易。

10）數(shù)據(jù)分片：如何統(tǒng)計(jì)“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)？

背景：假如我們有 1T 的日志文件炫狱，這里面記錄了用戶的搜索關(guān)鍵詞藻懒，我們想要快速統(tǒng)計(jì)出每個(gè)關(guān)鍵詞被搜索的次數(shù)，該怎么做呢视译？
我們來分析一下嬉荆。這個(gè)問題有兩個(gè)難點(diǎn)，第一個(gè)是搜索日志很大酷含，沒辦法放到一臺機(jī)器的內(nèi)存中鄙早。第二個(gè)難點(diǎn)是，如果只用一臺機(jī)器來處理這么巨大的數(shù)據(jù)椅亚，處理時(shí)間會很長限番。針對這兩個(gè)難點(diǎn)，我們可以先對數(shù)據(jù)進(jìn)行分片呀舔，然后采用多臺機(jī)器處理的方法弥虐，來提高處理速度。具體的思路是這樣的：為了提高處理的速度媚赖，我們用 n 臺機(jī)器并行處理躯舔。我們從搜索記錄的日志文件中，依次讀出每個(gè)搜索關(guān)鍵詞省古，并且通過哈希函數(shù)計(jì)算哈希值粥庄，然后再跟 n 取模，最終得到的值豺妓，就是應(yīng)該被分配到的機(jī)器編號惜互。這樣，哈希值相同的搜索關(guān)鍵詞就被分配到了同一個(gè)機(jī)器上琳拭。也就是說训堆，同一個(gè)搜索關(guān)鍵詞會被分配到同一個(gè)機(jī)器上。每個(gè)機(jī)器會分別計(jì)算關(guān)鍵詞出現(xiàn)的次數(shù)白嘁，最后合并起來就是最終的結(jié)果坑鱼。

十一：二叉樹

1）二叉樹基礎(chǔ)知識

• 二叉樹的高度（Height）、深度（Depth）、層（Level）鲁沥。

image.jpeg

• 滿二叉樹：葉子節(jié)點(diǎn)全都在最底層呼股，除了葉子節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)
• 完全二叉樹：葉子節(jié)點(diǎn)都在最底下兩層画恰，最后一層的葉子節(jié)點(diǎn)都靠左排列彭谁，并且除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大
• 鏈?zhǔn)酱鎯Ψǎ烘準(zhǔn)酱鎯Ψㄔ噬取膱D中你應(yīng)該可以很清楚地看到缠局，每個(gè)節(jié)點(diǎn)有三個(gè)字段，其中一個(gè)存儲數(shù)據(jù)考润，另外兩個(gè)是指向左右子節(jié)點(diǎn)的指針

image.jpeg

• 順序存儲法：我們把根節(jié)點(diǎn)存儲在下標(biāo) i = 1 的位置狭园，那左子節(jié)點(diǎn)存儲在下標(biāo) 2 * i = 2 的位置，右子節(jié)點(diǎn)存儲在 2 * i + 1 = 3 的位置糊治。(適合存儲完全二叉樹唱矛。

image.jpeg

2）二叉樹的遍歷：前序中序后序

• 前序遍歷，對于樹中的任意節(jié)點(diǎn)來說俊戳，先打印這個(gè)節(jié)點(diǎn)，然后再打印它的左子樹馆匿，最后打印它的右子樹抑胎。
• 中序遍歷，對于樹中的任意節(jié)點(diǎn)來說渐北，先打印它的左子樹阿逃，然后再打印它本身，最后打印它的右子樹赃蛛。
• 后序遍歷恃锉，對于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹呕臂，然后再打印它的右子樹破托，最后打印這個(gè)節(jié)點(diǎn)本身。

image.jpeg

3）二叉查找樹

定義:二叉查找樹中歧蒋，每個(gè)節(jié)點(diǎn)的值都大于左子樹節(jié)點(diǎn)的值土砂，小于右子樹節(jié)點(diǎn)的值。

特性:只需要中序遍歷谜洽，就可以在 O(n) 的時(shí)間復(fù)雜度內(nèi)萝映，輸出有序的數(shù)據(jù)序列。

4）二叉樹的查找阐虚、插入序臂、刪除操作

代碼略

5）二叉查找樹和散列表的比較

散列表的優(yōu)勢：時(shí)間負(fù)責(zé)度低。散列表的插入实束、刪除奥秆、查找操作的時(shí)間復(fù)雜度可以做到常量級的 O(1)逊彭，非常高效。而二叉查找樹在比較平衡的情況下吭练，插入诫龙、刪除、查找操作時(shí)間復(fù)雜度才是 O(logn)鲫咽。

二叉樹的優(yōu)勢：

1. 散列表中的數(shù)據(jù)是無序存儲的签赃，如果要輸出有序的數(shù)據(jù)，需要先進(jìn)行排序分尸。而對于二叉查找樹來說锦聊，我們只需要中序遍歷，就可以在 O(n) 的時(shí)間復(fù)雜度內(nèi)箩绍，輸出有序的數(shù)據(jù)序列孔庭。
2. 散列表擴(kuò)容耗時(shí)很多，而且當(dāng)遇到散列沖突時(shí)材蛛，性能不穩(wěn)定圆到，盡管二叉查找樹的性能不穩(wěn)定，但是在工程中卑吭，我們最常用的平衡二叉查找樹的性能非常穩(wěn)定芽淡，時(shí)間復(fù)雜度穩(wěn)定在 O(logn)。
3. 盡管散列表的查找等操作的時(shí)間復(fù)雜度是常量級的豆赏，但因?yàn)楣_突的存在挣菲，這個(gè)常量不一定比 logn 小，所以實(shí)際的查找速度可能不一定比 O(logn) 快掷邦。加上哈希函數(shù)的耗時(shí)白胀，也不一定就比平衡二叉查找樹的效率高。
4. 散列表的構(gòu)造比二叉查找樹要復(fù)雜抚岗，需要考慮的東西很多或杠。比如散列函數(shù)的設(shè)計(jì)、沖突解決辦法宣蔚、擴(kuò)容廷痘、縮容等。平衡二叉查找樹只需要考慮平衡性這一個(gè)問題件已，而且這個(gè)問題的解決方案比較成熟笋额、固定。
5. 為了避免過多的散列沖突篷扩，散列表裝載因子不能太大兄猩，特別是基于開放尋址法解決沖突的散列表，不然會浪費(fèi)一定的存儲空間。

leetcode

樹問題集合https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefb4e/
（二叉樹的前序枢冤、中序鸠姨、后序遍歷（遞歸 vs非遞歸方法）；二叉樹的最大深度淹真；對稱二叉樹讶迁；二叉樹的路徑總和）

十三、圖

1）圖基礎(chǔ)

• 圖中的元素我們就叫做頂點(diǎn)（vertex）核蘸；
• 頂點(diǎn)與頂點(diǎn)之間的關(guān)系就叫做邊（edge）巍糯；
• 無向圖中，頂點(diǎn)的度（degree）就是跟頂點(diǎn)相連接的邊的條數(shù)客扎。
• 有向圖中祟峦，我們把度分為入度（In-degree）和出度（Out-degree）（微博的例子，入度就表示有多少粉絲徙鱼，出度就表示關(guān)注了多少人）
• 帶權(quán)圖（weighted graph）宅楞。在帶權(quán)圖中，每條邊都有一個(gè)權(quán)重（weight）袱吆，我們可以通過這個(gè)權(quán)重來表示 QQ 好友間的親密度厌衙。

2）圖的存儲方式（鄰接矩陣、鄰接表）

• 鄰接矩陣（Adjacency Matrix）绞绒。即一個(gè)二維數(shù)組婶希，行與列代表節(jié)點(diǎn)，值代表邊处铛。
  缺點(diǎn)：浪費(fèi)空間饲趋；優(yōu)點(diǎn)：能高效獲取兩個(gè)節(jié)點(diǎn)間的關(guān)系拐揭；方便計(jì)算撤蟆，能將圖的計(jì)算轉(zhuǎn)化為矩陣運(yùn)算。

  
  
  image.jpeg
• 鄰接表（Adjacency List）每個(gè)頂點(diǎn)對應(yīng)一條鏈表堂污，鏈表中存儲的是與這個(gè)頂點(diǎn)相連接的其他頂點(diǎn)

• 優(yōu)點(diǎn)：節(jié)省空間家肯，缺點(diǎn)：使用起來很耗時(shí)間。

  
  
  image.jpeg

3）如何存儲微博盟猖、微信等這些社交網(wǎng)絡(luò)的好友關(guān)系

問題：微博讨衣、微信、LinkedIn 這些社交軟件我想你肯定都玩過吧式镐。在微博中反镇，兩個(gè)人可以互相關(guān)注；在微信中娘汞，兩個(gè)人可以互加好友歹茶。那你知道，如何存儲微博、微信等這些社交網(wǎng)絡(luò)的好友關(guān)系嗎惊豺？

需求：判斷用戶 A 是否關(guān)注了用戶 B燎孟；判斷用戶 A 是否是用戶 B 的粉絲；用戶 A 關(guān)注用戶 B尸昧；用戶 A 取消關(guān)注用戶 B揩页；根據(jù)用戶名稱的首字母排序，分頁獲取用戶的粉絲列表烹俗；根據(jù)用戶名稱的首字母排序爆侣，分頁獲取用戶的關(guān)注列表。

回答：關(guān)于如何存儲一個(gè)圖衷蜓，前面我們講到兩種主要的存儲方法累提，鄰接矩陣和鄰接表。因?yàn)樯缃痪W(wǎng)絡(luò)是一張稀疏圖磁浇，使用鄰接矩陣存儲比較浪費(fèi)存儲空間斋陪。所以，這里我們采用鄰接表來存儲置吓。鄰接表中存儲了用戶的關(guān)注關(guān)系无虚，逆鄰接表中存儲的是用戶的被關(guān)注關(guān)系。

在數(shù)據(jù)庫中的存儲方式：一列userid衍锚，一列followid友题，為了提高效率，兩列都建立了索引戴质。

image.jpeg

image.jpeg