昨天學習了幾種簡單數據結構，為何要了解數據結構？一方面的原因是因為集合的底層就是與其息息相關的。
ArrayList的底層數據結構：數組。LinkedList的底層數據結構：鍊表。TreeSet的底層數據結構：紅黑樹。HashSet的底層數據結構：哈希表。前天學習了Collection集合，其繼承體系圖如下：
今天就來了解Collection的子接口List，Set，以及它們各自的實現類。
一、List接口
List，翻譯就是列表的意思，列表有何特點？
它的元素是有序的。它是有索引的（Collection沒索引）。它的元素是可以重複的。Collection是List的父接口，那麼Collection中的所有方法，List都能直接拿來用。
List因為帶索引，所以它相對於Collection的特有方法基本都是索引相關的。
集合
中有四類方法是最常見的：
也就是增加元素，刪除元素，修改元素，查詢元素，簡稱就是增刪改查。
①增：add方法
可以直接添加元素，也可以根據索引添加元素。
②刪：remove方法
Collection中的remove方法是刪除對應的元素，List中可以根據索引來刪除元素。
③改：set方法
修改對應索引位的元素。
④查：get方法
得到對應索引位的元素。
1.ArrayList
這個集合很早前就學習過了，因為太常見了。
ArrayList是List的實現類，看名字就能看出來，其中Array就是數組的意思，顯而易見，ArrayList的底層就是數組。數組查詢快，故ArrayList常用來查詢數據。
那麼問題來了，數組長度不可變，ArrayList怎麼又可變了呢？
ArrayList默認是長度為10的數組，如果超過了，就會擴容。
如何擴容?
創建一個新的數組，再將舊數組複製進去，這樣長度就增加了。
所以本質上ArrayList長度可變是因為底層換了數組。
2.LinkedList
和ArrayList一樣，LinkedLIst也是List的實現類，其底層是鍊表。鍊表增刪快，故LinkedList常用來增刪數據。
集合中重要的是增刪改查四種方法，linkedList有幾種特殊的方法：
①addFirst方法：將元素添加到開頭。
其中push方法和addFirst方法一樣。
②addLast方法：將元素添加到結尾。
③removeFirst方法：將開頭元素移除並返回。
其中pop方法和removeFirst方法一樣。
④removeLast方法：將結尾元素移除並返回。
⑤getFirst方法：查詢獲取開頭元素。
⑥getLast方法：查詢獲取結尾元素。
這幾個方法都非常簡單，理解其中文意思也就知道其作用了。
其中有兩個方法比較特殊，官方解釋如下：
pop方法：從此列表所表示的堆棧處彈出一個元素。push方法：將元素推入此列表所表示的堆棧。不要看它解釋的這麼複雜，其實就是堆棧結構，堆棧有什麼特點？
先進先出，所以無論是增加還是刪除，都是最上面的元素。
二、Set接口
Set和List一樣，都是Collection的子接口。
特點和List剛好相反：
它的元素是無序的。它是沒有索引的。它的元素是不能重複的。集合有沒有索引的依據是什麼?
如果元素可以重複，比如說一個集合存了兩個元素，都是「劉小愛」，系統要如何判斷它們？所以就需要索引，這樣就能區分開：1索引位的劉小愛和2索引位的劉小愛，就算元素一樣，索引也不一樣。
故：元素可以重複，就有索引；元素不可以重複，就不需要索引。
Set因為沒有索引，所以和父接口Collection的方法一樣，沒有特殊方法。
那如何保證元素不重複？這就得依賴於hashCode和equals方法。
1.Object類的hashCode(哈希值)
Object類有一個toString方法，代碼如下：
toHexString：是轉換成十六進位的意思。
也就是說，我們直接列印Object對象得到的一串地址值就是hashCode的十六進位。
但是一個對象它真正的地址值，Java是不會輕易告訴我們的，一是我們知道了也沒啥用；二是黑客會拿它做壞事。於是Java就想了個辦法，對真正的地址進行加密，也就是hashCode的由來。
所以什麼叫hashCode?
hashCode是對真正的地址進行一種加密手段而得到的一串數字（什麼手段也不用去了解，除非你要去做黑客)。
那麼現在問題來了，有沒有可能存在多個對象地址，對應同一個hashCode呢？
答案是有的，只不過這種情況非常少見。也就是說：
不同的對象的真正地址是不可能相同的，不同對象的hashCode是有可能相同的。如何理解這句話呢？
就是我們理論上是可以創建無數多個對象的，可以不停地在電腦上new對象，但是hashCode值是有限的，它是一個int類型的數據，最多也只有42億（2的32次方）多種可能。
所以不同的對象是有可能出現同一hashCode的，這種情況就叫哈希碰撞，只不過遇到這種情況概率微乎其微。
Object有一個方法就是hashCode，按照繼承的原則，所有類都有這個方法。
2.String的hashCode
String的hashCode方法是重寫過了的，跟真正的地址其實是沒關係的。
為何要這麼做？為了保證Set的元素不可重複。
hashCode值若是不相等，那這兩個元素必定不重複。hashCode值若是相等，這兩個元素大概率是重複的，但也有例外。如下圖幾種情況：
三、哈希表
Set的元素不可重複，這個問題該如何解決？
若是我的話，我肯定會想：將新的元素和Set中的每一個元素比較一遍不就可以了？如果有相等的，就不添加；如果有不相等的，就添加。
這樣做有問題麼，理論上是沒問題的，但是效率太低太低了，每次添加一個元素就要將元素遍歷一遍。
那些程式設計師大神為了解決這個問題，就弄出了哈希表。
所以什麼叫哈希表？
哈希表可以用來高效率解決元素不可重複這個問題，其本質就是：數組+鍊表+紅黑樹。
①哈希值就有點類似於數組中的索引，因為哈希值不同其元素必定不同。
數組查詢快，如果現在添加進來了一個元素，我根本不用遍歷，我就看有沒有相同的哈希值（相當於索引），直接就可以定位：
如果沒有相同的哈希值，直接添加進集合。如果有相同的哈希值，我再比較內容是否一樣。數組有一個問題，就是長度是一定的，所以若是元素過多時，需要擴容。但是哈希表數據結構比較複雜，還要提前擴容：哈希表中數組默認長度16，如果數組中的元素超過了75%就開始擴容。
②雖然哈希值一樣，但我還會比較它們的內容是否一樣，用equals方法比較內容是否一樣。
如果內容也一樣，重複元素，不添加進集合。如果內容不一樣，不是重複元素，添加進集合。③如果鍊表元素數量超過8，就將鍊表重構成紅黑樹。
鍊表查詢是很慢的，所以為了查詢效率，鍊表元素數量過多，就會重構成紅黑樹，紅黑樹查詢效率比鍊表要快。
這裡面涉及就到了兩個方法：hashCode方法和equals方法，它們一起能很好地判斷元素是否重複。
所以如果新建了一個對象，需要重寫hashCode方法和equals方法，這個在開發工具中直接使用Alt+Insert自動重寫方法。
HashSet的底層原理就是哈希表。
其中LinkedHashSet又是HashSet的一個子類，其特點主要是有序的Set集合，存儲和取出的順序一致。總結