[[283143]]

今天說一說集合，在面試的時(shí)候出現(xiàn)的頻率非常高，開發(fā)中使用的頻率也非常高。經(jīng)常聽到有人說List是有序，Set是無序，那么這個(gè)有序和無序指的究竟是什么呢?

這里有兩個(gè)概念，一個(gè)是存取元素的順序，比如我存的時(shí)候是3 4 5 1 2 ，那么取出來也應(yīng)該是3 4 5 1 2 或者 2 1 5 4 3 。另一個(gè)是元素在容器中大小順序，更準(zhǔn)確說是排序。如果說區(qū)分了這兩個(gè)概念，就好說了，看上面的體系圖，List家族有兩名大將，分別是ArrayList和LinkedList。而Set家族里主要有HashSet和TreeSet兩名大將。

如果要按照存和取的順序來講，ArrayList和LinkedList就屬于有序集合，因?yàn)锳rrayList底層是動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的，而數(shù)組是一塊連續(xù)的空間，每次存的時(shí)候都是找到索引，一個(gè)接著一個(gè)的存儲(chǔ)，取的時(shí)候也要按照索引遍歷出來。

鏈表也是一樣，不是存到鏈表頭就是存到鏈表尾。因?yàn)榇婧腿〉捻樞蛴行?，模擬棧(先進(jìn)后出)和隊(duì)列(先進(jìn)先出)這兩種數(shù)據(jù)結(jié)構(gòu)也很容易。但這兩種結(jié)構(gòu)它們本身并不能對(duì)元素進(jìn)行排序，這也決定了我不能輕易的找到數(shù)組或鏈表中的最大值和最小值，或者說元素和元素之間存儲(chǔ)的并沒有什么規(guī)律。

同樣，按照存儲(chǔ)順序來講，HashSet依賴哈希存儲(chǔ)，計(jì)算哈希值之后，會(huì)分散到不同的存儲(chǔ)位置上，這也就代表存儲(chǔ)的時(shí)候，元素不是一個(gè)挨著一個(gè)存儲(chǔ)的，而是根據(jù)每個(gè)元素的hash值，散列到了不同的位置。存取的順序也是不能保證的，元素的排序順序也是不能保證的，但好處就是存取效率高。

而TreeSet依賴的是樹存儲(chǔ)，在樹這種結(jié)構(gòu)中，無論是二分查找樹，還是紅黑樹，在存儲(chǔ)元素的時(shí)候都會(huì)對(duì)元素本身進(jìn)行比較，按照大小放到合適的位置，這也就說明，元素會(huì)按照樹的性質(zhì)去存儲(chǔ)，那么也就無法保證存和取元素的順序。但是元素可以在存儲(chǔ)的時(shí)候根據(jù)自身的大小排好序，從而可以很輕易的找到最大值，最小值，以及給定一個(gè)元素，找到比他大和比他小元素等操作。

總結(jié)：按元素存取順序來說，List是有序的，Set是無序的。按照元素和元素之間的關(guān)系來說，List是無序的，TreeSet是有序的。而HashSet怎么說都是無序的。