代碼審查應該關注什麼：數據結構

科技 06-04

前言

周五團隊分享會上有童鞋推薦了有興趣的童鞋可以去看看。今日早讀文章由@唐先僧翻譯分享。

這系列用的語言是java，不是javascript。

正文從這開始~

數據結構是編程的基礎，所以它是計算機科學課程中一直講授的領域之一。然而，令人驚訝的是很容易錯誤使用或者選擇錯誤的數據結構。在本文中，我們將引導你作為代碼審查者關注需要關注的那些事情--我們將通過一系列示例代碼來討論「壞的代碼味道」，這些「味道」可能暗示我們選擇了錯誤的數據結構或者是數據結構被以錯誤的方式使用。

列表（Lists）

這也許是最常用的數據結構。因為是最常見的選擇，它有時被用在了錯誤的地方。

反模式：過多搜索

迭代列表本身當然不是一件壞事情。但是如果要求迭代是一個常用操作（比如像上面代碼這樣通過 ID 查找一個客戶），應該有更好的數據結構可以使用。在這個例子中，因為我們常常需要通過 ID 查找某個特定的項目，也許創建一個 ID-->Customer 的 map 更合適。

注意，在 Java 8 中以及其他支持更多表達式搜索的語言中，這一點可能沒有 for 循環那麼明顯，但是問題仍然存在。

反模式：頻繁重新排序

如果使用它們的默認排序列表是很棒的，但是如果作為審查者你發現代碼中對列表重新排序，確認一下使用列表是否合適。在上面的例子中，在第16行 twitterUsers 總是重新排序以後再返回。再次說明，Java 8 使得這個操作看起來很簡單，可能很容易忽略這個信號：

在這種情況下，鑒於 TwitterUser 是獨立的並且看起來你需要一個默認已經排序好的集合，你可能需要類似 TreeSet 這樣的數據結構。

Maps

如果你選擇了正取的 key， map是一種對單個元素的訪問只有 O(1)複雜度的多用途數據結構。

反模式：Map 作為全局常量

map 是一個很好的通用數據結構，以致可以用一個全局的 map 來讓其他類訪問。

在上面的例子中，作者簡單的將 CUSTOMERS 這個 map 作為全局常量。CustomerUpdateService需要添加或者更新 customers 時就直接使用這個 map。這看起來沒什麼問題，因為 CustomerUpdateService的職責就是負責添加和更新操作，這些操作最終會修改 map。問題是當其他類，尤其是系統中自其它模塊的類需要訪問數據的時候：

在這裡，訂購服務是知道存儲 customers 的數據結構的。事實上，在上面的代碼中，作者已經犯了一個錯誤--他們沒有檢查 customer 是否為 null，所以第12行可能會引發 NullPointerExeption。作為審查者，你應該建議隱藏數據結構並提供合適的訪問方法。那樣的話其他訪問類會更容易理解，並且將管理 map 的複雜工作隱藏到 map 所屬的 CustomerRepository。另外，如果以後你想修改 customers 所使用的數據結構，或者使用分布式緩存或其他的技術，相關的修改都會限制在 CustomerRepository，而不是遍及整個系統。這就是信息隱藏原則。

儘管修改以後的代碼並不短，你獲得了標準化以及集中的核心函數--例如，你知道在獲取一個不存在的 customer 信息時總會返回一個異常。或者你也可以選擇返回一個新的 Optional 類型。

注意這是屬於在代碼審查中就應該發現的一類問題，如果一個全局變數的訪問已經遍及整個系統，需要隱藏它是比較困難的，但是當它第一次被引入時還是很容易實現的。

其他的反模式：迭代和重新排序

和列表一樣，如果在 map 上進行了大量的排序或者迭代操作，你應該建議採用其他可替換的數據結構。

Java 代碼需要特別關心的事情

在 Java 中，map 的行為依賴於 key 和 value 的 equals 和 hashCode 方法的實現。作為審查者，應該檢查 key 和 value 類的這些方法，以確保獲得預期的行為。

Java 8 給 Map 介面添加了一些有用的方法。例如，上面代碼中的第11行使用的 getOrDefault方法可以簡化 CustomerRepository 的代碼。

Sets

一個常常不被充分使用的數據結構，它的優點是不會包含重複的元素。

反模式：有時你真的需要重複元素

我們假設你有一個 user 類，使用了 set 來跟蹤其訪問過的網站。現在有一個新的功能要求返回這些網站中最近訪問的一個。

這段代碼的作者將跟蹤一個用戶訪問網站的 set 從 HashSet 修改為 LinkedHashSet，後者的實現保留了插入順序，所以現在我們的 set 按照訪問的順序跟蹤每一個 URI。

然而這段代碼中有很多信號說明它是錯誤的。首先--由於 set 不是為按照位置訪問設計的，為了獲取最後一個元素必須迭代整個 set（第13-15行），這樣的訪問開銷太大，有時候 list 是一個完美的選擇。其次，由於 sets 中不包含重複的值，如果最後訪問的頁面在之前已經訪問過，那麼它在 set 中的位置並不在最後。相反，它會處在第一次被添加的位置。

在這個例子中，list 或者 stack（參考下文）或者就是一個簡單的屬性都可以讓我們更好的獲得最後瀏覽過的頁面。

Java 需要特別注意

因為 set 的一個關鍵操作是 contains，作為審查者你應該檢查 set 所包含的類型的 equals 方法實現。

棧（Stacks）

Stacks是計算機科學課程最喜歡的數據結構之一，但是在現實世界中常常被忽略-在 Java 中，也許是因為 Stack 繼承自 Vector，所以有一點點過時。在這裡我不討論具體的細節，只是列出一些關鍵的點：

Stacks 支持 LIFO，所以非常適合 push/pop 操作，但是真的不適合迭代操作。

Java 在1.6版本以後是使用 Deque來實現 stack。它既可以作為 queue 又可以作為 stack 使用，所有審查者需要檢查 dequene 在代碼中的使用方式是一致的。

隊列（Queues）

隊列是 FIFO 的數據結構，通常在你想往尾部添加數據或者從頭部移除數據時非常合適。如果你在審查代碼是發現對隊列進行迭代操作（特殊情況下訪問隊列中間的元素），需要確認一下隊列是否是正確的數據結構。

隊列可以是限定大小的，也可以是不限定大小的。不限定大小的隊列可能會一直增長，所以如果審查代碼時發現使用了不限定大小隊列，請注意我們在上一篇文章中討論的性能問題。限定大小的隊列也有它的問題--在審查代碼時，需要關注什麼條件下隊列會滿，並且了解隊列滿的情況下系統會做出什麼反應。

Java 開發者特別注意

作為審查者，你不僅僅要了解通用的數據結構特性，還需要注意各種實現的優點和弱點，這些知識在 Javadoc 中都有詳細的說明：

Javadoc for List

Javadoc for Map

Javadoc for Set

如果你使用的是 Java8，記住很多集合類都添加了新的方法。作為審查者，你應該意識到這一點--你可以在一些複雜的代碼中建議使用新的方法。

為什麼要選擇正確的數據結構？

我們已經在這篇博客中討論了數據結構--怎樣確定被審查的代碼是否使用了錯誤的數據結構，以及各種數據結構的優缺點的要點，這樣作為審查者不僅僅可以確認數據結構沒有正確使用，而且可以給出更好的替代方案。我們一起來看一下為什麼選擇正確的數據結構如此重要。

性能

如果你在計算機科學課程中學習了數據結構，你應該知道選擇數據結構對性能的影響，事實上，我們在這篇博客中甚至用「大O表示法」來強調特定數據結構的某些優點。在代碼中使用正確的數據結構當然會對性能有幫助，但是這不是選擇正確工具的唯一理由。

表述預期的行為

代碼的維護者，或者是使用你的系統 API 的開發者會根據數據結構做出相應的假設。如果一個方法調用通過 list 返回數據，開發者會假設數據已經以某種方式排序。如果是以 map 返回數據，開發者會假設會頻繁的根據 key 查找單個元素。如果數據是以 set 返回，開發者會假設一個元素只會存儲一次而不是多次。一個不錯的建議是在這個假設內工作而不是破壞它。

降低複雜性

任何開發者，尤其是代碼審查者的總體目標應該是確保在最小的複雜度下代碼按照預期的行為工作-這樣可以使得代碼以後更易讀、更易理解、更容易修改、維護。在前面列出的一些反模式中（如錯誤使用 Set），我們可以發現選擇錯誤的數據結構會導致編寫更多的代碼。通常情況下選擇正確的數據結構都會簡化代碼。

總結

選擇正確的數據結構不僅僅是為了獲取性能或者在同行面前看起來很聰明。還會產生更易理解、更易維護的代碼。代碼編寫者選擇了錯誤數據結構的一些常見信號：

頻繁通過迭代在一堆值中查找某幾個值

頻繁重新排序數據

沒有使用提供關鍵功能的方法--如棧的 push 或者 pop 方法

不管是讀還是寫數據的代碼都很複雜

另外，不管是通過提供對數據結構本身的全局訪問，還是通過將類的介面緊密耦合到操作底層數據結構來暴露所選數據結構的細節，都會導致很脆弱的設計，並且以後難以修改。在代碼審查過程中應儘早發現這些問題，而不是產生可避免的技術債務。

關於本文

譯者：@唐先僧

譯文：http://www.jianshu.com/p/2c43516b9ea1