????這段時(shí)間在讀《java程序性能優(yōu)化》封拧，看到里面有一些關(guān)于Java的一些數(shù)據(jù)結(jié)構(gòu)相關(guān)的內(nèi)容，主要涉及到String字符串類型和Map夭问、List泽西、Set等常用的數(shù)據(jù)結(jié)構(gòu)的一些使用小技巧。感覺在平時(shí)的開發(fā)中還是很實(shí)用的缰趋，這里做一些延伸總結(jié)捧杉，記錄一下。

Part I.String字符串優(yōu)化處理

1.1 String的實(shí)現(xiàn)介紹

Java中的String對(duì)象實(shí)現(xiàn)是通過(guò)對(duì)Char數(shù)組的擴(kuò)展和進(jìn)一步封裝實(shí)現(xiàn)的秘血。它主要由三部分組成：Char數(shù)組味抖、偏移量和String的長(zhǎng)度』伊福看下圖源碼中String的構(gòu)造函數(shù)可以明了的看出仔涩。Char value[]數(shù)組就是String的內(nèi)容，它是String對(duì)象所表示的字符串的超集粘舟，意味著假如你定義了一個(gè)字符串String=”abc”熔脂，其實(shí)value[]數(shù)組其實(shí)可能不單單就是一個(gè)長(zhǎng)度為3的存在a,b,c三個(gè)字符的數(shù)組佩研，長(zhǎng)度可能是4或者其他值，只不過(guò)其他位置沒存值霞揉。String的真實(shí)內(nèi)容還需要用偏移量和長(zhǎng)度在這個(gè)value[]數(shù)組中去定位和截取旬薯。這點(diǎn)是平時(shí)很容易忽略的，但是知道這點(diǎn)對(duì)后面要講的String的一些字符串處理方法的性能和內(nèi)存泄漏的理解很有幫助适秩。

String對(duì)象有三個(gè)基本特點(diǎn)：

■不變性绊序；

■針對(duì)常量池的優(yōu)化；

■類的final定義隶症；

1.不變性是指String對(duì)象一旦生成了政模，就不能在對(duì)它進(jìn)行改變。這個(gè)不變性其實(shí)和并發(fā)模式里面的不變模式異曲同工蚂会，有很多共通的地方淋样。即一個(gè)對(duì)象一旦創(chuàng)建了，就不會(huì)再發(fā)生改變胁住，并發(fā)的不變模式主要用在當(dāng)一個(gè)對(duì)象需要被多個(gè)線程共享的時(shí)候趁猴，并且訪問(wèn)很頻繁，這個(gè)時(shí)候不變性可以保證省略同步和鎖的情況下仍是線程安全的彪见，從而大幅度提高系統(tǒng)性能

這里既然順便擴(kuò)展介紹一下不變模式：不變模式就是依靠對(duì)象的不變性儡司，確保在沒有同步操作的多線程環(huán)境中依然始終保持內(nèi)部狀態(tài)一致性和正確性。不變模式的實(shí)現(xiàn)很簡(jiǎn)單余指，為了確保對(duì)象一旦被創(chuàng)建就不會(huì)再被改變只要在創(chuàng)建對(duì)象時(shí)做到下面幾點(diǎn)：

①去除setter方法以及所有修改自身屬性的方法捕犬。

②將所有的屬性設(shè)置為私有，并用final標(biāo)記酵镜，確保其不可修改性碉碉。

③確保沒有子類可以重載修改它的方法。

④有一個(gè)可創(chuàng)建完成對(duì)象的構(gòu)造函數(shù)淮韭。

舉個(gè)栗子吧,實(shí)現(xiàn)一個(gè)產(chǎn)品對(duì)象垢粮，有序列號(hào)，名稱靠粪，價(jià)格三個(gè)屬性：

public final class Product{

????private final String no;

????private final String name;

????private final double price;

public Product (String no ,String name, double price){

????Super();

????this.no =no;

????this.name=name;

????this.price=price;

}

public String getNo(){

????return no;

}

public String getName(){

????return name;

}

public double getPrice(){

????return price;

}

}

在不變模式中final關(guān)鍵字起到了重要作用蜡吧，不管是上面這個(gè)例子還是String的定義，都用到final關(guān)鍵字占键。對(duì)class的final定義保證了不變類沒有子類昔善，確保了它里面的所有g(shù)etter方法不會(huì)被重寫。對(duì)屬性值的fianl定義確保所有的數(shù)據(jù)只能在對(duì)象被構(gòu)造時(shí)賦值一次捞慌，之后就不會(huì)再發(fā)生改變耀鸦。我們可以看到String類的定義是完全符合以上這些要求的。?

2.針對(duì)常量池的優(yōu)化，當(dāng)兩個(gè)String對(duì)象擁有相同的值得時(shí)候袖订，它們只引用常量池中的同一個(gè)拷貝氮帐。這個(gè)在同一個(gè)字符串反復(fù)出現(xiàn)時(shí)，可以大幅度節(jié)省內(nèi)存空間洛姑。這里的常量池就是JVM中的常量池那個(gè)內(nèi)存區(qū)域上沐，需要注意的是當(dāng)你使用new String("")方式創(chuàng)建的字符串時(shí)，會(huì)被存在堆中楞艾，因?yàn)閷?duì)象實(shí)例都是存放在堆上参咙。

String str1="abc";

String str2="abc";

String str3=new String("abc");

定義這三個(gè)變量，str1 == str2返回true硫眯，str1 == str3返回false蕴侧，str1 == str3.intern()返回true。因?yàn)閟tr3使用的new方法重新定義的两入，所以單獨(dú)在堆上開辟了一塊新的存儲(chǔ)空間净宵，所以str1和str3是不相等的，但實(shí)際上str3指向的實(shí)體str1一樣裹纳，都是存在常量池中的“abc”择葡，所以當(dāng)str3.intern()返回String對(duì)象在常量池中的引用時(shí)，值和str1是一樣的剃氧。

3.類的final定義敏储，用final關(guān)鍵字定義的類不可能有任何子類，從上面介紹不變性時(shí)已經(jīng)講了朋鞍，這樣可以保證多線程下的安全性已添。

1.2 String使用需要注意的地方

?????? 由于String對(duì)象是不可變對(duì)象，所以在對(duì)字符串進(jìn)行修改操作時(shí)滥酥，比如說(shuō)字符串拼接酝碳，替換時(shí)，String對(duì)象總是會(huì)生成新的對(duì)象恨狈，所以性能較差。針對(duì)字符串修改較多的操作呛讲，我們應(yīng)該使用StringBuffer和StringBuilder類禾怠。

?????? 實(shí)際使用中，對(duì)String對(duì)象的“+”和“+=”操作其實(shí)都會(huì)在運(yùn)行時(shí)編譯成StringBuilder的實(shí)現(xiàn)贝搁。但是當(dāng)這種“+”和“+=”的操作出現(xiàn)在循環(huán)體中時(shí)吗氏，如果還是使用String的話，就會(huì)針對(duì)每次的“+”和“+=”操作都new一個(gè)StringBuilder對(duì)象雷逆，影響系統(tǒng)性能弦讽。所以在實(shí)際編碼中，盡量少用String的“+”和“+=”操作，String的concat()方法效率也要遠(yuǎn)高于“+”和“+=”運(yùn)算符往产，但和StringBuilder類的效率比起來(lái)還是要相差很遠(yuǎn)被碗。

??? 1.3 StingBuilder和StringBuffer的區(qū)別

?????? 通過(guò)查看源碼可以發(fā)現(xiàn)其實(shí)這兩個(gè)類實(shí)現(xiàn)的方法都差不多，只不過(guò)StringBuffer對(duì)幾乎所有的方法都做了同步處理仿村，而StringBuilder并沒有做同步處理锐朴。因?yàn)樽龇椒ㄍ綍?huì)對(duì)性能有一定的影響，所以StringBuilder的效率要優(yōu)于StringBuffer蔼囊，但是在多線程系統(tǒng)中焚志，StringBuilder無(wú)法保證線程安全。

?????? 在初始化StringBuilder和StringBuffer時(shí)都可以預(yù)先設(shè)置一個(gè)容量參數(shù)畏鼓，如果可以預(yù)先預(yù)測(cè)到大小時(shí)酱酬，可以設(shè)置一個(gè)初始容量。因?yàn)閿U(kuò)容函數(shù)的策略是將原有的容量翻倍云矫，創(chuàng)建一個(gè)新的數(shù)組膳沽，然后將原有的數(shù)組中的內(nèi)容復(fù)制到這個(gè)新的數(shù)組中去。

Part II.List類型

????List有三種最常用也是最重要的實(shí)現(xiàn)就是泼差，ArrayList贵少、Vector和LinkedList。以LinkedList的類圖為例堆缘。這三種List都是來(lái)自AbstractList的實(shí)現(xiàn)滔灶，AbstracList直接實(shí)現(xiàn)了List接口，并擴(kuò)展自AbstractCollection吼肥。

????需要注意的是录平，三種List的實(shí)現(xiàn)并不完全一樣，ArrayList和Vector使用了數(shù)組實(shí)現(xiàn)缀皱，可以理解為這兩種List里面的方法其實(shí)是封裝好的對(duì)內(nèi)部數(shù)組的操作斗这。對(duì)這兩種List的操作等價(jià)于對(duì)內(nèi)部數(shù)組的操作。而LinkedList則是使用雙向循環(huán)鏈表實(shí)現(xiàn)的啤斗。這兩種不同的實(shí)現(xiàn)方式?jīng)Q定了他們適用于不一樣的工作場(chǎng)景表箭。ArrayList和Vector幾乎使用了相同的算法，唯一的區(qū)別就是對(duì)多線程的支持钮莲。ArrayList中沒有對(duì)方法進(jìn)行線程同步處理免钻，因此不是線程安全的。Vector中絕大部分方法都是做了線程同步的崔拥，是一種線程安全的實(shí)現(xiàn)极舔。

????所以我們主要是要對(duì)比ArrayList和LinkedList的實(shí)現(xiàn)區(qū)分兩者更適用的場(chǎng)景。

操作一：在任意位置做插入操作链瓦。

????這是ArrayList的實(shí)現(xiàn)拆魏，可以看出里面需要先確定數(shù)組容量是否足夠，不夠的話涉及到擴(kuò)容的處理，擴(kuò)容需要重新創(chuàng)建一個(gè)數(shù)組并且將整個(gè)數(shù)組復(fù)制過(guò)去渤刃。在不需要擴(kuò)容的情況下拥峦，對(duì)ArrayList的每一次插入操作也會(huì)涉及到一個(gè)數(shù)組復(fù)制，只有在插入List的尾端時(shí)溪掀，這個(gè)操作才不消耗資源事镣。而且如果插入的元素位置越靠前，數(shù)組的重組開銷也越大揪胃。試想一下假設(shè)數(shù)組很大璃哟，此時(shí)要在List的頭部位置插入數(shù)值，這種操作是相當(dāng)耗費(fèi)資源和時(shí)間的喊递。

????這是LinkedList的add函數(shù)的實(shí)現(xiàn)随闪。對(duì)于使用雙向循環(huán)鏈表實(shí)現(xiàn)的LinkedList來(lái)說(shuō)，不管在哪個(gè)位置插入都是一樣的骚勘。因?yàn)橹恍枰薷囊幌聦?duì)象的前后指針的指向位置铐伴。

所以在系統(tǒng)中如果需要經(jīng)常在任意位置插入元素，則可以考慮使用LinkedList代替ArrayList俏讹。

操作二：在任意位置做刪除操作当宴。

????在對(duì)ArrayList進(jìn)行刪除操作時(shí)，由于自身是數(shù)組實(shí)現(xiàn)的泽疆，所以也需要進(jìn)行數(shù)組重組户矢。而LinkedList只需要遍歷到對(duì)應(yīng)要?jiǎng)h除的對(duì)象位置然后修改前后位置的指針指向就好了。

操作三：遍歷列表殉疼。

????我們常用的遍歷方式有三種：ForEach操作撑瞧，迭代器和for循環(huán)善已。書中對(duì)這三種方法做了比較朽寞，最后發(fā)現(xiàn)對(duì)ArrayList來(lái)說(shuō)for循環(huán)這種隨機(jī)訪問(wèn)的方式效率最高黎比，這是由于他們實(shí)現(xiàn)了RandomAccess接口。迭代器比ForEach的方式效率要高一些眠砾。但是對(duì)于LinkedList來(lái)說(shuō)虏劲，for循環(huán)這種隨機(jī)訪問(wèn)的方式性能非常的差。所以對(duì)于ArrayList這些基于數(shù)組是實(shí)現(xiàn)的來(lái)說(shuō)褒颈，在遍歷對(duì)象時(shí)可以優(yōu)先考慮隨機(jī)訪問(wèn)伙单，對(duì)于LinkedList這種基于鏈表實(shí)現(xiàn)的，隨機(jī)訪問(wèn)的性能特別差哈肖，要遍歷的話考慮用迭代的方式去實(shí)現(xiàn)。

Part III.Map類型

????Map是非常常用的數(shù)據(jù)結(jié)構(gòu)念秧，下面是從網(wǎng)上找的Map的類圖淤井，圍繞著Map接口，最主要的實(shí)現(xiàn)類有Hashtable、HashMap币狠、LinkedHashMap和treeMap游两。我們平時(shí)用的最多的可能是中間兩個(gè)。還有我們平時(shí)讀取配置文件經(jīng)常用到的properties類也是Map的一種實(shí)現(xiàn)漩绵。值得我們關(guān)注的是贱案，HashMap和Hashtable有兩套不同的實(shí)現(xiàn)，兩者都是實(shí)現(xiàn)了Map接口止吐，但不同的是宝踪，Hashtable的大部分方法都做了同步，而HashMap沒有碍扔，所以HashMap不是線程安全的瘩燥。其次Hashtable不允許key或者value使用null值，而HashMap可以不同。第三厉膀，他們對(duì)key的hash算法和hash值到內(nèi)存索引的映射算法不同。

HashMap的實(shí)現(xiàn)原理：

????HashMap其實(shí)就是將Key做hash算法二拐，然后得到的hash值映射到內(nèi)存地址服鹅，直接取得key所對(duì)應(yīng)的數(shù)據(jù)。在HashMap中百新，底層數(shù)據(jù)結(jié)構(gòu)使用的是數(shù)組企软，內(nèi)存地址其實(shí)就是數(shù)組下標(biāo)索引。HashMap的高性能需要保證以下幾點(diǎn)：

■? ? Hash算法必須是高效的吟孙。

■? ?Hash值到內(nèi)存地址的算法是快速的

■? ?根據(jù)內(nèi)存地址可以直接取到對(duì)應(yīng)的值

下圖中就是HashMap中hash計(jì)算方法

????key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)澜倦，返回int型散列值。在取到散列值后還做一個(gè)操作就是先右移了16位再和自己異或處理了一下杰妓。其實(shí)這個(gè)處理是有一定的原因的藻治。因?yàn)镠ashMap的put方法里除了調(diào)用到了hash()方法外，調(diào)用到了putVal方法巷挥。在putVal方法里面有個(gè)被選中的部分桩卵，就是來(lái)確定數(shù)組下標(biāo)的（上面說(shuō)過(guò)了HashMap底層其實(shí)就是用數(shù)組和鏈表實(shí)現(xiàn)的）。因?yàn)槲覀冎繦ashMap的初始大小是16倍宾，但是通過(guò)hashCode()返回的散列值的二進(jìn)制后面幾位可能都是0雏节，這個(gè)時(shí)候直接和n-1（n是整個(gè)散列表的長(zhǎng)度）按位與的話返回結(jié)果可能就是0，如果這樣的話高职，可能很多值都會(huì)堆積在散列表索引為0的這個(gè)位置钩乍，導(dǎo)致效率低下。

????舉個(gè)栗子怔锌，我們默認(rèn)n為16寥粹，然后16-1=15变过，轉(zhuǎn)化為二進(jìn)制后為1111。此時(shí)涝涤，假設(shè)hash的值不做 h = key.hashCode() ^ (h >>> 16) 這樣的處理而是直接調(diào)用 h = key.hashCode() 得到h媚狰，h的值為10100110101000000，那么1111和h按位與阔拳，i 結(jié)果就為0 崭孤。那么傳入的鍵值對(duì)放的位置就是tab[0]位置或者說(shuō)是在掛tab[0]位置下面的鏈表的一個(gè)節(jié)點(diǎn)。這樣的話大多數(shù)類似于 xxxx xxxx 0000這樣的數(shù)和 1111 按位與或結(jié)果都為0糊肠。那么tab[0]位置有可能會(huì)存儲(chǔ)很多的值辨宠，即鏈表的長(zhǎng)度會(huì)很長(zhǎng)，這樣查找時(shí)就會(huì)降低了性能罪针。

????如果我們這個(gè)時(shí)候做了右移16位然后和自己異或的操作的話彭羹，h的值就是00000000000000001，然后再和1111按位與泪酱，得到就是00000000000001110派殷，即14。這個(gè)時(shí)候就不再返回0了墓阀。

????其實(shí)介紹了這么多毡惜，就是想說(shuō)在計(jì)算hash值時(shí)效率是很高的。

????Hash沖突問(wèn)題斯撮，在一些特殊情況下经伙，HashMap還是會(huì)遇到一些性能問(wèn)題，當(dāng)通過(guò)Hash計(jì)算后勿锅，發(fā)現(xiàn)對(duì)應(yīng)的內(nèi)存中的同一個(gè)地址時(shí)帕膜，就出現(xiàn)了Hash沖突的問(wèn)題，雖然HashMap底層使用數(shù)組實(shí)現(xiàn)的溢十，但是數(shù)組里的元素不知一個(gè)簡(jiǎn)單值垮刹，而是一個(gè)Entry對(duì)象，每個(gè)Entry對(duì)象里面包含key张弛，value荒典，next，hash等幾項(xiàng)吞鸭。里面的next是一個(gè)指向另外一個(gè)Entry的指針寺董。所以當(dāng)put操作有沖突時(shí)，新的Entry依然會(huì)被放在其hash值對(duì)應(yīng)的索引下標(biāo)內(nèi)刻剥，并替換原有的值遮咖，同時(shí)，為了保證舊值不丟失造虏，會(huì)將新的Entry的next指向舊值御吞。這樣就實(shí)現(xiàn)了一個(gè)數(shù)組索引空間內(nèi)存放多個(gè)值踢械，其實(shí)相當(dāng)于一個(gè)數(shù)組項(xiàng)里面存的是一個(gè)單向鏈表。

????除了hashcode沖突導(dǎo)致的性能問(wèn)題魄藕，還有個(gè)影響HashMap性能的是它的容量參數(shù)。和ArrayList和Vector這種基于數(shù)組的結(jié)構(gòu)一樣撵术，在空間不足時(shí)同樣需要進(jìn)行擴(kuò)展背率。

HashMap有兩個(gè)可以指定初始化大小的構(gòu)造函數(shù)，其中一個(gè)可以設(shè)置一個(gè)負(fù)載因子嫩与，我們以這個(gè)函數(shù)為例寝姿。

????initialCapacity指定了HashMap的初始容量，loadFactor指定了其負(fù)載因子划滋。一般初始默認(rèn)情況饵筑，初始大小為16，負(fù)載因子為0.75.

負(fù)載因子=元素個(gè)數(shù)/內(nèi)部數(shù)組總大小

????在HashMap內(nèi)部還有一個(gè)threshold的變量处坪，這個(gè)變量值等于當(dāng)前數(shù)組總?cè)萘亢拓?fù)載因子的乘積根资。它表示HashMap的閾值，當(dāng)HashMap的實(shí)際容量超過(guò)閾值時(shí)同窘，HashMap就會(huì)進(jìn)行擴(kuò)容玄帕。很明顯，HashMap的擴(kuò)容操作會(huì)遍歷整個(gè)HashMap想邦，所以應(yīng)該設(shè)置合理的初始大小和負(fù)載因子裤纹，以避免擴(kuò)容操作的發(fā)生。

????上面我們介紹了HashMap的實(shí)現(xiàn)原理和一些需要注意的地方丧没，雖然HashMap有很不錯(cuò)的效率鹰椒，但是它是無(wú)序的，被存入在HashMap的元素呕童，在遍歷HashMap時(shí)漆际，其輸出是無(wú)序的。如果希望元素是輸出時(shí)是按照存入的順序的話拉庵，就需要使用LinkedHashMap來(lái)替代灿椅。與HashMap不同的是，LinkedHashMap內(nèi)部增加了一個(gè)鏈表钞支，用于存放元素的順序茫蛹。

?????? LinkedHashMap可以提供兩種類型的順序：一種是是元素插入時(shí)的順序，第二種是最近訪問(wèn)的順序烁挟。默認(rèn)是按插入順序的婴洼，當(dāng)accessOrder聲明為true時(shí)，則是按照最近訪問(wèn)順序撼嗓。LinkedHashMap繼承了HashMap的Entry類柬采，同時(shí)還增加了before和after兩個(gè)屬性欢唾，用來(lái)記錄某一個(gè)表項(xiàng)的前驅(qū)和后繼，并構(gòu)成了循環(huán)鏈表粉捻。

? ??TreeMap礁遣，支持進(jìn)行排序的一種Map，他實(shí)現(xiàn)了SortedMap接口肩刃，可以對(duì)元素進(jìn)行排序祟霍。TreeMap是根據(jù)元素的Key進(jìn)行排序的，為了確定Key的排序順序盈包，可以使用兩種方法指定沸呐。（1）在TreeMap的構(gòu)造函數(shù)中注入一個(gè)Comparator（2）使用一個(gè)實(shí)現(xiàn)了Comparable接口的Key。使用TreeMap時(shí)是必須進(jìn)行排序操作的呢燥，所以使用過(guò)程中一定要通過(guò)上面兩個(gè)方式中的其中一種將排序規(guī)則遞給TreeMap崭添。TreeMap的內(nèi)部實(shí)現(xiàn)是基于紅黑樹，紅黑樹是一種平衡查找樹叛氨。關(guān)于紅黑樹的算法有些復(fù)雜呼渣，有空再詳細(xì)了解一下。

?????? 如果需要將排序功能假如HashMap時(shí)力试，盡量使用TreeMap而不是本人在程序中實(shí)現(xiàn)排序算法徙邻。

Part IV.Set接口

?????? Set接口在Collection接口之上沒有增加額外的操作，Set集合中的元素是不能重復(fù)的畸裳。關(guān)于Set的實(shí)現(xiàn)有HashSet缰犁、LinkedHashSet和TreeSet。這三個(gè)都是基于上面介紹的對(duì)應(yīng)的Map的一種封裝而已怖糊，內(nèi)部的方法都是差不多的帅容。這里就不再重復(fù)介紹，只要記住元素不能重復(fù)就好了伍伤。