JAVA中常用的數(shù)據(jù)結(jié)構(gòu)（java.util. 中）
java中有幾種常用的數(shù)據(jù)結(jié)構(gòu)锻梳，主要分為Collection和map兩個(gè)主要接口（接口只提供方法，并不提供實(shí)現(xiàn)）稿饰，而程序中最終使用的數(shù)據(jù)結(jié)構(gòu)是繼承自這些接口的數(shù)據(jù)結(jié)構(gòu)類栅葡。其主要的關(guān)系（繼承關(guān)系）有： （----詳細(xì)參見(jiàn)java api文檔！）
Collection---->Collections
Map----->SortedMap------>TreeMap
Collection---->List----->(Vector \ ArryList \ LinkedList)
Map------>HashMap
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)
一近忙、collection 數(shù)據(jù)結(jié)構(gòu)圖解（網(wǎng)上盜圖 抱歉）
二、具體實(shí)現(xiàn)說(shuō)明
1智润、Collections
該類完全由操作集合或返回集合的靜態(tài)方法組成及舍。它包含對(duì)集合進(jìn)行操作的多態(tài)算法，“包裝器”窟绷，它返回一個(gè)由指定集合支持的新集合锯玛，以及一些其他零碎內(nèi)容。靜態(tài)類，返回的還是 collection ,相當(dāng)于工具類攘残。
2拙友、List
List是有序的Collection，使用此接口能夠精確的控制每個(gè)元素插入的位置歼郭。用戶能夠使用索引（元素在List中的位置遗契，類似于數(shù)組下 >標(biāo)）來(lái)訪問(wèn)List中的元素，這類似于Java的數(shù)組病曾。
3牍蜂、Vector
基于數(shù)組（Array）的List，其實(shí)就是封裝了數(shù)組所不具備的一些功能方便我們使用泰涂，所以它難易避免數(shù)組的限制鲫竞，同時(shí)性能也不可能超越數(shù)組。所以逼蒙，在可能的情況下从绘，我們要多運(yùn)用數(shù)組。另外很重要的一點(diǎn)就是Vector是線程同步的(sychronized)的是牢，這也是Vector和ArrayList 的一個(gè)的重要區(qū)別僵井。
4、ArrayList
同Vector一樣是一個(gè)基于數(shù)組上的鏈表妖泄，但是不同的是ArrayList不是同步的驹沿。所以在性能上要比Vector好一些，但是當(dāng)運(yùn)行到多線程環(huán)境中時(shí)蹈胡，可需要自己在管理線程的同步問(wèn)題渊季。
5、LinkedList
LinkedList不同于前面兩種List罚渐，它不是基于數(shù)組的却汉，所以不受數(shù)組性能的限制。
它每一個(gè)節(jié)點(diǎn)（Node）都包含兩方面的內(nèi)容：
1.節(jié)點(diǎn)本身的數(shù)據(jù)（data）荷并；
2.下一個(gè)節(jié)點(diǎn)的信息（nextNode）合砂。
所以當(dāng)對(duì)LinkedList做添加，刪除動(dòng)作的時(shí)候就不用像基于數(shù)組的ArrayList一樣源织，必須進(jìn)行大量的數(shù)據(jù)移動(dòng)翩伪。只要更改nextNode的相關(guān)信息就可以實(shí)現(xiàn)了，這是LinkedList的優(yōu)勢(shì)谈息。
List總結(jié)：
- 所有的List中只能容納單個(gè)不同類型的對(duì)象組成的表缘屹，而不是Key－Value鍵值對(duì)。例如：[ tom,1,c ]
- 所有的List中可以有相同的元素侠仇，例如Vector中可以有 [ tom,koo,too,koo ]
- 所有的List中可以有null元素轻姿，例如[ tom,null,1 ]
基于Array的List（Vector犁珠，ArrayList）適合查詢，而LinkedList 適合添加互亮，刪除操作
6犁享、Set(接口)
Set是不包含重復(fù)元素的Collection
7、HashSet
雖然Set同List都實(shí)現(xiàn)了Collection接口豹休，但是他們的實(shí)現(xiàn)方式卻大不一樣炊昆。List基本上都是以Array為基礎(chǔ)。但是Set則是在 HashMap的基礎(chǔ)上來(lái)實(shí)現(xiàn)的威根，這個(gè)就是Set和List的根本區(qū)別窑眯。HashSet的存儲(chǔ)方式是把HashMap中的Key作為Set的對(duì)應(yīng)存儲(chǔ)項(xiàng)∫搅看看 HashSet的add（Object obj）方法的實(shí)現(xiàn)就可以一目了然了。
8炊林、LinkedHashSet
HashSet的一個(gè)子類姥卢，一個(gè)鏈表。
9渣聚、SortedSet
有序的Set独榴，通過(guò)SortedMap來(lái)實(shí)現(xiàn)的。
Set總結(jié)：
（1）Set實(shí)現(xiàn)的基礎(chǔ)是Map（HashMap）（2）Set中的元素是不能重復(fù)的奕枝，如果使用add(Object obj)方法添加已經(jīng)存在的對(duì)象棺榔，則會(huì)覆蓋前面的對(duì)象
-------------Map-----------------
Map 是一種把鍵對(duì)象和值對(duì)象進(jìn)行關(guān)聯(lián)的容器，而一個(gè)值對(duì)象又可以是一個(gè)Map隘道，依次類推症歇，這樣就可形成一個(gè)多級(jí)映射。對(duì)于鍵對(duì)象來(lái)說(shuō)谭梗，像Set一樣忘晤，一個(gè) Map容器中的鍵對(duì)象不允許重復(fù)，這是為了保持查找結(jié)果的一致性;如果有兩個(gè)鍵對(duì)象一樣激捏，那你想得到那個(gè)鍵對(duì)象所對(duì)應(yīng)的值對(duì)象時(shí)就有問(wèn)題了设塔，可能你得到的并不是你想的那個(gè)值對(duì)象，結(jié)果會(huì)造成混亂远舅，所以鍵的唯一性很重要闰蛔，也是符合集合的性質(zhì)的。當(dāng)然在使用過(guò)程中图柏，某個(gè)鍵所對(duì)應(yīng)的值對(duì)象可能會(huì)發(fā)生變化序六，這時(shí)會(huì)按照最后一次修改的值對(duì)象與鍵對(duì)應(yīng)。對(duì)于值對(duì)象則沒(méi)有唯一性的要求爆办，你可以將任意多個(gè)鍵都映射到一個(gè)值對(duì)象上难咕，這不會(huì)發(fā)生任何問(wèn)題（不過(guò)對(duì)你的使用卻可能會(huì)造成不便，你不知道你得到的到底是那一個(gè)鍵所對(duì)應(yīng)的值對(duì)象）。
1余佃、HashMap
HashMap 和 HashSet 是 Java Collection Framework 的兩個(gè)重要成員暮刃，其中 HashMap 是 Map 接口的常用實(shí)現(xiàn)類，HashSet 是 Set 接口的常用實(shí)現(xiàn)類爆土。雖然 HashMap 和 HashSet 實(shí)現(xiàn)的接口規(guī)范不同椭懊，但它們底層的 Hash 存儲(chǔ)機(jī)制完全一樣，甚至 HashSet 本身就采用 HashMap 來(lái)實(shí)現(xiàn)的步势。
2氧猬、TreeMap
TreeMap則是對(duì)鍵按序存放，因此它便有一些擴(kuò)展的方法坏瘩，比如firstKey(),lastKey()等盅抚，你還可以從TreeMap中指定一個(gè)范圍以取得其子Map。
鍵和值的關(guān)聯(lián)很簡(jiǎn)單倔矾，用put(Object key,Object value)方法即可將一個(gè)鍵與一個(gè)值對(duì)象相關(guān)聯(lián)妄均。用get(Object key)可得到與此key對(duì)象所對(duì)應(yīng)的值對(duì)象。
------------說(shuō)明-----------
一哪自、幾個(gè)常用類的區(qū)別
1．ArrayList: 元素單個(gè)丰包，效率高，多用于查詢
2．Vector: 元素單個(gè)壤巷，線程安全邑彪，多用于查詢
3．LinkedList:元素單個(gè)，多用于插入和刪除
4．HashMap: 元素成對(duì)胧华，元素可為空
5．HashTable: 元素成對(duì)寄症，線程安全，元素不可為空
二矩动、Vector瘸爽、ArrayList和LinkedList
大多數(shù)情況下，從性能上來(lái)說(shuō)ArrayList最好铅忿，但是當(dāng)集合內(nèi)的元素需要頻繁插入剪决、刪除時(shí)LinkedList會(huì)有比較好的表現(xiàn)，但是它們?nèi)齻€(gè)性能都比不上數(shù)組檀训，另外Vector是線程同步的柑潦。所以：
如果能用數(shù)組的時(shí)候(元素類型固定，數(shù)組長(zhǎng)度固定)峻凫，請(qǐng)盡量使用數(shù)組來(lái)代替List渗鬼；
如果沒(méi)有頻繁的刪除插入操作，又不用考慮多線程問(wèn)題荧琼，優(yōu)先選擇ArrayList譬胎；
如果在多線程條件下使用差牛，可以考慮Vector；
如果需要頻繁地刪除插入堰乔，LinkedList就有了用武之地偏化；
如果你什么都不知道，用ArrayList沒(méi)錯(cuò)镐侯。
三侦讨、Collections和Arrays
在 Java集合類框架里有兩個(gè)類叫做Collections（注意，不是Collection９斗）和Arrays韵卤，這是JCF里面功能強(qiáng)大的工具，但初學(xué)者往往會(huì)忽視崇猫。按JCF文檔的說(shuō)法沈条，這兩個(gè)類提供了封裝器實(shí)現(xiàn)（Wrapper Implementations）、數(shù)據(jù)結(jié)構(gòu)算法和數(shù)組相關(guān)的應(yīng)用诅炉。
想必大家不會(huì)忘記上面談到的“折半查找”拍鲤、“排序”等經(jīng)典算法吧，Collections類提供了豐富的靜態(tài)方法幫助我們輕松完成這些在數(shù)據(jù)結(jié)構(gòu)課上煩人的工作：
binarySearch：折半查找汞扎。
sort：排序，這里是一種類似于快速排序的方法擅这，效率仍然是O(n * log n)澈魄，但卻是一種穩(wěn)定的排序方法。
reverse：將線性表進(jìn)行逆序操作仲翎，這個(gè)可是從前數(shù)據(jù)結(jié)構(gòu)的經(jīng)典考題哦痹扇！
rotate：以某個(gè)元素為軸心將線性表“旋轉(zhuǎn)”。
swap：交換一個(gè)線性表中兩個(gè)元素的位置溯香。
……
Collections還有一個(gè)重要功能就是“封裝器”（Wrapper）鲫构，它提供了一些方法可以把一個(gè)集合轉(zhuǎn)換成一個(gè)特殊的集合，如下：
unmodifiableXXX：轉(zhuǎn)換成只讀集合玫坛，這里XXX代表六種基本集合接口：Collection结笨、List、Map湿镀、Set炕吸、SortedMap和SortedSet。如果你對(duì)只讀集合進(jìn)行插入刪除操作勉痴，將會(huì)拋出UnsupportedOperationException異常赫模。
synchronizedXXX：轉(zhuǎn)換成同步集合。
singleton：創(chuàng)建一個(gè)僅有一個(gè)元素的集合蒸矛，這里singleton生成的是單元素Set瀑罗，
singletonList和singletonMap分別生成單元素的List和Map胸嘴。
空集：由Collections的靜態(tài)屬性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示斩祭。
