关于java:如何写出高性能代码一善用算法和数据结构

34次阅读

共计 1885 个字符，预计需要花费 5 分钟才能阅读完成。

同一份逻辑，不同人的实现的代码性能会呈现数量级的差别；同一份代码，你可能微调几个字符或者某行代码的程序，就会有数倍的性能晋升；同一份代码，也可能在不同处理器上运行也会有几倍的性能差别；十倍程序员 不是只存在于传说中，可能在咱们的四周也亘古未有。十倍体现在程序员的办法面面，而代码性能却是其中最直观的一面。

“如何写出高性能代码”系列源自我在组内做的一次分享，本系列将以我集体之前的教训为根底，尝试帮忙大家写出更高性能的代码。原 ppt 分享的面有宽也比拟肤浅，所以这里将原 ppt 拆分成 5 个独立的局部，别离成文，也作为对原 ppt 的扩大和补充，本文是第一篇——善用算法和数据结构。

荀子 - 劝学中说道：小人生非异也，善假于物也。其粗心是小人的资质跟个别人没什么不同，只是长于借助外物罢了。对于程序猿而已，咱们在日常编码过程中，可能最罕用的就是数据结构。古代各语言的开发库里基本上都封装好了各类的数据结构，咱们根本不须要本人去实现。但谬误地应用数据结构可能导致代码性能呈现大幅的降落。

这里我举三个 Java 中因未思考到底层实现导致性能损耗的示例。

下面这段代码自身性能上没有任何问题，但 Java 中 ArrayList 在增加过程中在容量有余时会触发扩容，扩容的过程会额定耗费 CPU 资源。但我在上述代码中指定了 ArrayList 的初始化容量为 100 后，用 JMH 压测发现有了 33% 的性能晋升。

在 Java 中，很多容器都有动静扩容的个性，而扩容的过程波及到内存的拷贝，很耗费性能。所以倡议如果能预知到数据量大小，在容器初始化的时候给定一个初始容量。这点在当初很多公司的编码标准中也明确提出了，如下图来自阿里巴巴 Java 开发手册。

再来看一个谬误应用 LinkedList 导致的性能问题。

    // jdk LinkedList 中的 get(int index）public E get(int index) {checkElementIndex(index);
        return node(index).item;
    }
    Node<E> node(int index) {// assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            // 这里会从前到后遍历链表
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

LinkedList 并不受动静扩容的影响，然而它的底层实现是用的链表，而链表最大的问题在于不反对随机遍历，所以 LinkedList 中 get(int index)的底层实现是用了遍历，工夫复杂度是 O(n)，而 ArrayList 的底层实现是数组，它的 get 工夫复杂度是 O(1)。在上述代码中我将 LinkedList 改成 ArrayList 后压测的确也失去了十倍以上的性能晋升。

在 Java 中，Set 和 List 都提供了 contains()办法，其作用就是校验某个在是否存在于这个汇合中，但其 contains 实现办法齐全不一样。在 HashSet 中，contains 间接是从 hash 表中查找，其工夫复杂度只有 O(1)。而在 ArrayList 和 LinkedList 中，都是须要遍历一次全量数据能力得出后果，工夫复杂度是 O(n)，代码这里就不再赘述，具体能够自行查阅。
在我理论测试是，Set 和 List 的 contains 性能差别的确也非常明显。我用 JMH 测试发现，当有 100 个元素时，HashSet.contains 的性能是 ArrayList 的 10 倍，是 LinkedList 的 20 倍，当数据量更大时，这个差别会更显著。

以上 3 个谬误的示例其实在咱们日常代码中常常会遇到，或者你当初去翻阅下我的项目代码，很容易就能找到 List 和 Set 应用不当之处。兴许你会反驳，JDK 中这些 Api 的性能都极高，而且这部分也只是业务逻辑中十分十分小的一部分，谬误得应用可能只会导致整体百分之一甚至千分之一的差别，然而不积跬步无以至千里，不积小流无以成江河。

下图是各种罕用数据结构各种操作的工夫、空间复杂度供大家查阅：

算法和数据结构是一个程序员的根基，尽管日常咱们很少本人去实现某种具体的算法或数据结构，但咱们却无时无刻不在应用各种已被封装好的算法或数据结构，咱们该当做到对各种算法和数据结构烂熟于心，包含其工夫复杂度、空间复杂度、适用范围。