Collection
一、List (有序，可重復)
1、ArrayList底層用陣列實作，執行緒不安全，效率高
2、LinkedList:底層用雙向鏈表實作，執行緒不安全，效率高
3、Vector:底層用陣列實作，執行緒安全，效率低
4、和陣列類似，List可以動態增長，查找元素效率高，插入洗掉元素效率低，因為會引起其他元素位置改變
二、Set (無序，不可重復)
HashSet(內部是使用HashMap實作)
檢索元素效率低下，洗掉和插入效率高，插入和洗掉不會引起元素位置改變
向 HashSet 中 add ()元素時，判斷元素是否存在的依據，不僅要比較hash值，同時還要結合 equles 方法比較，當添加元素時先判斷插入元素hashcode值是否和集合中的某個元素相同，若不相同則可以允許插入集合，若相同則equals比較兩個元素是否相等，若相等則覆寫原來的元素不會產生新的元素，若不相等則允許插入集合產生一個新元素，借此實作Set中元素不可重復的特點，HashSet 中的 add ()方法會使用 HashMap 的 add ()方法，就是把插入元素作為map的key來進行上述邏輯判斷，
Map
采用“key-value”來存盤我們資料，
一、HashMap
1、執行緒不安全，效率高
如果有兩個執行緒A和B，都進行插入資料，剛好這兩條不同的資料經過哈希計算后得到的哈希碼是一樣的，且該位置還沒有其他的資料，假設一種情況，執行緒A通過if判斷，該位置沒有哈希沖突，進入了if陳述句，還沒有進行資料插入，這時候 CPU 就把資源讓給了執行緒B，執行緒A停在了if陳述句里面，執行緒B判斷該位置沒有哈希沖突（執行緒A的資料還沒插入），也進入了if陳述句，執行緒B執行完后，輪到執行緒A執行，現在執行緒A直接在該位置插入而不用再判斷，這時候，你會發現執行緒A把執行緒B插入的資料給覆寫了，發生了執行緒不安全情況，本來在 HashMap 中，發生哈希沖突是可以用鏈表法或者紅黑樹來解決的，但是在多執行緒中，可能就直接給覆寫了，
上面所說的是一個圖來解釋可能更加直觀，如下面所示，兩個執行緒在同一個位置添加資料，后面添加的資料就覆寫住了前面添加的，
2、HashMap擴容
當向容器添加元素的時候,會判斷當前容器的元素個數,如果大于等于閾值即當前陣列的長度乘以加載因子的值的時候,就要自動擴容啦，
擴容( resize )就是重新計算容量,向HashMap物件里不停的添加元素,而HashMap物件內部的陣列無法裝載更多的元素時,物件就需要擴大陣列的長度,以便能裝入更多的元素，當然Java里的陣列是無法自動擴容的,方法是使用一個新的陣列代替已有的容量小的陣列,就像我們用一個小桶裝水,如果想裝更多的水,就得換大水桶，
HashMap hashmap=new HashMap(cap) ;
cap =3，hashMap 的容量為4 ;
cap =4，hashMap 的容量為4 ;
cap =5，hashMap 的容量為8 ;
cap =9，hashmap 的容量為16 ;
如果cap是2的n次方,則容量為cap ,否則為大于cap的第一個2的n次方的數，
小知識：
JDK1.7及之前的版本中，HashMap 又叫散列鏈表:基于-個陣列以及 多個鏈表的實作, hash值沖突的時候,就將對應節點以鏈表的形式存盤，
使用一個Entry陣列來存盤資料,用key的hashcode取模來決定key會被放到陣列里的位置,如果hashcode相同,或者hashcode取模后的結果相同( hash collision) , 那么這些key會被定位到Entry陣列的同一個格子里,這些key會形成一個鏈表，在hashcode特別差的情況下,比方說所有key的hashcode都相同,這個鏈表可能會很長,那么put/get操作都可能需要遍歷這個鏈表,也就是說時間復雜度在最差情況下會退化到o(n)
JDK1.8中,當同一個hash值( Table上元素)的鏈表節點數不小于8時,將不再以單鏈表的形式存盤了,會被調整成一顆紅黑樹，這就是JDK7與JDK8中HashMap實作的最大區別，
使用一個Node陣列來存盤資料,但這個Node可能是鏈表結構,也可能是紅黑樹結構
●如果插入的key的hashcode相同,那么這些key也會被定位到Node陣列的同一個格子里，
●如果同一個格子里的key不超過8個,使用鏈表結構存盤，
●如果超過了8個,那么會呼叫treeifyBin函式,將鏈表轉換為紅黑樹，
那么即使hashcode完全相同,由于紅黑樹的特點,查找某個特定元素,也只需要0(log n)的開銷也就是說put/get的操作的時間復雜度最差只有0(log n),聽起來挺不錯,但是真正想要利用JDK1.8 的好處,有一個限制:key的物件,必須正確的實作了Compare 介面,如果沒有實作Compare介面,或者實作得不正確(比方說所有Compare 方法都回傳0 ),那JDK1.8的HashMap其實還是慢于JDK1.7的
二、HashTable 執行緒安全，效率低
Iterator
通過他，可以實作遍歷容器中元素
泛型
預定義容器里面資料型別
Collections 工具類
便于對容器操作
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/150677.html
標籤：Java
上一篇：Java記憶體機制
下一篇：多執行緒