尚硅谷JAVA笔记
目錄
StringBuffer和StringBuilder的底層實現
List及其子類底層實現
Set及其子類底層實現
Map及其子類底層實現
其他
StringBuffer和StringBuilder的底層實現
（文章只講了部分，詳細請移步StringBuilder與StringBuffer的底層原理實現）：
注：StringBuilder與stringBuffer相同底層原理相同只是stringbuffer加了鎖,下面以stringbuilder為例
1.StringBuffer和StringBuilder都繼承了AbstractStringBuilder
2.new StringBuilder()對象時：
①如果傳入參數為空，默認造一個長度為16的char型數組
②如果傳入的參數為int型整數，造一個整數大小的char型數組
③如果傳入的參數為string類型的字符串，造一個（字符串長度+16）大小的char型數組，然后調用append()方法
3.擴容問題:
一般擴容為初始容量的二倍加2，即 擴容容量 = 原來容量*2+2
4.線程安全問題:
StringBuilder為線程不安全的,StringBuffer為線程安全的
5.效率問題:
由第四點很容易得出，StringBuild的效率 > StringBuffer的效率 >String?
List及其子類底層實現
1. List接口框架
? ? |----Collection接口：單列集合，用來存儲一個一個的對象
? ? ? ? |----List接口：存儲有序的、可重復的數據。 ?-->“動態”數組,替換原有的數組
? ? ? ? ? ?|----ArrayList：作為List接口的主要實現類；線程不安全的，效率高；底層使用Object[] elementData存儲
? ? ? ? ? ?|----LinkedList：對于頻繁的插入、刪除操作，使用此類效率比ArrayList高；底層使用雙向鏈表存儲
? ? ? ? ? ?|----Vector：作為List接口的古老實現類；線程安全的，效率低；底層使用Object[] elementData存儲
2.ArrayList底層源碼實現
jdk 7：
ArrayList list = new ArrayList();//底層創建了長度是10的Object[ ]數組elementData
list.add(123);//elementData[0] = new Integer(123);
...(一系列的增刪查改操作)
list.add(11);//如果此次的添加導致底層elementData數組容量不夠，則擴容。
注：默認情況下，擴容為原來的容量的1.5倍，同時需要將原有數組中的數據復制到新的數組中。即 擴容容量 = 原來容量 * 1.5
jdk 8：
ArrayList list = new ArrayList();//底層Object[] elementData初始化為{ }.并沒有創建長度為10的數組
list.add(123);//第一次調用add()時，底層才創建了長度10的數組，并將數據123添加到elementData[0]
...(一系列的增刪查改操作)
其他的操作幾乎一樣
jdk7與jdk8的對比：
jdk7中的ArrayList的對象的創建類似于單例的餓漢式，而jdk8中的ArrayList的對象的創建類似于單例的懶漢式，延遲了數組的創建，節省內存。
3.LinkedList底層源碼實現
- 對于頻繁的插入或刪除元素的操作，建議使用LinkedList類，效率較高
- LinkedList：雙向鏈表，內部沒有聲明數組，而是定義了Node類型的first和last，用于記錄首末元素。同時，定義內部類Node，作為LinkedList中保存數據的基本結構。
?LinkedList的源碼分析：
? * ? ? ? LinkedList list = new LinkedList(); 內部聲明了Node類型的first和last屬性，默認值為null
? * ? ? ? list.add(123);//將123封裝到Node中，創建了Node對象。
? *
? * ? ? ? 其中，Node定義為：體現了LinkedList的雙向鏈表的說法
? * ? ? ? 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; ? ? //next變量記錄下一個元素的位置
? * ? ? ? ? ? ?this.prev = prev; ? ? //prev變量記錄前一個元素的位置
? * ? ? ? ? ? ?}
? * ? ? ? ?}
4.Vector
Vector 是一個古老的集合，JDK1.0就有了。大多數操作與ArrayList相同，區別之處在于Vector是線程安全的。
注：在各種list中，最好把ArrayList作為缺省選擇。當插入、刪除頻繁時，使用LinkedList；Vector總是比ArrayList慢，所以盡量避免使用。（而且這個類太古老了，基本不會使用了現在）
擴容分析：jdk7和jdk8中通過Vector()構造器創建對象時，底層都創建了長度為10的數組。在擴容方面，默認擴容為原來的數組長度的2倍。即 擴容容量 = 原來容量 * 2。
Set及其子類底層實現
Set:存儲無序的、不可重復的數據
無序性：不等于隨機性。存儲的數據在底層數組中并非按照數組索引的順序添加，而是根據數據的哈希值決定的。
不可重復性：保證添加的元素按照equals()判斷時，不能返回true.即：相同的元素只能添加一個
Set接口是Collection的子接口，set接口沒有提供額外的方法
Set 集合不允許包含相同的元素，如果試把兩個相同的元素加入同一個Set 集合中，則添加操作失敗。
Set 判斷兩個對象是否相同不是使用==運算符，而是根據equals()方法?
?1.Set接口框架
?* |----Collection接口：單列集合，用來存儲一個一個的對象
?* ? ? ? ? ?|----Set接口：存儲無序的、不可重復的數據 ? -->高中講的“集合”
?* ? ? ? ? ? ? |----HashSet：作為Set接口的主要實現類；線程不安全的；可以存儲null值
?* ? ? ? ? ? ? ? ? |----LinkedHashSet：作為HashSet的子類；遍歷其內部數據時，可以按照添加的順序遍歷
?* ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?對于頻繁的遍歷操作，LinkedHashSet效率高于HashSet.
?* ? ? ? ? ? ? |----TreeSet：可以按照添加對象的指定屬性，進行排序。
2.HashSet
HashSet是Set 接口的典型實現，大多數時候使用Set 集合時都使用這個實現類。
HashSet按Hash 算法來存儲集合中的元素，因此具有很好的存取、查找、刪除性能。
HashSet具有以下特點：不能保證元素的排列順序
HashSet不是線程安全的
集合元素可以是null
底層也是數組，初始容量為16，當如果使用率超過0.75，（16*0.75=12）就會擴大容量為原來的2倍。（16擴容為32，依次為64,128…等）
HashSet 集合判斷兩個元素相等的標準：兩個對象通過hashCode() 方法比較相等，并且兩個對象的equals()方法返回值也相等。
對于存放在Set容器中的對象，對應的類一定要重寫equals()和hashCode(Object obj)方法，以實現對象相等規則。即：“相等的對象必須具有相等的散列碼”。
HashSet底層添加數據過程：
? ? ?* ? ? ?我們向HashSet中添加元素a,首先調用元素a所在類的hashCode()方法，計算元素a的哈希值，
? ? ?* ? ? ?此哈希值接著通過某種算法計算出在HashSet底層數組中的存放位置（即為：索引位置），判斷
? ? ?* ? ? ?數組此位置上是否已經有元素：
? ? ?* ? ? ? ? ?如果此位置上沒有其他元素，則元素a添加成功。 --->情況1
? ? ?* ? ? ? ? ?如果此位置上有其他元素b(或以鏈表形式存在的多個元素），則比較元素a與元素b的hash值：
? ? ?* ? ? ? ? ? ? ?如果hash值不相同，則元素a添加成功。--->情況2
? ? ?* ? ? ? ? ? ? ?如果hash值相同，進而需要調用元素a所在類的equals()方法：
? ? ?* ? ? ? ? ? ? ? ? ? ?equals()返回true,元素a添加失敗
? ? ?* ? ? ? ? ? ? ? ? ? ?equals()返回false,則元素a添加成功。--->情況2
? ? ?*
? ? ?* ? ? ?對于添加成功的情況2和情況3而言：元素a 與已經存在指定索引位置上數據以鏈表的方式存儲。
? ? ?* ? ? ?jdk 7 :元素a放到數組中，指向原來的元素。
? ? ?* ? ? ?jdk 8 :原來的元素在數組中，指向元素a
? ? ?* ? ? ?總結：七上八下
? ? ?*
? ? ?* HashSet底層：數組+鏈表的結構。
?注：關于HashCode()和equals()的重寫
直接用編譯器里面的重寫快捷鍵重寫就完事了，而且不易出錯。
3.LinkedHashSet
LinkedHashSet是HashSet的子類。
LinkedHashSet根據元素的hashCode值來決定元素的存儲位置，但它同時使用雙向鏈表維護元素的次序，這使得元素看起來是以插入順序保存的。
LinkedHashSet插入性能略低于HashSet，但在迭代訪問Set 里的全部元素時有很好的性能。
LinkedHashSet不允許集合元素重復。
優點：對于頻繁的遍歷操作，LinkedHashSet效率高于HashSet
4.TreeSet
- TreeSet是SortedSet接口的實現類，TreeSet可以確保集合元素處于排序狀態。
- TreeSet底層使用紅黑樹結構存儲數據
- TreeSet兩種排序方法：自然排序和定制排序。默認情況下，TreeSet采用自然排序。（關于TreeSet這兩種排序方法，可以看尚硅谷的視頻）
- 特點：有序，查詢速度比List快
- 如果試圖把一個對象添加到TreeSet時，則該對象的類必須實現Comparable 接口。
- 實現Comparable?的類必須實現compareTo(Object obj)方法，兩個對象即通過compareTo(Object obj)方法的返回值來比較大小。
- 注：因為只有相同類的兩個實例才會比較大小，所以向TreeSet中添加的應該是同一個類的對象。
- 對于TreeSet集合而言，它判斷兩個對象是否相等的唯一標準是：兩個對象通過compareTo(Object obj)方法比較返回值。
當需要把一個對象放入TreeSet中，重寫該對象對應的equals()方法時，應保證該方法與compareTo(Object obj) 方法有一致的結果：如果兩個對象通過equals()方法比較返回true，則通過compareTo(Object obj)方法比較應返回0。否則，讓人難以理解。
Map及其子類底層實現
?* 1.Map的實現類的結構：
?* ?|----Map:雙列數據，存儲key-value對的數據 ? ---類似于高中的函數：y = f(x)
?* ? ? ? ? |----HashMap:作為Map的主要實現類；線程不安全的，效率高；存儲null的key和value
?* ? ? ? ? ? ? ?|----LinkedHashMap:保證在遍歷map元素時，可以按照添加的順序實現遍歷。
?* ? ? ? ? ? ? ? ? ? ? ?原因：在原有的HashMap底層結構基礎上，添加了一對指針，指向前一個和后一個元素。
?* ? ? ? ? ? ? ? ? ? ? ?對于頻繁的遍歷操作，此類執行效率高于HashMap。
?* ? ? ? ? |----TreeMap:保證按照添加的key-value對進行排序，實現排序遍歷。此時考慮key的自然排序或定制排序
?* ? ? ? ? ? ? ? ? ? ? ?底層使用紅黑樹
?* ? ? ? ? |----Hashtable:作為古老的實現類；線程安全的，效率低；不能存儲null的key和value
?* ? ? ? ? ? ? ?|----Properties:常用來處理配置文件。key和value都是String類型
?*
?*
?* ? ? ?HashMap的底層：數組+鏈表 ?（jdk7及之前）
?* ? ? ? ? ? ? ? ? ? ?數組+鏈表+紅黑樹 （jdk 8）
2.Map中存儲的key-value的特點
Map與Collection并列存在。用于保存具有映射關系的數據:key-value
Map中的key和value都可以是任何引用類型的數據
Map 中的key 用Set來存放，不允許重復，即同一個Map 對象所對應的類，須重寫hashCode()和equals()方法
常用String類作為Map的“鍵”
key和value之間存在單向一對一關系，即通過指定的key總能找到唯一的、確定的value。
Map接口的常用實現類：HashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是Map接口使用頻率最高的實現類
3.HashMap
HashMap是Map接口使用頻率最高的實現類。
允許使用null鍵和null值，與HashSet一樣，不保證映射的順序。
所有的key構成的集合是Set:無序的、不可重復的。所以，key所在的類要重寫：equals()和hashCode()
所有的value構成的集合是Collection:無序的、可以重復的。所以，value所在的類要重寫：equals()
一個key-value構成一個entry
所有的entry構成的集合是Set:無序的、不可重復的
HashMap判斷兩個key相等的標準是：兩個key通過equals()方法返回true，hashCode值也相等。
HashMap判斷兩個value相等的標準是：兩個value 通過equals()方法返回true。
HashMap底層實現：
JDK 7及以前版本：HashMap是數組+鏈表結構(即為鏈地址法)
JDK 8版本發布以后：HashMap是數組+鏈表+紅黑樹實現。
4.HashMap中的重要常量
/*
?* ? ? ?DEFAULT_INITIAL_CAPACITY : HashMap的默認容量，16
?* ? ? ?DEFAULT_LOAD_FACTOR：HashMap的默認加載因子：0.75
?* ? ? ?threshold：擴容的臨界值，=容量*填充因子：16 * 0.75 => 12
?* ? ? ?TREEIFY_THRESHOLD：Bucket中鏈表長度大于該默認值，轉化為紅黑樹:8
?* ? ? ?MIN_TREEIFY_CAPACITY：桶中的Node被樹化時最小的hash表容量:64
*/
5.HashMap在JDK7中的底層實現原理
HashMap的內部存儲結構其實是數組和鏈表的結合。當實例化一個HashMap時，系統會創建一個長度為Capacity的Entry數組，這個長度在哈希表中被稱為容量(Capacity)，在這個數組中可以存放元素的位置我們稱之為“桶”(bucket)，每個bucket都有自己的索引，系統可以根據索引快速的查找bucket中的元素。
每個bucket中存儲一個元素，即一個Entry對象，但每一個Entry對象可以帶一個引用變量，用于指向下一個元素，因此，在一個桶中，就有可能生成一個Entry鏈。而且新添加的元素作為鏈表的head。
添加元素的過程：
向HashMap中添加entry1(key，value)，需要首先計算entry1中key的哈希值(根據key所在類的hashCode()計算得到)，此哈希值經過處理以后，得到在底層Entry[]數組中要存儲的位置i。
如果位置i上沒有元素，則entry1直接添加成功。
如果位置i上已經存在entry2(或還有鏈表存在的entry3，entry4)，則需要通過循環的方法，依次比較entry1中key的hash值和其他的entry的hash值。
如果彼此hash值不同，則直接添加成功。
如果hash值相同，繼續比較二者是否equals。如果返回值為true，則使用entry1的value去替換equals為true的entry的value。
如果遍歷一遍以后，發現所有的equals返回都為false,則entry1仍可添加成功。entry1指向原有的entry元素。
6.HashMap在JDK8中的底層實現原理
HashMap的內部存儲結構其實是數組+鏈表+紅黑樹的結合。當實例化一個HashMap時，會初始化initialCapacity和loadFactor，在put第一對映射關系時，系統會創建一個長度為initialCapacity的Node數組，這個長度在哈希表中被稱為容量(Capacity)，在這個數組中可以存放元素的位置我們稱之為“桶”(bucket)，每個bucket都有自己的索引，系統可以根據索引快速的查找bucket中的元素
每個bucket中存儲一個元素，即一個Node對象，但每一個Node對象可以帶一個引用變量next，用于指向下一個元素，因此，在一個桶中，就有可能生成一個Node鏈。也可能是一個一個TreeNode對象，每一個TreeNode對象可以有兩個葉子結點left和right，因此，在一個桶中，就有可能生成一個TreeNode樹。而新添加的元素作為鏈表的last，或樹的葉子結點。
那么HashMap什么時候進行擴容和樹形化呢？
當HashMap中的元素個數超過數組大小(數組總大小length,不是數組中個數size)*loadFactor時，就會進行數組擴容，loadFactor的默認值(DEFAULT_LOAD_FACTOR)為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小(DEFAULT_INITIAL_CAPACITY)為16，那么當HashMap中元素個數超過16*0.75=12（這個值就是代碼中的threshold值，也叫做臨界值）的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然后重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。
當HashMap中的其中一個鏈的對象個數如果達到了8個，此時如果capacity沒有達到64，那么HashMap會先擴容解決，如果已經達到了64，那么這個鏈會變成紅黑樹，結點類型由Node變成TreeNode類型。當然，如果當映射關系被移除后，下次resize方法時判斷樹的結點個數低于6個，也會把紅黑樹再轉為鏈表。
關于映射關系的key是否可以修改？answer：不要修改
映射關系存儲到HashMap中會存儲key的hash值，這樣就不用在每次查找時重新計算每一個Entry或Node（TreeNode）的hash值了，因此如果已經put到Map中的映射關系，再修改key的屬性，而這個屬性又參與hashcode值的計算，那么會導致匹配不上。
二者總結：
/*????? jdk8 相較于jdk7在底層實現方面的不同：
?* ? ? ?1.new HashMap():底層沒有創建一個長度為16的數組
?* ? ? ?2.jdk 8底層的數組是：Node[],而非Entry[]
?* ? ? ?3.首次調用put()方法時，底層創建長度為16的數組
?* ? ? ?4.jdk7底層結構只有：數組+鏈表。jdk8中底層結構：數組+鏈表+紅黑樹。
?* ? ? ? ? 4.1形成鏈表時，七上八下（jdk7:新的元素指向舊的元素。jdk8：舊的元素指向新的元素）
?* ? ? ? ? 4.2當數組的某一個索引位置上的元素以鏈表形式存在的數據個數 > 8 且當前數組的長度 > 64時，此時此索引位置上的所數據改為使用紅黑樹存儲。
?*/
7.HashMap的擴容
/*
? * HashMap的擴容
? * ? ? 當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，
? * ? ? 因為數組的長度是固定的。所以為了提高查詢的效率，
? * ? ? 就要對HashMap的數組進行擴容，而在HashMap數組擴容之后，
? * ? ? 最消耗性能的點就出現了：原數組中的數據必須重新計算其在新數組中的位置，
? * ? ? 并放進去，這就是resize。
? * ? ??
? * 那么HashMap什么時候進行擴容呢？
? * ? ? ?當HashMap中的元素個數超過數組大小(數組總大小length,
? * ? ? ?不是數組中個數size)*loadFactor時，就 會 進 行 數 組 擴 容，
? * ? ? ?loadFactor的默認值(DEFAULT_LOAD_FACTOR)為0.75，這是一個折中的取值。
? * ? ? ?也就是說，默認情況下，數組大小(DEFAULT_INITIAL_CAPACITY)為16，
? * ? ? ?那么當HashMap中元素個數超過16*0.75=12（這個值就是代碼中的threshold值，
? * ? ? ?也叫做臨界值）的時候，就把數組的大小擴展為2*16=32，即擴大一倍，
? * ? ? ?然后重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，
? * ? ? ?所以如果我們已經預知HashMap中元素的個數，
? * ? ? ?那么預設元素的個數能夠有效的提高HashMap的性能。
? */
8.LinkedHashMap的底層實現原理
LinkedHashMap是HashMap的子類
在HashMap存儲結構的基礎上，使用了一對雙向鏈表來記錄添加元素的順序
與LinkedHashSet類似，LinkedHashMap可以維護Map 的迭代順序：迭代順序與Key-Value 對的插入順序一致
HashMap中的內部類：Node
其他
?如果有錯誤，歡迎評論指出！謝謝！
來源聲明：文章關于一些底層代碼實現的文章基本上來自于這位博主的總結
大佬根據尚硅谷視頻做的筆記
總結
- 上一篇： 前端机器学习——线性回归
- 下一篇： 快速非支配排序算法流程