數(shù)據(jù)結(jié)構(gòu)是編程的基礎(chǔ)，所以它是計(jì)算機(jī)科學(xué)課程中一直講授的領(lǐng)域之一。然而，令人驚訝的是很容易錯(cuò)誤使用或者選擇錯(cuò)誤的數(shù)據(jù)結(jié)構(gòu)。在本文中，我們將引導(dǎo)你作為代碼審查者關(guān)注需要關(guān)注的那些事情--我們將通過(guò)一系列示例代碼來(lái)討論“壞的代碼味道”，這些“味道”可能暗示我們選擇了錯(cuò)誤的數(shù)據(jù)結(jié)構(gòu)或者是數(shù)據(jù)結(jié)構(gòu)被以錯(cuò)誤的方式使用。
列表（Lists）
這也許是最常用的數(shù)據(jù)結(jié)構(gòu)。因?yàn)槭亲畛Ｒ?jiàn)的選擇，它有時(shí)被用在了錯(cuò)誤的地方。
反模式：過(guò)多搜索
迭代列表本身當(dāng)然不是一件壞事情。但是如果要求迭代是一個(gè)常用操作（比如像上面代碼這樣通過(guò) ID 查找一個(gè)客戶），應(yīng)該有更好的數(shù)據(jù)結(jié)構(gòu)可以使用。在這個(gè)例子中，因?yàn)槲覀兂３Ｐ枰ㄟ^(guò) ID 查找某個(gè)特定的項(xiàng)目，也許創(chuàng)建一個(gè) ID-->Customer 的 map 更合適。
注意，在 Java 8 中以及其他支持更多表達(dá)式搜索的語(yǔ)言中，這一點(diǎn)可能沒(méi)有 for 循環(huán)那么明顯，但是問(wèn)題仍然存在。
反模式：頻繁重新排序
如果使用它們的默認(rèn)排序列表是很棒的，但是如果作為審查者你發(fā)現(xiàn)代碼中對(duì)列表重新排序，確認(rèn)一下使用列表是否合適。在上面的例子中，在第16行 twitterUsers 總是重新排序以后再返回。再次說(shuō)明，Java 8 使得這個(gè)操作看起來(lái)很簡(jiǎn)單，可能很容易忽略這個(gè)信號(hào)：
在這種情況下，鑒于 TwitterUser 是獨(dú)立的并且看起來(lái)你需要一個(gè)默認(rèn)已經(jīng)排序好的集合，你可能需要類似 TreeSet 這樣的數(shù)據(jù)結(jié)構(gòu)。
Maps
如果你選擇了正取的 key， map是一種對(duì)單個(gè)元素的訪問(wèn)只有 O(1)復(fù)雜度的多用途數(shù)據(jù)結(jié)構(gòu)。
反模式：Map 作為全局常量
map 是一個(gè)很好的通用數(shù)據(jù)結(jié)構(gòu)，以致可以用一個(gè)全局的 map 來(lái)讓其他類訪問(wèn)。
在上面的例子中，作者簡(jiǎn)單的將 CUSTOMERS 這個(gè) map 作為全局常量。CustomerUpdateService需要添加或者更新 customers 時(shí)就直接使用這個(gè) map。這看起來(lái)沒(méi)什么問(wèn)題，因?yàn)?CustomerUpdateService的職責(zé)就是負(fù)責(zé)添加和更新操作，這些操作最終會(huì)修改 map。問(wèn)題是當(dāng)其他類，尤其是系統(tǒng)中自其它模塊的類需要訪問(wèn)數(shù)據(jù)的時(shí)候：
在這里，訂購(gòu)服務(wù)是知道存儲(chǔ) customers 的數(shù)據(jù)結(jié)構(gòu)的。事實(shí)上，在上面的代碼中，作者已經(jīng)犯了一個(gè)錯(cuò)誤--他們沒(méi)有檢查 customer 是否為 null，所以第12行可能會(huì)引發(fā) NullPointerExeption。作為審查者，你應(yīng)該建議隱藏?cái)?shù)據(jù)結(jié)構(gòu)并提供合適的訪問(wèn)方法。那樣的話其他訪問(wèn)類會(huì)更容易理解，并且將管理 map 的復(fù)雜工作隱藏到 map 所屬的 CustomerRepository。另外，如果以后你想修改 customers 所使用的數(shù)據(jù)結(jié)構(gòu)，或者使用分布式緩存或其他的技術(shù)，相關(guān)的修改都會(huì)限制在 CustomerRepository，而不是遍及整個(gè)系統(tǒng)。這就是信息隱藏原則。
盡管修改以后的代碼并不短，你獲得了標(biāo)準(zhǔn)化以及集中的核心函數(shù)--例如，你知道在獲取一個(gè)不存在的 customer 信息時(shí)總會(huì)返回一個(gè)異常?；蛘吣阋部梢赃x擇返回一個(gè)新的 Optional 類型。
注意這是屬于在代碼審查中就應(yīng)該發(fā)現(xiàn)的一類問(wèn)題，如果一個(gè)全局變量的訪問(wèn)已經(jīng)遍及整個(gè)系統(tǒng)，需要隱藏它是比較困難的，但是當(dāng)它第一次被引入時(shí)還是很容易實(shí)現(xiàn)的。
其他的反模式：迭代和重新排序
和列表一樣，如果在 map 上進(jìn)行了大量的排序或者迭代操作，你應(yīng)該建議采用其他可替換的數(shù)據(jù)結(jié)構(gòu)。
Java 代碼需要特別關(guān)心的事情
在 Java 中，map 的行為依賴于 key 和 value 的 equals 和 hashCode 方法的實(shí)現(xiàn)。作為審查者，應(yīng)該檢查 key 和 value 類的這些方法，以確保獲得預(yù)期的行為。
Java 8 給 Map 接口添加了一些有用的方法。例如，上面代碼中的第11行使用的 getOrDefault方法可以簡(jiǎn)化 CustomerRepository 的代碼。
Sets
一個(gè)常常不被充分使用的數(shù)據(jù)結(jié)構(gòu)，它的優(yōu)點(diǎn)是不會(huì)包含重復(fù)的元素。
反模式：有時(shí)你真的需要重復(fù)元素
我們假設(shè)你有一個(gè) user 類，使用了 set 來(lái)跟蹤其訪問(wèn)過(guò)的網(wǎng)站?，F(xiàn)在有一個(gè)新的功能要求返回這些網(wǎng)站中最近訪問(wèn)的一個(gè)。
這段代碼的作者將跟蹤一個(gè)用戶訪問(wèn)網(wǎng)站的 set 從 HashSet 修改為 LinkedHashSet，后者的實(shí)現(xiàn)保留了插入順序，所以現(xiàn)在我們的 set 按照訪問(wèn)的順序跟蹤每一個(gè) URI。
然而這段代碼中有很多信號(hào)說(shuō)明它是錯(cuò)誤的。首先--由于 set 不是為按照位置訪問(wèn)設(shè)計(jì)的，為了獲取最后一個(gè)元素必須迭代整個(gè) set（第13-15行），這樣的訪問(wèn)開(kāi)銷太大，有時(shí)候 list 是一個(gè)完美的選擇。其次，由于 sets 中不包含重復(fù)的值，如果最后訪問(wèn)的頁(yè)面在之前已經(jīng)訪問(wèn)過(guò)，那么它在 set 中的位置并不在最后。相反，它會(huì)處在第一次被添加的位置。
在這個(gè)例子中，list 或者 stack（參考下文）或者就是一個(gè)簡(jiǎn)單的屬性都可以讓我們更好的獲得最后瀏覽過(guò)的頁(yè)面。
Java 需要特別注意
因?yàn)?set 的一個(gè)關(guān)鍵操作是 contains，作為審查者你應(yīng)該檢查 set 所包含的類型的 equals 方法實(shí)現(xiàn)。
棧（Stacks）
Stacks是計(jì)算機(jī)科學(xué)課程最喜歡的數(shù)據(jù)結(jié)構(gòu)之一，但是在現(xiàn)實(shí)世界中常常被忽略-在 Java 中，也許是因?yàn)?Stack 繼承自 Vector，所以有一點(diǎn)點(diǎn)過(guò)時(shí)。在這里我不討論具體的細(xì)節(jié)，只是列出一些關(guān)鍵的點(diǎn)：
- Stacks 支持 LIFO，所以非常適合 push/pop 操作，但是真的不適合迭代操作。
- Java 在1.6版本以后是使用 Deque來(lái)實(shí)現(xiàn) stack。它既可以作為 queue 又可以作為 stack 使用，所有審查者需要檢查 dequene 在代碼中的使用方式是一致的。
隊(duì)列（Queues）
計(jì)算機(jī)科學(xué)最喜歡的另一個(gè)數(shù)據(jù)結(jié)構(gòu)。Queues 常常在討論并發(fā)相關(guān)的話題時(shí)出現(xiàn)（確實(shí)，Java 中大多數(shù) Queue 的實(shí)現(xiàn)都在 java.util.concurrent 中使用），因?yàn)樗畛Ｒ?jiàn)的用法是在線程和模塊之間傳遞數(shù)據(jù)。
- 隊(duì)列是 FIFO 的數(shù)據(jù)結(jié)構(gòu)，通常在你想往尾部添加數(shù)據(jù)或者從頭部移除數(shù)據(jù)時(shí)非常合適。如果你在審查代碼是發(fā)現(xiàn)對(duì)隊(duì)列進(jìn)行迭代操作（特殊情況下訪問(wèn)隊(duì)列中間的元素），需要確認(rèn)一下隊(duì)列是否是正確的數(shù)據(jù)結(jié)構(gòu)。
- 隊(duì)列可以是限定大小的，也可以是不限定大小的。不限定大小的隊(duì)列可能會(huì)一直增長(zhǎng)，所以如果審查代碼時(shí)發(fā)現(xiàn)使用了不限定大小隊(duì)列，請(qǐng)注意我們?cè)?a href="http://www.itdecent.cn/p/8cf4f3fe5506" target="_blank">上一篇文章中討論的性能問(wèn)題。限定大小的隊(duì)列也有它的問(wèn)題--在審查代碼時(shí)，需要關(guān)注什么條件下隊(duì)列會(huì)滿，并且了解隊(duì)列滿的情況下系統(tǒng)會(huì)做出什么反應(yīng)。
Java 開(kāi)發(fā)者特別注意
作為審查者，你不僅僅要了解通用的數(shù)據(jù)結(jié)構(gòu)特性，還需要注意各種實(shí)現(xiàn)的優(yōu)點(diǎn)和弱點(diǎn)，這些知識(shí)在 Javadoc 中都有詳細(xì)的說(shuō)明：
如果你使用的是 Java8，記住很多集合類都添加了新的方法。作為審查者，你應(yīng)該意識(shí)到這一點(diǎn)--你可以在一些復(fù)雜的代碼中建議使用新的方法。
為什么要選擇正確的數(shù)據(jù)結(jié)構(gòu)？
我們已經(jīng)在這篇博客中討論了數(shù)據(jù)結(jié)構(gòu)--怎樣確定被審查的代碼是否使用了錯(cuò)誤的數(shù)據(jù)結(jié)構(gòu)，以及各種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)的要點(diǎn)，這樣作為審查者不僅僅可以確認(rèn)數(shù)據(jù)結(jié)構(gòu)沒(méi)有正確使用，而且可以給出更好的替代方案。我們一起來(lái)看一下為什么選擇正確的數(shù)據(jù)結(jié)構(gòu)如此重要。
性能
如果你在計(jì)算機(jī)科學(xué)課程中學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)，你應(yīng)該知道選擇數(shù)據(jù)結(jié)構(gòu)對(duì)性能的影響，事實(shí)上，我們?cè)谶@篇博客中甚至用“大O表示法”來(lái)強(qiáng)調(diào)特定數(shù)據(jù)結(jié)構(gòu)的某些優(yōu)點(diǎn)。在代碼中使用正確的數(shù)據(jù)結(jié)構(gòu)當(dāng)然會(huì)對(duì)性能有幫助，但是這不是選擇正確工具的唯一理由。
表述預(yù)期的行為
代碼的維護(hù)者，或者是使用你的系統(tǒng) API 的開(kāi)發(fā)者會(huì)根據(jù)數(shù)據(jù)結(jié)構(gòu)做出相應(yīng)的假設(shè)。如果一個(gè)方法調(diào)用通過(guò) list 返回?cái)?shù)據(jù)，開(kāi)發(fā)者會(huì)假設(shè)數(shù)據(jù)已經(jīng)以某種方式排序。如果是以 map 返回?cái)?shù)據(jù)，開(kāi)發(fā)者會(huì)假設(shè)會(huì)頻繁的根據(jù) key 查找單個(gè)元素。如果數(shù)據(jù)是以 set 返回，開(kāi)發(fā)者會(huì)假設(shè)一個(gè)元素只會(huì)存儲(chǔ)一次而不是多次。一個(gè)不錯(cuò)的建議是在這個(gè)假設(shè)內(nèi)工作而不是破壞它。
降低復(fù)雜性
任何開(kāi)發(fā)者，尤其是代碼審查者的總體目標(biāo)應(yīng)該是確保在最小的復(fù)雜度下代碼按照預(yù)期的行為工作-這樣可以使得代碼以后更易讀、更易理解、更容易修改、維護(hù)。在前面列出的一些反模式中（如錯(cuò)誤使用 Set），我們可以發(fā)現(xiàn)選擇錯(cuò)誤的數(shù)據(jù)結(jié)構(gòu)會(huì)導(dǎo)致編寫(xiě)更多的代碼。通常情況下選擇正確的數(shù)據(jù)結(jié)構(gòu)都會(huì)簡(jiǎn)化代碼。
總結(jié)
選擇正確的數(shù)據(jù)結(jié)構(gòu)不僅僅是為了獲取性能或者在同行面前看起來(lái)很聰明。還會(huì)產(chǎn)生更易理解、更易維護(hù)的代碼。代碼編寫(xiě)者選擇了錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)的一些常見(jiàn)信號(hào)：
- 頻繁通過(guò)迭代在一堆值中查找某幾個(gè)值
- 頻繁重新排序數(shù)據(jù)
- 沒(méi)有使用提供關(guān)鍵功能的方法--如棧的 push 或者 pop 方法
- 不管是讀還是寫(xiě)數(shù)據(jù)的代碼都很復(fù)雜
另外，不管是通過(guò)提供對(duì)數(shù)據(jù)結(jié)構(gòu)本身的全局訪問(wèn)，還是通過(guò)將類的接口緊密耦合到操作底層數(shù)據(jù)結(jié)構(gòu)來(lái)暴露所選數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)，都會(huì)導(dǎo)致很脆弱的設(shè)計(jì)，并且以后難以修改。 在代碼審查過(guò)程中應(yīng)盡早發(fā)現(xiàn)這些問(wèn)題，而不是產(chǎn)生可避免的技術(shù)債務(wù)。
