同样的逻辑，不同的人实现的代码性能会有数量级的差异；同样的代码，微调几个字符或一行代码序列，会有数倍的性能提升；同样的代码在不同的处理器上运行也可能有数倍的性能差异；十倍程序员不仅存在于传说中，在我们的身边也可能被拿来比较。两个都。十倍体现在程序员方法的方方面面，代码性能是最直观的方面。 《如何编写高性能代码》系列源于我在群里做的一个分享。本系列将根据我以往的经验，尝试帮助大家写出更高性能的代码。原ppt的分享广而浅，所以这里我们把原ppt拆分成5个独立的部分，分别写，也作为对原ppt的延伸和补充。这篇文章是第一篇——用好算法和数据结构。 荀子在劝学中说：君子不生异，善假如物。大意是君子的资质与常人无异，只是善用外物而已。对于程序员来说，数据结构可能是我们日常编码过程中最常用的。现代语言的开发库基本上封装了各种数据结构，我们基本不需要自己去实现。但是不正确地使用数据结构会导致代码性能急剧下降。 这里我举三个Java由于没有考虑底层实现而导致性能损失的例子。 以上代码本身没有功能问题，但是Java中的ArrayList在添加过程中容量不足时会触发扩容，扩容过程会额外消耗CPU资源。但是我在上面的代码中指定ArrayList的初始化容量为100之后，通过JMH压测发现性能提升了33%。 在Java中，很多容器都有动态扩容的特性，扩容过程涉及到内存的复制，对性能的消耗很大。因此，建议在数据量可预测的情况下，在容器初始化时给定一个初始容量。这一点在很多公司的编码规范中也有明确的表述，如下图来自阿里巴巴Java开发手册。我们来看一个因LinkedList的不正确使用而导致的性能问题。//get(intindex)injdkLinkedListpublicEget(intindex){checkElementIndex(index);返回节点（索引）。项目；}Nodenode(intindex){//断言isElementIndex(index);if(index<(size>>1)){Nodex=first;//这里会从前到后遍历链表for(inti=0;ix=最后一个；for(inti=size-1;i>index;i--)x=x.prev;返回x;} LinkedList不受动态扩容影响，但其底层实现使用链表，而链表最大的问题是不支持随机遍历，所以LinkedList中get(intindex)的底层实现使用遍历，时间复杂度为O(n)，而ArrayList的底层实现是一个数组，其获取时间复杂度为O(1)。上面代码中，我把LinkedList改成ArrayList后，压测性能提升了十几倍。 在Java中，Set和List都提供了contains()方法，其作用是检查某个对象是否存在于这个集合中，但是contains的实现方法是完全不同的。在HashSet中，contains直接从哈希表中查找，时间复杂度仅为O(1)。ArrayList和LinkedList都需要遍历一次全量数据才能得到结果，时间复杂度为O(n)。代码这里就不赘述了，具体可以自行查看。 在我的实际测试中，Set和List的contains性能差异确实非常明显。我用JMH测试发现，当有100个元素时，HashSet.contains的性能是ArrayList的10倍，LinkedList的20倍。当数据量较大时，差异会更加明显。 以上三个错误例子其实在我们日常的代码中经常会遇到。或许你现在浏览一下项目代码，很容易就能发现List和Set的不当使用。也许你会反驳说JDK中的这些API的性能是极高的，而这部分只是业务逻辑中非常非常小的一部分。错误的使用可能只会导致整体的百分之一甚至千分之一的差异，但如果不积累步数，就无法到达万里；不积小溪，不成江河。下图展示了各种常用的数据结构和操作的时空复杂度，供大家参考： 算法和数据结构是一个程序员的基础，虽然我们很少自己实现一个具体的算法或者数据结构，但是我们一直使用各种封装的算法或数据结构。我们应该熟悉各种算法和数据结构，包括它们的时间复杂度、空间复杂度和适用范围。如何写出高性能代码系列文章（一）善用算法和数据结构（二）善用数据特性
