-
List
- ArrayList：
背后是一個(gè)動(dòng)態(tài)數(shù)組，有序插入元素，可以根據(jù)下標(biāo)取得對(duì)應(yīng)元素，檢索元素為線(xiàn)性查找，效率較低。當(dāng)容量不足時(shí)會(huì)自動(dòng)擴(kuò)容，每次新建一個(gè)新的List，大小為原來(lái)的1.5倍，再將所有元素拷貝到新的List中去。 - LinkedList：
背后是一個(gè)鏈表結(jié)構(gòu)，有序插入元素，可以根據(jù)下標(biāo)取得對(duì)應(yīng)元素， 檢索時(shí)從頭部或者尾部不斷向下標(biāo)靠攏，所以頭部和尾部的查找效率高，中間低。
-
Set
- HashSet：
計(jì)算出元素的哈希值，哈希值相同的元素放在同一個(gè)哈希桶里，每個(gè)哈希桶里維護(hù)一個(gè)鏈表。插入的元素是無(wú)序的且不允許出現(xiàn)重復(fù)元素，查找效率高。但當(dāng)發(fā)生哈希碰撞時(shí)，整個(gè)結(jié)構(gòu)退化為鏈表會(huì)導(dǎo)致性能急劇下降。 - LinkedHashSet：
不同于HashSet，前面的數(shù)據(jù)結(jié)構(gòu)為鏈表，所以是有序的，其他幾乎一樣。 - TreeSet：
前面的數(shù)據(jù)結(jié)構(gòu)為二叉樹(shù)，可以對(duì)插入的元素進(jìn)行排序。檢索快，時(shí)間復(fù)雜度降為對(duì)數(shù)級(jí)。
-
Map
- HashMap：
實(shí)質(zhì)上和HashSet一樣，不過(guò)可以存儲(chǔ)鍵（Key）到值（Value）的映射。JDK1.8之后當(dāng)鏈表節(jié)點(diǎn)大于7時(shí)會(huì)裂變?yōu)榧t黑樹(shù)。 - TreeMap：
可以排序的HashMap。
