List-LinkedList、set集合基礎增強底層原始碼分析
List-LinkedList
作者 ： Stanley 羅昊
【轉載請註明出處和署名，謝謝！】
繼上一章繼續講解，上章內容：
List-ArreyLlist集合基礎增強底層原始碼分析：https://www.cnblogs.com/StanleyBlogs/p/10396253.html
List-LinkedList
首先，LinkedList底層是一個連結串列結構，連結串列結構的特點，並且是雙向連結串列；
增刪快 、查詢慢
並分為 單向連結串列跟雙向連結串列
單向連結串列
單向連結串列，每個元素都稱之為一個節點，每個節點都由兩部分組成分別是，資料 、指向下一個節點的指標；
單向連結串列每一個節點在記憶體中儲存上、空間位置上、都是無無序的；
連結串列查詢效率較低
單向連結串列中的每個元素在空間的儲存位置上沒有規律，也沒有順序，那麼在查詢某個元素的時候，必須從頭節點挨著往後找，直到找到為止；
連結串列增 刪 效率高
因為連結串列每個元素在儲存的空間是沒有順序的，，刪除或者新增某個元素，只需要讓指標重新指向即可，不需要將其他元素位移。所以隨機增刪效率較高
雙向連結串列
雙向連結串列的查詢方式是交替查詢，就是左表查詢一個，右邊查詢一個，最終左表跟右邊誰先返回，那麼誰就先找到；
雙向連結串列就是雙向開工，最後離誰近我返回誰，說白就是誰查的次數最少，我返回誰；
LinkedList底層講解
那麼，連結串列結構在底層儲存的是什麼結構呢？
Node（節點），它底層儲存的是Node，一個節點一個節點的；
我們點進原始碼後我們開始進行分析：
transient int size = 0;
我們點進原始碼後，看到的第一個屬性就是 size =0；
這句話的意思就是，LinkedList初始值是0，也就是，你沒有給它任何資料的時候，它的長度為0；
再往下看：
transient Node<E> first;//代表第一個節點 /** * Pointer to last node. * Invariant: (first == null && last == null) || *(last.next == null && last.item != null) */
我們看到了Node，Node這個物件，就代表連結串列中的每一個元素；
我們點進去看一下，Node裡面有什麼：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
我們點進去後，第一行有一個E，這個E是幹什麼的呢？
這個E就代表，本節點的資訊，比如說你這裡插入的資料的型別都是String型別，那麼這個節點的型別就是String，另外一個節點可能是int型別，double型別，那麼節點型別也就不同，所以這個E是個泛型；
再往下走，有一個next跟一個prev；
next代表下一個，prev代表前一個；
為什麼會有這兩個呢，是因為便於雙向查詢的時候能夠找到對方；
transient Node<E> last;//代表最後一個節點 /** * Constructs an empty list. */
我們看到在底層原始碼中，還有一個代表最後一個節點的方法，我們發現，兩個方法分別宣告，為什麼不寫在一起呢？
因為，最後一個節點的資訊，跟中間的資訊儲存的不一樣！
第一個節點只需要儲存，下一個節點，而最後一個節點只需要儲存上一個節點；
總結：
我需要知道的是LinkedList是一個連結串列結構，連結串列結構的特點是查詢慢 增刪快；
還有連結串列結構的每一個元素都是一個Node（節點），而Node的底層，就是一個雙向連結串列；
每個Node都會儲存三個資訊，prev item next；
Set集合
set集合特點：
無序、不重複；
這裡的無序是指，沒有新增順序；
它有兩個實現類，分別是 HashSet、TreeSet
首先我們先關注HashSet；
HashSet
建立一個HashSet集合：
Set<泛型> 物件名 = new HashSet<String>();
新增元素:
物件名.add("");
下面我們就做一些例子來更好的講一下HashSet集合；
1.建立一個HashSet賦值，並用增強for迴圈列印，新增相同元素觀察狀態；
Set<String> set01 = new HashSet<String>();
set.add("hh");
set.add("aa");
set.add("cc");
set.add("hh");
for(String str : set01){
syso(str);
}
執行結果我們會發現，我們明明新增進去了兩個，為什麼卻值打印出來一個hh？
這就是HashSet的特性，值不能重複；
那麼它是如何做到的呢，它是如何保證元素不重複的？
我們現在可以假設一下HashSet的底層是什麼，我們假設它底層是一個數組，那麼，陣列是如何做到元素不重複的呢？
是不是要從頭開始遍歷，直到遍歷結束後發現這個元素沒有出現過，那麼就表明這個元素確實為唯一未重複的；
但是，如果陣列的長度非常長，這個時候，你這樣的方法，還能行得通嗎？當然不行了，因為效能太低了！
它的底層確實是陣列，但是，缺不是這樣的遍歷方式，而是hash演算法；
所有元素儲存的時候，存的是hashcode的元素值，那個這個值是可以當成它索引；
hash演算法
*任何一種hashcode的演算法都無法達到絕對的完美*
*必然會存在hashcode值的衝突*
假如我現在要新增一個元素，加進來之後首先會計算這個值的hashcode值，如果這個hashcode值 = 50，那我就把你這個元素存到下標為50的陣列的對應位置上；
這個時候又假設又存進來一個“bb”，首先第一步還是需要先計算它的hashcode值，假設bb的hashcode值 = 25，那麼，它就會被分配到下標為25的數組裡；
這個時候我又存進來了一個元素“cc”，當你插入cc元素的時候，首先還是需要先算一個你這個元素的hashcode值，假設這個cc還等與25，那麼這個cc是不是也要去找相對應的下標為25的位置了，但是發現，這個25這個位置已經被bb佔用了，這個時候就會觸發底層的equals方法進行內容比較，如果內容相同，則不讓你插入，如果不同，那麼就會以列表的方式進行插入，就是掛在“bb”的下面；
在java1.5的時候，以上這個結構被稱之為，hashset桶表+連結串列；
在java1.8點時候，以上轉增結構被稱之為，桶表+連結串列+二叉樹；
為什麼要加二叉樹？
假設有許多hashcode的值 = 25，那麼你是不是就需要一直的往下掛呀；
大家都知道連結串列是有缺陷的，就是查詢慢！那你查的時候，是不是就是從第一個開始遍歷，去尋找啊，假設這個元素剛好在連結串列的最末端，那麼你需要查多久啊；
所以到1.8之後，為了避免這種情況出現，所以它對這個連結串列做了一個優化，連結串列深度超過8的時候，就會轉化成二叉樹
hashset底層程式碼分析
進去之後，首先第一句話：
private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map
看到這個map，就說明set跟map是有一定關係的，你說白了set的底層實現，事實上就是map的底層實現；
看一下set的底層構造方法：
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
* collection.The <tt>HashMap</tt> is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
*/
是HashMap；
所以點進去後你會發現，最後還是到了HashMap的底層裡面去了；
首先看第一行：
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
預設長度是 16；
再往下走：
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;
這個是最大容量，int的最大值/2；10億左右
再往下：
/** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f;
這個是預設載入因子；
也就是16元素，到第16*0.75（12）；
也就是到達12個元素即將到達第13個元素的時候，它就開始擴容，並以二倍的速度開始擴的；
再往下看：
/** * The bin count threshold for using a tree rather than list for a * bin.Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8;
這個就是樹結構控制；
每個連結串列達到8之後，就開始自動轉化為二叉樹結構；
什麼是時候會觸發連結串列啊？
hash演算法相同的時候會把值相同的放到同一個連結串列上；