Collection集合
在collection接口之上還有一個Iterable接口，也就意味著這一組集合全部都可以通過迭代器來操作。
繼承了Collection的抽象類abstractCollection實現(xiàn)了大部分通用的操作,以便于子類的使用.
List集合
list作為有序集合，定義了多個可以隨機訪問的接口,list集合可以通過兩種方式來訪問
- 迭代器訪問，必須順序訪問
- 整數(shù)索引訪問，隨機訪問
鏈表更適合迭代器訪問,數(shù)組適合索引訪問,java1.4引入了RandomAccess接口,用來標識是否支持高效隨機訪問.
不得不提Iterator接口,LIstIterator是Iterator的子接口,定義了在迭代器之前增加add()方法以及可以反向遍歷的兩個方法:previous() ,hasPervious(),列表迭代器有保持位置的計數(shù)器
LinkedList
鏈表數(shù)據(jù)結(jié)構(gòu),LinkedList雖然提供了隨機訪問的方法,但是其實是"虛假的",例如:
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
link.add("小汪汪");
link.add("小張張");
link.add("小黃黃");
for (int i = 0; i < link.size(); i++) {
System.out.println(link.get(i));
}
}
在語法上支持隨機訪問,其實并不是,每一次遍歷元素都要從頭開始,linkedlist不存儲位置信息.因此,進行隨機訪問使用arraylist.
Arraylist
數(shù)組集合,封裝了一個動態(tài)再分配的對象數(shù)組,支持高速隨機訪問.
Vector
Vector極少使用,不過多贅述,可以理解為線程安全的ArrayList。
- List常見實現(xiàn)類
ArrayList，LinkedList，Vector - ArrayList ,LinkedList的區(qū)別
數(shù)組，訪問速度快，便于查詢。鏈表，插入刪除快，訪問慢，不支持隨機訪問。 - List集合的擴容機制
ArrayList：初始長度為10，可指定長度。未添加數(shù)據(jù)前為0，添加一個數(shù)據(jù)增長到10。通過grow()方法按照原來數(shù)據(jù)的1.5倍增長。最大長度為Integer.MAX_VALUE或者Integer.MAX_VALUE-8.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector：grow()方法，按照原來數(shù)據(jù)長度的兩倍增長。
LinkedList：鏈表，節(jié)點增加數(shù)據(jù)即可。
Set集合
HashSet
散列表:
為了能夠快速查找到指定元素,但是又不知道元素的位置,就需要遍歷全部數(shù)據(jù),當數(shù)據(jù)過多時,就會消耗大量的時間.散列表就可以快速訪問數(shù)據(jù),不同的數(shù)據(jù)對象就有不同的散列碼.注意:要與equals方法保持一致,如果兩個數(shù)據(jù)相同,那么散列碼也要保持相同.
散列表基于鏈表數(shù)組實現(xiàn)，每個列表被稱為桶，計算散列碼，與桶的總數(shù)取余，插入對應的桶中，這個操作可能會發(fā)生散列沖突。在java8以后，當桶滿時從鏈表轉(zhuǎn)化為平衡二叉樹，提高性能。
如果想更多控制性能，大致知道有多少個元素，通常將桶數(shù)設定為元素個數(shù)的75%到150%。
當然大部分并不知道有多少個元素，裝填因子可以確定什么時候散列表再散列，通常設定為0.75，如果表中元素填滿了75%以上，就再散列，是原來的2倍。
contains()方法已經(jīng)被重新定義，只查看一個元素不再遍歷，迭代器依次按順序遍歷所有元素，并非隨機訪問。不關心元素順序使用Hashset。
TreeSet
樹集是一個有序集合,可將數(shù)據(jù)自動排序,添加數(shù)據(jù)效率比散列表稍慢,但查找速度要快,速度為Log以2為底的N次方。結(jié)合Compareable接口或提供comparetor方法實現(xiàn)排序。
Map
HashMap和TreeMap與hashSet和treeSet底層是相同的，散列映射將鍵進行散列，樹映射根據(jù)鍵的順序組織為一個搜索樹。散列與比較函數(shù)只能作用于鍵。
映射視圖
集合框架并不認為映射本身就是一個集合，但是可以得到視圖。
三種視圖：
Set<K> keySet()
Collection<V> values()
Set<Map.Entry(k,v)> entrySet<>
利用lamda表達式,遍歷Map集合:
HashMap<String, String> map = new HashMap<String, String>();
map.put("f","f");
map.put("x", "x");
map.forEach((k,v)->System.out.println(k+v))
鏈接散列集映射
LinkedHashset和LinkedHashMap會記住插入元素項的順序。在表中插入元素時，就會并入到雙向鏈表。
HashTable
與HashMap作用一樣，接口也基本相同。與vector一樣，方法是同步的，如果對兼容性沒要要求，就使用HashMap。如果需要并發(fā)訪問，應該使用ConcurrentHashMap。
擴容機制：初始容量為11，每次擴容變?yōu)樵瓉淼?n+1.
- HashMap 的長度為什么是2的冪次方?
在散列表中，進行取余操作，使用的是hash%length=hash&(length-1)。兩個操作相同，&運算的效率更高，但是長度必須是2的n次方。
