同一份邏輯，不同人的實作的代碼性能會出現數量級的差異； 同一份代碼，你可能微調幾個字元或者某行代碼的順序，就會有數倍的性能提升；同一份代碼，也可能在不同處理器上運作也會有幾倍的性能差異；十倍程式員不是隻存在于傳說中，可能在我們的周圍也比比皆是。十倍展現在程式員的方法面面，而代碼性能卻是其中最直覺的一面。
“如何寫出高性能代碼”系列源自我在組内做的一次分享，本系列将以我個人之前的經驗為基礎，嘗試幫助大家寫出更高性能的代碼 。原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的性能都極高，而且這部分也隻是業務邏輯中非常非常小的一部分，錯誤得使用可能隻會導緻整體百分之一甚至千分之一的差異，但是不積跬步無以至千裡，不積小流無以成江河。
下圖是各種常用資料結構各種操作的時間、空間複雜度供大家查閱：