計(jì)算機(jī)編程之美：數(shù)據(jù)結(jié)構(gòu)與算法之美+設(shè)計(jì)模式之美

《數(shù)據(jù)結(jié)構(gòu)與算法之美（全彩印刷）》

目錄

第 1章　復(fù)雜度分析　1

1.1　復(fù)雜度分析（上）：如何分析代碼的執(zhí)行效率和資源消耗　2

1.1.1　復(fù)雜度分析的意義　2

1.1.2　大O復(fù)雜度表示法　2

1.1.3　時(shí)間復(fù)雜度分析方法　4

1.1.4　幾種常見的時(shí)間復(fù)雜度量級(jí)　5

1.1.5　空間復(fù)雜度分析方法　7

1.1.6　內(nèi)容小結(jié)　7

1.1.7　思考題　8

1.2　復(fù)雜度分析（下）：詳解最好、最壞、平均、均攤這4種時(shí)間復(fù)雜度　8

1.2.1　最好時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度　8

1.2.2　平均時(shí)間復(fù)雜度　9

1.2.3　均攤時(shí)間復(fù)雜度　10

1.2.4　內(nèi)容小結(jié)　11

1.2.5　思考題　12

第 2章　數(shù)組、鏈表、棧和隊(duì)列　13

2.1　數(shù)組（上）：為什么數(shù)組的下標(biāo)一般從0開始編號(hào)　14

2.2　數(shù)組（下）：數(shù)據(jù)結(jié)構(gòu)中的數(shù)組和編程語言中的數(shù)組的區(qū)別　19

2.3　鏈表（上）：如何基于鏈表實(shí)現(xiàn)LRU緩存淘汰算法　23

2.4　鏈表（下）：借助哪些技巧可以輕松地編寫鏈表相關(guān)的復(fù)雜代碼　30

2.5　棧：如何實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能　35

2.6　隊(duì)列：如何實(shí)現(xiàn)線程池等有限資源池的請(qǐng)求排隊(duì)功能　40

第3章　遞歸、排序、二分查找　46

3.1　遞歸：如何用3行代碼找到“Z終推薦人”　47

3.2　尾遞歸：如何借助尾遞歸避免遞歸過深導(dǎo)致的堆棧溢出　53

3.3　排序算法基礎(chǔ)：從哪幾個(gè)方面分析排序算法　55

3.4　O(n2)排序：為什么插入排序比冒泡排序更受歡迎　58

3.5　O(nlogn)排序：如何借助快速排序思想快速查找第K大元素　64

3.6　線性排序：如何根據(jù)年齡給100萬個(gè)用戶排序　72

3.7　排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)高性能的通用的排序函數(shù)　78

3.8　二分查找：如何用Z省內(nèi)存的方式實(shí)現(xiàn)快速查找功能　80

3.9　二分查找的變體：如何快速定位IP地址對(duì)應(yīng)的歸屬地　85

第4章　哈希表、位圖和哈希算法　91

4.1　哈希表（上）：Word軟件的單詞拼寫檢查功能是如何實(shí)現(xiàn)的　92

4.2　哈希表（中）：如何打造一個(gè)工業(yè)級(jí)的哈希表　96

4.3　哈希表（下）：如何利用哈希表優(yōu)化LRU緩存淘汰算法　101

4.4　位圖：如何實(shí)現(xiàn)網(wǎng)頁“爬蟲”中的網(wǎng)址鏈接去重功能　106

4.5　哈希算法：如何防止數(shù)據(jù)庫脫庫后用戶信息泄露　111

第5章　樹　117

5.1　樹和二叉樹：什么樣的二叉樹適合用數(shù)組存儲(chǔ)　118

5.2　二叉查找樹：相比哈希表，二叉查找樹有何優(yōu)勢(shì)　122

5.3　平衡二叉查找樹：為什么紅黑樹如此受歡迎　128

5.4　遞歸樹：如何借助樹求遞歸算法的時(shí)間復(fù)雜度　131

5.5　B+樹：MySQL數(shù)據(jù)庫索引是如何實(shí)現(xiàn)的　135

第6章　堆　141

6.1　堆：如何維護(hù)動(dòng)態(tài)集合的最值　142

6.2　堆排序：為什么說堆排序沒有快速排序快　147

6.3　堆的應(yīng)用：如何快速獲取Top 10熱門搜索關(guān)鍵詞　151

第7章　跳表、并查集、線段樹和樹狀數(shù)組　157

7.1　跳表：Redis中的有序集合類型是如何實(shí)現(xiàn)的　158

7.2　并查集：路徑壓縮和按秩合并這兩個(gè)優(yōu)化是否沖突　163

7.3　線段樹：如何查找獵聘網(wǎng)中積分排在第K位的獵頭　168

7.4　樹狀數(shù)組：如何實(shí)現(xiàn)一個(gè)高性能、低延遲的實(shí)時(shí)排行榜　174

第8章　字符串匹配算法　179

8.1　BF算法：編程語言中的查找、替換函數(shù)是怎樣實(shí)現(xiàn)的　180

8.2　RK算法：如何借助哈希算法實(shí)現(xiàn)高效的字符串匹配　182

8.3　BM算法：如何實(shí)現(xiàn)文本編輯器中的查找和替換功能　185

8.4　KMP算法：如何借助BM算法理解KMP算法　194

8.5　Trie樹：如何實(shí)現(xiàn)搜索引擎的搜索關(guān)鍵詞提示功能　198

8.6　AC自動(dòng)機(jī)：如何用多模式串匹配實(shí)現(xiàn)敏感詞過濾　204

第9章　圖　210

9.1　圖的表示：如何存儲(chǔ)微博、微信等社交網(wǎng)絡(luò)中的好友關(guān)系　211

9.2　深度優(yōu)先搜索和廣度優(yōu)先搜索：如何找出社交網(wǎng)絡(luò)中的三度好友關(guān)系　216

9.3　拓?fù)渑判颍喝绾未_定代碼源文件的編譯依賴關(guān)系　221

9.4　單源Z短路徑：地圖軟件如何“計(jì)算”Z優(yōu)出行路線　225

9.5　多源Z短路徑：如何利用Floyd算法解決傳遞閉包問題　231

9.6　啟發(fā)式搜索：如何用A*算法實(shí)現(xiàn)游戲中的尋路功能　233

9.7　Z小生成樹：如何隨機(jī)生成游戲中的迷宮地圖　238

9.8　Z大流：如何解決單身交友聯(lián)誼中的Z多匹配問題　245

第 10章　貪心、分治、回溯和動(dòng)態(tài)規(guī)劃　251

10.1　貪心算法：如何利用貪心算法實(shí)現(xiàn)霍夫曼編碼　252

10.2　分治算法：談一談大規(guī)模計(jì)算框架MapReduce中的分治思想　256

10.3　回溯算法：從電影《蝴蝶效應(yīng)》中學(xué)習(xí)回溯算法的核心思想　260

10.4　初識(shí)動(dòng)態(tài)規(guī)劃：如何巧妙解決“雙11”購(gòu)物時(shí)的湊單問題　264

10.5　動(dòng)態(tài)規(guī)劃理論：徹底理解最優(yōu)子結(jié)構(gòu)、無后效性和重復(fù)子問題　272

10.6　動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：如何實(shí)現(xiàn)搜索引擎中的拼寫糾錯(cuò)功能　278

第 11章　數(shù)據(jù)結(jié)構(gòu)和算法實(shí)戰(zhàn)　284

11.1　實(shí)戰(zhàn)1：剖析Redis的常用數(shù)據(jù)類型對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)　285

11.2　實(shí)戰(zhàn)2：剖析搜索引擎背后的經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法　288

11.3　實(shí)戰(zhàn)3：剖析微服務(wù)鑒權(quán)和限流背后的數(shù)據(jù)結(jié)構(gòu)和算法　293

11.4　實(shí)戰(zhàn)4：用學(xué)過的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)短網(wǎng)址服務(wù)　299

附錄A　思考題答案　304

《設(shè)計(jì)模式之美》

第 1章概述　1

1.1　為什么學(xué)習(xí)代碼設(shè)計(jì)　2

1.1.1　編寫高質(zhì)量的代碼　2

1.1.2　應(yīng)對(duì)復(fù)雜代碼的開發(fā)　2

1.1.3　程序員的基本功　3

1.1.4　職場(chǎng)發(fā)展的必備技能　4

1.1.5　思考題　4

1.2　如何評(píng)價(jià)代碼質(zhì)量　4

1.2.1　可維護(hù)性（maintainability）　5

1.2.2　可讀性（readability）　6

1.2.3　可擴(kuò)展性（extensibility）　6

1.2.4　靈活性（flexibility）　6

1.2.5　簡(jiǎn)潔性（simplicity）　7

1.2.6　可復(fù)用性（reusability）　7

1.2.7　可測(cè)試性（testability）　7

1.2.8　思考題　8

1.3　如何寫出高質(zhì)量代碼　8

1.3.1　面向?qū)ο蟆?

1.3.2　設(shè)計(jì)原則　8

1.3.3　設(shè)計(jì)模式　9

1.3.4　代碼規(guī)范　9

1.3.5　重構(gòu)技巧　10

1.3.6　思考題　11

1.4　如何避免過度設(shè)計(jì)　 11

1.4.1　代碼設(shè)計(jì)的初衷是提高代碼質(zhì)量　11

1.4.2　代碼設(shè)計(jì)的原則是“先有問題，后有方案”　12

1.4.3　代碼設(shè)計(jì)的應(yīng)用場(chǎng)景是復(fù)雜代碼　12

1.4.4　持續(xù)重構(gòu)可有效避免過度設(shè)計(jì)　12

1.4.5　不要脫離具體的場(chǎng)景談代碼設(shè)計(jì)　13

1.4.6　思考題　13

第 2章面向?qū)ο缶幊谭妒健?4

2.1　當(dāng)我們?cè)谡務(wù)撁嫦驅(qū)ο髸r(shí)，到底在談?wù)撌裁础?5

2.2　封裝、抽象、繼承和多態(tài)為何而生　17

2.3　如何進(jìn)行面向?qū)ο蠓治?、面向?qū)ο笤O(shè)計(jì)和面向?qū)ο缶幊獭?5

2.4　面向?qū)ο缶幊膛c面向過程編程和函數(shù)式編程之間的區(qū)別　35

2.5　哪些代碼看似面向?qū)ο缶幊田L(fēng)格，實(shí)則面向過程編程風(fēng)格　45

2.6　基于“貧血”模型的傳統(tǒng)開發(fā)模式是否違背OOP　51

2.7　接口和抽象類：如何使用普通類模擬接口和抽象類　59

2.8　基于接口而非實(shí)現(xiàn)編程：有沒有必要為每個(gè)類都定義接口　65

2.9　組合優(yōu)于繼承：什么情況下可以使用繼承　70

第3章設(shè)計(jì)原則　75

3.1　單一職責(zé)原則：如何判定某個(gè)類的職責(zé)是否單一　76

3.2　開閉原則：只要修改代碼，就一定違反開閉原則嗎　79

3.3　里氏替換原則：什么樣的代碼才算違反里氏替換原則　86

3.4　接口隔離原則：如何理解該原則中的“接口”　89

3.5　依賴反轉(zhuǎn)原則：依賴反轉(zhuǎn)與控制反轉(zhuǎn)、依賴注入有何關(guān)系　97

3.6　KISS原則和YAGNI原則：二者是一回事嗎　100

3.7　DRY原則：相同的兩段代碼就一定違反DRY原則嗎　104

3.8　LoD：如何實(shí)現(xiàn)代碼的“高內(nèi)聚、低耦合”　110

第4章代碼規(guī)范　117

4.1　命名與注釋：如何精準(zhǔn)命名和編寫注釋　118

4.2　代碼風(fēng)格：與其爭(zhēng)論標(biāo)準(zhǔn)，不如團(tuán)隊(duì)統(tǒng)一　121

4.3　編程技巧：小技巧，大作用，一招提高代碼的可讀性　123

第5章重構(gòu)技巧　130

5.1　重構(gòu)四要素：目的、對(duì)象、時(shí)機(jī)和方法　131

5.2　單元測(cè)試：保證重構(gòu)不出錯(cuò)的有效手段　133

5.3　代碼的可測(cè)試性：如何編寫可測(cè)試代碼　139

5.4　解耦：哪些方法可以用來解耦代碼　147

5.5　重構(gòu)案例：將ID生成器代碼從“能用”重構(gòu)為“好用”　150

第6章創(chuàng)建型設(shè)計(jì)模式　166

6.1　單例模式（上）：為什么不推薦在項(xiàng)目中使用單例模式　167

6.2　單例模式（下）：如何設(shè)計(jì)實(shí)現(xiàn)一個(gè)分布式單例模式　177

6.3　工廠模式（上）：如何解耦復(fù)雜對(duì)象的創(chuàng)建和使用　180

6.4　工廠模式（下）：如何設(shè)計(jì)實(shí)現(xiàn)一個(gè)依賴注入容器　188

6.5　建造者模式：什么情況下必須用建造者模式創(chuàng)建對(duì)象　194

6.6　原型模式：如何快速?gòu)?fù)制（clone）一個(gè)哈希表　200

第7章結(jié)構(gòu)型設(shè)計(jì)模式　208

7.1　代理模式：代理模式在RPC、緩存和監(jiān)控等場(chǎng)景中的應(yīng)用　209

7.2　裝飾器模式：剖析Java IO類庫的底層設(shè)計(jì)思想　213

7.3　適配器模式：如何利用適配器模式解決代碼的不兼容問題　219

7.4　橋接模式：如何將M×N的繼承關(guān)系簡(jiǎn)化為M+N的組合關(guān)系　230

7.5　門面模式：如何設(shè)計(jì)接口以兼顧接口的易用性和通用性　231

7.6　組合模式：一種應(yīng)用在樹形結(jié)構(gòu)上的特殊設(shè)計(jì)模式　233

7.7　享元模式：如何利用享元模式降低系統(tǒng)的內(nèi)存開銷　239

第8章行為型設(shè)計(jì)模式　249

8.1　觀察者模式：如何實(shí)現(xiàn)一個(gè)異步非阻塞的EventBus框架　250

8.2　模板方法模式（上）：模板方法模式在JDK、Servlet、JUnit中的應(yīng)用　261

8.3　模板方法模式（下）：模板方法模式與回調(diào)有何區(qū)別和聯(lián)系　267

8.4　策略模式：如何避免冗長(zhǎng)的if-else和switch-case語句　273

8.5　職責(zé)鏈模式：框架中的過濾器、攔截器和插件是如何實(shí)現(xiàn)的　282

8.6　狀態(tài)模式：游戲和工作流引擎中常用的狀態(tài)機(jī)是如何實(shí)現(xiàn)的　297

8.7　迭代器模式（上）：為什么要用迭代器遍歷集合　306

8.8　迭代器模式（下）：如何實(shí)現(xiàn)一個(gè)支持快照功能的迭代器　315

8.9　訪問者模式：為什么支持雙分派的編程語言不需要訪問者模式　320

8.10　備忘錄模式：如何優(yōu)雅地實(shí)現(xiàn)數(shù)據(jù)防丟失、撤銷和恢復(fù)功能　330

8.11　命令模式：如何設(shè)計(jì)實(shí)現(xiàn)基于命令模式的手游服務(wù)器　334

8.12　解釋器模式：如何設(shè)計(jì)實(shí)現(xiàn)一個(gè)自定義接口告警規(guī)則的功能　337

8.13　中介模式：什么時(shí)候使用中介模式？什么時(shí)候使用觀察者模式？　343