【第955期】代码审查应该关注什么：数据结构
前言
周五团队分享会上有童鞋推荐了<Head First设计模式(中文版）>有兴趣的童鞋可以去看看。今日早读文章由@唐先僧翻译分享。
前戏：
这系列用的语言是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）
计算机科学最喜欢的另一个数据结构。Queues 常常在讨论并发相关的话题时出现（确实，Java 中大多数 Queue 的实现都在 java.util.concurrent 中使用），因为它最常见的用法是在线程和模块之间传递数据。
队列是 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
作者：@Trisha Gee
原文：https://blog.jetbrains.com/upsource/2015/08/20/what-to-look-for-in-a-code-review-data-structures/