(7)散列表

①散列函數(shù)

散列函數(shù)可以算出數(shù)據(jù)存放對(duì)應(yīng)的數(shù)組下標(biāo)，當(dāng)出現(xiàn)散列沖突可以通過(guò)開(kāi)放尋址法（適合數(shù)據(jù)量比較小盒犹、裝載因子小的時(shí)候）懂更、鏈表法（適合存儲(chǔ)大對(duì)象、大數(shù)據(jù)量的散列表急膀【谛可以用紅黑樹(shù)代替鏈表來(lái)優(yōu)化）來(lái)解決。
當(dāng)散列表中空閑位置不多的時(shí)候卓嫂，散列沖突的概率就會(huì)大大提高皂股。為了保證散列表的操作效率，一般情況下會(huì)保證散列表有一定比例的空閑槽位命黔。

②哈希算法

將任意長(zhǎng)度的二進(jìn)制值串映射為固定長(zhǎng)度的二進(jìn)制值串呜呐，這個(gè)映射的規(guī)則就是哈希算法，而通過(guò)原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值悍募。

哈希算法常見(jiàn)應(yīng)用：

• 安全加密（MD5蘑辑、SHA等）

• 唯一標(biāo)識(shí)
  對(duì)大數(shù)據(jù)做信息摘要，通過(guò)一個(gè)較短的二進(jìn)制編碼來(lái)表示很大的數(shù)據(jù)坠宴。

• 數(shù)據(jù)校驗(yàn)
  校驗(yàn)數(shù)據(jù)的完整性和正確性洋魂。如HTTPS中通過(guò)摘要算法保證數(shù)據(jù)的完整性

• 散列函數(shù)
  散列函數(shù)中用到的散列算法更加看重的是散列的平均性和哈希算法的執(zhí)行效率

• 負(fù)載均衡
  通過(guò)哈希算法，對(duì)客戶(hù)端 IP 地址或者會(huì)話 ID 計(jì)算哈希值，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算副砍，最終得到應(yīng)該被路由到的服務(wù)器編號(hào)衔肢。
  這樣就可以把同一個(gè) IP 過(guò)來(lái)的所有請(qǐng)求，都路由到同一個(gè)后端服務(wù)器上豁翎，實(shí)現(xiàn)會(huì)話粘滯（session sticky）角骤。

• 數(shù)據(jù)分片
  通過(guò)哈希算法對(duì)數(shù)據(jù)分片，以實(shí)現(xiàn)采用多機(jī)分布式處理海量數(shù)據(jù)

• 分布式存儲(chǔ)
  針對(duì)海量數(shù)據(jù)的緩存心剥，可以通過(guò)哈希算法對(duì)數(shù)據(jù)取哈希值邦尊，然后對(duì)機(jī)器個(gè)數(shù)取模，得到應(yīng)該存儲(chǔ)的緩存機(jī)器編號(hào)优烧。
  這種方法有個(gè)缺點(diǎn)就是當(dāng)擴(kuò)容或縮容蝉揍，所有的數(shù)據(jù)都要重新計(jì)算哈希值，然后重新搬移到正確的機(jī)器上畦娄。相當(dāng)于緩存中的數(shù)據(jù)都失效了又沾，可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫(kù)熙卡≌人ⅲ可以采用一致性哈希算法來(lái)解決。

③散列表和二叉查找樹(shù)比較

• 散列表插入再膳、刪除挺勿、查找的時(shí)間復(fù)雜度是O(1)曲横，而二叉查找樹(shù)在比較平衡的基礎(chǔ)上才能做到O(logN)喂柒。
• 但是散列表的數(shù)據(jù)是無(wú)序的，二叉查找樹(shù)可以通過(guò)中序遍歷在O(N)的時(shí)間復(fù)雜度內(nèi)獲得有序的數(shù)據(jù)禾嫉。
• 散列表擴(kuò)容耗時(shí)多灾杰，遇到散列沖突時(shí)，性能不穩(wěn)定熙参。平衡二叉樹(shù)性能穩(wěn)定艳吠，時(shí)間復(fù)雜度穩(wěn)定在 O(logn)。

④為什么散列表經(jīng)常和鏈表一起使用（如LinkedHashMap）孽椰？

• 散列表數(shù)據(jù)存儲(chǔ)是無(wú)序的昭娩，無(wú)法支持按照某種順序快速地遍歷數(shù)據(jù)。如果希望按照順序遍歷散列表中的數(shù)據(jù)黍匾，需要將散列表中的數(shù)據(jù)拷貝到數(shù)組中栏渺，然后排序，再遍歷锐涯】恼铮可以通過(guò)維護(hù)一個(gè)鏈表維持順序，實(shí)現(xiàn)LRU淘汰算法。
• 借助散列表和雙向鏈表可以實(shí)現(xiàn)O(1)的查詢(xún)霎终、刪除操作

4.排序算法

(1)非線性排序算法

ps：為了兼顧任意規(guī)模數(shù)據(jù)的排序莱褒，一般都會(huì)首選時(shí)間復(fù)雜度是 O(nlogn) 的排序算法來(lái)實(shí)現(xiàn)排序函數(shù)击困。

(2)線性排序算法

ps：桶排序中時(shí)間復(fù)雜度沛励、是否原地排序、是否穩(wěn)定取決于桶內(nèi)選取的排序算法炮障；桶排序其實(shí)是一種算法思想目派；計(jì)數(shù)排序是一種特殊的桶排序

5.字符串匹配算法

(1)單模式串匹配（在一個(gè)主串中查找一個(gè)模式串）

①BF（Brute Force）算法

暴力匹配/樸素匹配算法。

思路：把主串的長(zhǎng)度記作 n胁赢，模式串的長(zhǎng)度記作 m企蹭。在主串中，檢查起始位置分別是 0智末、1谅摄、2…n-m 且長(zhǎng)度為 m 的 n-m+1 個(gè)子串，看有沒(méi)有跟模式串匹配的系馆。

時(shí)間復(fù)雜度：

最壞情況時(shí)間復(fù)雜度是 O(n*m)送漠。

適用場(chǎng)景:

適合主串和模式串都不太長(zhǎng)的情況。在實(shí)際的軟件開(kāi)發(fā)中由蘑，絕大部分情況下闽寡，樸素的字符串匹配算法就夠用了。

②RK算法

RK 算法是借助哈希算法對(duì) BF 算法進(jìn)行改造尼酿。

思路：對(duì)主串中每個(gè)子串分別求哈希值爷狈，然后拿子串的哈希值與模式串的哈希值比較，減少了比較的時(shí)間裳擎。

時(shí)間復(fù)雜度：

O(n)涎永。極端情況下，如果哈希算法存在大量的沖突鹿响，每次都要再對(duì)比子串和模式串本身羡微，那時(shí)間復(fù)雜度就會(huì)退化成 O(n*m)。

適用場(chǎng)景：

字符集范圍不要太大且模式串不要太長(zhǎng)惶我， 否則hash值可能沖突妈倔。但設(shè)計(jì)一個(gè)良好的哈希算法會(huì)比較困難。

③BM算法

借助“壞字符規(guī)則”和“好后綴規(guī)則”指孤，在每一輪比較時(shí)启涯，讓模式串盡可能多移動(dòng)幾位贬堵，減少無(wú)謂的比較。

a.壞字符規(guī)則

從模式串的末尾往前倒著匹配结洼，當(dāng)發(fā)現(xiàn)某個(gè)字符沒(méi)法匹配的時(shí)候黎做。把這個(gè)沒(méi)有匹配的字符叫作壞字符（主串中的字符）。
ps：壞字符的位置越靠右松忍，下一輪模式串的挪動(dòng)跨度就可能越長(zhǎng)蒸殿，節(jié)省的比較次數(shù)也就越多。這就是BM算法從右向左檢測(cè)的好處鸣峭。

把壞字符對(duì)應(yīng)的模式串中的字符下標(biāo)記作 si宏所。如果壞字符在模式串中存在，把這個(gè)壞字符在模式串中的下標(biāo)記作xi摊溶。如果不存在爬骤， xi 記作 -1。模式串往后移動(dòng)的位數(shù)就等于 si-xi莫换。如果壞字符在模式串里多處出現(xiàn)霞玄，選擇最靠后的那個(gè)作為xi 。

時(shí)間復(fù)雜度：

利用壞字符規(guī)則拉岁，BM 算法最好時(shí)間復(fù)雜度是 O(n/m)坷剧。【 n是主串長(zhǎng)度喊暖，m是模式串長(zhǎng)度 】

單純使用壞字符規(guī)則還是不夠的惫企。因?yàn)楦鶕?jù) si-xi 計(jì)算出來(lái)的移動(dòng)位數(shù)，有可能是負(fù)數(shù)陵叽，比如主串是 aaaaaaaaaaaaaaaa狞尔，模式串是 baaa。不但不會(huì)向后滑動(dòng)模式串咨跌，還有可能倒退沪么。

b.好后綴規(guī)則

遇到無(wú)法匹配的壞字符后硼婿，看好后綴在模式串中锌半，是否有另一個(gè)匹配的子串。如果有寇漫，則按如下滑動(dòng)：

如果沒(méi)有則從好后綴的后綴子串中刊殉，找一個(gè)最長(zhǎng)的并且能跟模式串的前綴子串匹配的。

時(shí)間復(fù)雜度：

好后綴預(yù)處理最壞時(shí)間復(fù)雜度O(m * m)州胳，匹配O(n)【m是模式串長(zhǎng)度记焊，n是主串長(zhǎng)度】

如何運(yùn)用壞字符和好后綴規(guī)則？

分別計(jì)算好后綴和壞字符往后滑動(dòng)的位數(shù)栓撞，然后取兩個(gè)數(shù)中最大的遍膜，作為模式串往后滑動(dòng)的位數(shù)碗硬。這種處理方法可以避免根據(jù)壞字符規(guī)則計(jì)算得到的往后滑動(dòng)的位數(shù)有可能是負(fù)數(shù)的情況。
好后綴規(guī)則可以獨(dú)立于壞字符規(guī)則使用瓢颅。因?yàn)閴淖址?guī)則的實(shí)現(xiàn)比較耗內(nèi)存恩尾，為了節(jié)省內(nèi)存，可以只用好后綴規(guī)則來(lái)實(shí)現(xiàn) BM 算法挽懦，但算法效率就會(huì)下降一些翰意。

適用場(chǎng)景：

壞字符規(guī)則需要占用較多的空間，適合字符集不是很大的情況信柿。
壞字符和好后綴都需要對(duì)模式串進(jìn)行預(yù)處理冀偶，所以模式串最好不要太長(zhǎng)。

④KMP算法

KMP算法與BM算法類(lèi)似渔嚷，也是讓模式串盡可能多移動(dòng)幾位进鸠，減少無(wú)謂的比較，KMP算法重點(diǎn)放在已匹配前綴上形病。

思路：在模式串和主串匹配的過(guò)程中堤如，當(dāng)遇到壞字符后，對(duì)于已經(jīng)比對(duì)過(guò)的好前綴窒朋，在好前綴的后綴子串中搀罢，查找最長(zhǎng)的那個(gè)可以跟好前綴的前綴子串匹配的。假設(shè)最長(zhǎng)的可匹配的那部分前綴子串是{v}侥猩，長(zhǎng)度是 k榔至。把模式串一次性往后滑動(dòng) j-k 位，相當(dāng)于欺劳，每次遇到壞字符的時(shí)候唧取，就把 j 更新為 k，i 不變划提，然后繼續(xù)比較枫弟。

時(shí)間復(fù)雜度：

O(m+n)（其中構(gòu)建next數(shù)組是O(m)，借助next數(shù)組匹配是O(n)）【m是模式串長(zhǎng)度鹏往，n是主串長(zhǎng)度】淡诗。

可結(jié)合小灰大牛這篇來(lái)食用：
漫畫(huà)：什么是KMP算法？

(2)多模式串匹配（在一個(gè)主串中查找多個(gè)模式串）

①Trie 樹(shù)

Trie 樹(shù)的本質(zhì)伊履，就是利用字符串之間的公共前綴韩容，將重復(fù)的前綴合并在一起。

其中唐瀑，根節(jié)點(diǎn)不包含任何信息群凶。每個(gè)節(jié)點(diǎn)表示一個(gè)字符串中的字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)的一條路徑表示一個(gè)字符串（注意：紅色節(jié)點(diǎn)并不都是葉子節(jié)點(diǎn)）哄辣。

時(shí)間復(fù)雜度：

構(gòu)建 Trie 樹(shù)的過(guò)程请梢，需要掃描所有的字符串赠尾，時(shí)間復(fù)雜度是 O(n)【n 表示所有字符串的長(zhǎng)度和 】。
構(gòu)建好 Trie 樹(shù)后毅弧，在其中查找字符串的時(shí)間復(fù)雜度是 O(k)【k 表示要查找的字符串的長(zhǎng)度】萍虽。

空間復(fù)雜度：

空間復(fù)雜度取決于子節(jié)點(diǎn)存儲(chǔ)大小。Trie 樹(shù)有可能很浪費(fèi)內(nèi)存形真，為了解決內(nèi)存問(wèn)題杉编，可以稍微犧牲一點(diǎn)查詢(xún)的效率，將每個(gè)節(jié)點(diǎn)中的數(shù)組換成其他數(shù)據(jù)結(jié)構(gòu)咆霜，來(lái)存儲(chǔ)一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)指針邓馒。比如有序數(shù)組、跳表蛾坯、散列表光酣、紅黑樹(shù)等。

適用場(chǎng)景:

精確匹配查找更適合用散列表或者紅黑樹(shù)來(lái)解決脉课，Trie 樹(shù)比較適合的是查找前綴匹配的字符串救军，適合多模式串公共前綴較多的匹配，如實(shí)現(xiàn)搜索關(guān)鍵詞的提示功能倘零。

②AC 自動(dòng)機(jī)

AC 自動(dòng)機(jī)實(shí)際上就是在 Trie 樹(shù)之上唱遭，加了類(lèi)似 KMP 的 next 數(shù)組，只不過(guò)此處的 next 數(shù)組是構(gòu)建在樹(shù)上呈驶。

時(shí)間復(fù)雜度：

構(gòu)建Trie 樹(shù)的時(shí)間復(fù)雜度是 O(m * len)【 len 表示敏感詞的平均長(zhǎng)度拷泽，m 表示敏感詞的個(gè)數(shù)】。
失敗指針的構(gòu)建過(guò)程就是 O(k * len)【 k是 Trie 樹(shù)中總的節(jié)點(diǎn)個(gè)數(shù)】袖瞻。
AC 自動(dòng)機(jī)做匹配的時(shí)間復(fù)雜度O(n * len)司致，因?yàn)槊舾性~并不會(huì)很長(zhǎng)，實(shí)際情況下聋迎，可能近似于 O(n)脂矫。【n是主串長(zhǎng)度】

適用場(chǎng)景:

適合大量文本中多模式串的精確匹配查找霉晕，如敏感詞過(guò)濾

6.二分查找

(1)特點(diǎn)

二分查找依賴(lài)的是順序表結(jié)構(gòu)庭再，也就是數(shù)組，并且針對(duì)的是有序數(shù)據(jù)娄昆。時(shí)間復(fù)雜度為O(logN)佩微。

(2)使用場(chǎng)景

①二分查找只能用在插入缝彬、刪除操作不頻繁萌焰，一次排序多次查找的場(chǎng)景中
②數(shù)據(jù)量太小不適合，此時(shí)使用順序查找就足夠了谷浅。數(shù)據(jù)量太大也不適合扒俯，二分查找的底層需要依賴(lài)數(shù)組這種數(shù)據(jù)結(jié)構(gòu)奶卓，而數(shù)組為了支持隨機(jī)訪問(wèn)的特性，要求內(nèi)存空間連續(xù)撼玄，對(duì)內(nèi)存的要求比較苛刻夺姑。
③如果數(shù)據(jù)之間的比較操作非常耗時(shí)，不管數(shù)據(jù)量大小掌猛，推薦使用二分查找盏浙。比如對(duì)于大字符串間的比較，可以盡量減少比較次數(shù)

7.其他算法思想

(1)貪心算法

貪心算法實(shí)際上是動(dòng)態(tài)規(guī)劃算法的一種特殊情況荔茬。針對(duì)一組數(shù)據(jù)废膘，定義了限制值和期望值，希望從中選出幾個(gè)數(shù)據(jù)慕蔚，在滿(mǎn)足限制值的情況下丐黄，期望值最大。

適用場(chǎng)景：

指導(dǎo)設(shè)計(jì)基礎(chǔ)算法孔飒。比如Prim 和 Kruskal 最小生成樹(shù)算法 灌闺、Dijkstra 單源最短路徑算法、霍夫曼編碼（Huffman Coding）（一種十分有效的編碼方法坏瞄，廣泛用于數(shù)據(jù)壓縮中）桂对。

(2)分治算法

分治算法（divide and conquer）的核心思想是分而治之 ，也就是將原問(wèn)題劃分成 n 個(gè)規(guī)模較小鸠匀，并且結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題接校，遞歸地解決這些子問(wèn)題，然后再合并其結(jié)果狮崩，就得到原問(wèn)題的解蛛勉。

分治算法一般都比較適合用遞歸來(lái)實(shí)現(xiàn)。

適用場(chǎng)景：

用來(lái)指導(dǎo)編碼睦柴，降低問(wèn)題求解的時(shí)間復(fù)雜度（如歸并排序求逆序?qū)Γ?br> 解決海量數(shù)據(jù)處理問(wèn)題诽凌。比如 MapReduce 本質(zhì)上就是利用了分治思想。

(3)回溯算法

回溯相當(dāng)于窮舉搜索坦敌。窮舉所有的解侣诵，找到滿(mǎn)足期望的解。通過(guò)把問(wèn)題求解的過(guò)程分為多個(gè)階段狱窘。每個(gè)階段杜顺，我們都會(huì)面對(duì)一個(gè)岔路口，我們先隨意選一條路走蘸炸，當(dāng)發(fā)現(xiàn)這條路走不通的時(shí)候（不符合期望的解）躬络，就回退到上一個(gè)岔路口，另選一種走法繼續(xù)走搭儒。
時(shí)間復(fù)雜度非常高穷当，是指數(shù)級(jí)別的提茁。

適用場(chǎng)景：

用來(lái)解決廣義的搜索問(wèn)題：從一組可能的解中，選擇出一個(gè)滿(mǎn)足要求的解馁菜。（如八皇后茴扁、0-1背包問(wèn)題、正則表達(dá)式匹配等）
時(shí)間復(fù)雜度高汪疮，只能用來(lái)解決小規(guī)模數(shù)據(jù)的問(wèn)題峭火。
適合用遞歸來(lái)實(shí)現(xiàn)，在實(shí)現(xiàn)的過(guò)程中智嚷，剪枝操作是提高回溯效率的一種技巧躲胳。利用剪枝，我們并不需要窮舉搜索所有的情況纤勒，從而提高搜索效率坯苹。

(4)動(dòng)態(tài)規(guī)劃

把問(wèn)題分解為多個(gè)階段，每個(gè)階段對(duì)應(yīng)一個(gè)決策摇天。我們記錄每一個(gè)階段可達(dá)的狀態(tài)集合（去掉重復(fù)的）粹湃，然后通過(guò)當(dāng)前階段的狀態(tài)集合，來(lái)推導(dǎo)下一個(gè)階段的狀態(tài)集合泉坐，動(dòng)態(tài)地往前推進(jìn)为鳄。
動(dòng)態(tài)規(guī)劃是一種空間換時(shí)間的算法思想。執(zhí)行效率較回溯高腕让，但是空間復(fù)雜度也高孤钦。

能解決的問(wèn)題

符合一個(gè)模型，三個(gè)特征的問(wèn)題纯丸。

• 一個(gè)模型
  多階段決策最優(yōu)解模型偏形。解決問(wèn)題的過(guò)程，需要經(jīng)歷多個(gè)決策階段觉鼻。每個(gè)決策階段都對(duì)應(yīng)著一組狀態(tài)俊扭。然后我們尋找一組決策序列，經(jīng)過(guò)這組決策序列坠陈，能夠產(chǎn)生最終期望求解的最優(yōu)值萨惑。
• 三個(gè)特征
  最優(yōu)子結(jié)構(gòu)：可以通過(guò)子問(wèn)題的最優(yōu)解，推導(dǎo)出問(wèn)題的最優(yōu)解仇矾。后面階段的狀態(tài)可以通過(guò)前面階段的狀態(tài)推導(dǎo)出來(lái)庸蔼。
  無(wú)后效性：在推導(dǎo)后面階段的狀態(tài)的時(shí)候，只關(guān)心前面階段的狀態(tài)值贮匕，不關(guān)心這個(gè)狀態(tài)是怎么一步一步推導(dǎo)出來(lái)的姐仅；某階段狀態(tài)一旦確定，就不受之后階段的決策影響。
  重復(fù)子問(wèn)題：不同的決策序列萍嬉，到達(dá)某個(gè)相同的階段時(shí)乌昔，可能會(huì)產(chǎn)生重復(fù)的狀態(tài)

解題思路

• 狀態(tài)轉(zhuǎn)移表法：回溯算法實(shí)現(xiàn) - 定義狀態(tài) - 畫(huà)遞歸樹(shù) - 找重復(fù)子問(wèn)題 - 畫(huà)狀態(tài)轉(zhuǎn)移表 - 根據(jù)遞推關(guān)系填表 - 將填表過(guò)程翻譯成代碼
• 狀態(tài)轉(zhuǎn)移方程法：找最優(yōu)子結(jié)構(gòu) - 寫(xiě)狀態(tài)轉(zhuǎn)移方程 - 將狀態(tài)轉(zhuǎn)移方程翻譯成代碼

適用場(chǎng)景：

用來(lái)求解最優(yōu)問(wèn)題隙疚，比如求最大值壤追、最小值等等。