[[283143]]

今天說一說集合，在面試的時候出現的頻率非常高，開發中使用的頻率也非常高。經常聽到有人說List是有序，Set是無序，那么這個有序和無序指的究竟是什么呢?

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

如果要按照存和取的順序來講，ArrayList和LinkedList就屬于有序集合，因為ArrayList底層是動態數組實現的，而數組是一塊連續的空間，每次存的時候都是找到索引，一個接著一個的存儲，取的時候也要按照索引遍歷出來。

鏈表也是一樣，不是存到鏈表頭就是存到鏈表尾。因為存和取的順序有序，模擬棧(先進后出)和隊列(先進先出)這兩種數據結構也很容易。但這兩種結構它們本身并不能對元素進行排序，這也決定了我不能輕易的找到數組或鏈表中的最大值和最小值，或者說元素和元素之間存儲的并沒有什么規律。

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

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

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