接口
- 集合有兩個(gè)基本接口 Collection 和 Map
- List 是一個(gè)有序集合衙熔。元素會(huì)增加到容器中的特定位置嫉你。
- Set<E>集月帝。Set 接口等同于 Collection 接口，不過其方法的行為有更嚴(yán)謹(jǐn)?shù)亩x幽污，不能添加重復(fù)的對(duì)象
- Iterator<E>
- iterator.forEachRemaining(element -> do something with element);
- iterator.next()嚷辅，當(dāng)調(diào)用 next 時(shí)，迭代器就越過下一個(gè)元素距误，并返回剛剛越過的那個(gè)元素的引用簸搞。
- iterator.remove()，將會(huì)刪除上次調(diào)用 next 方法時(shí)返回的元素深寥。
it.next(); // skip over the first element
it.remove(); // now remove it
- ListIterator 定義了一個(gè)方法用于在迭代器位置前面增加一個(gè)元素攘乒。void add(E element)
- RandomAccess 為標(biāo)記接口，不包含任何方法惋鹅≡蛟停可以用來測(cè)試一個(gè)特定的集合是否支持高效的隨機(jī)訪問。
if (c instanceof RandomAccess){
use random access algorithm
else{
use sequential access algorithm
}
類
- ArrayList 可以動(dòng)態(tài)增長(zhǎng)和縮減的索引序列
- LinkedList 可以在任何位置進(jìn)行高效地插人和刪除操作的有序序列
- ArrayDeque 用循環(huán)數(shù)組實(shí)現(xiàn)的雙端隊(duì)列
- HashSet 沒有重復(fù)元素的無序集
- TreeSet 有序集
- EnumSet 包含枚舉類型值的集
- LinkedHashSet 可以記住元素插人次序的集
- PriorityQueue 允許高效刪除最小元素的集合
- HashMap 存儲(chǔ)鍵 / 值關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)
- TreeMap 鍵值有序排列的映射表
- EnumMap 鍵值屬于枚舉類型的映射表
- LinkedHashMap 可以記住鍵 / 值項(xiàng)添加次序的映射表
- WeakHashMap 其值無用武之地后可以被垃圾回收器回收的映射表
- IdentityHashMap 用 = 而不是用 equals 比較鍵值的映射表
鏈表
Java 程序設(shè)計(jì)語言中闰集， 所有鏈表實(shí)際上都是雙向鏈接的沽讹。LinkedList
注意iterator的位置（“光標(biāo)”）
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("this");
linkedList.add("is");
linkedList.add("a");
linkedList.add("sentence");
ListIterator<String> iterator = linkedList.listIterator();
while (iterator.hasNext()){
if (iterator.next() == "sentence")
iterator.add("complete");
}
- 用“ 光標(biāo)” 類比時(shí)要格外小心。remove 操作與 BACKSPACE 鍵的工作方式不太一樣武鲁。在調(diào)用 next 之后爽雄， remove 方法確實(shí)與 BACKSPACE 鍵一樣刪除了迭代器左側(cè)的元素。但是沐鼠， 如果調(diào)用 previous 就會(huì)將右側(cè)的元素刪除掉挚瘟， 并且不能連續(xù)調(diào)用兩次remove
- add 方法只依賴于迭代器的位置叹谁， 而 remove 方法依賴于迭代器的狀態(tài)。
- 如果在某個(gè)迭代器修改集合時(shí)乘盖， 另一個(gè)迭代器對(duì)其進(jìn)行遍歷焰檩， 一定會(huì)出現(xiàn)混亂的狀況。鏈表迭代器的設(shè)計(jì)使它能夠檢測(cè)到這種修改订框。 如果迭代器發(fā)現(xiàn)它的集合被另一個(gè)迭代器修改了析苫， 或是被該集合自身的方法修改了，就會(huì)拋出一個(gè)ConcurrentModificationException 異常穿扳。
數(shù)組列表
List 接口用于描述一個(gè)有序集合衩侥，并且集合中每個(gè)元素的位置十分重要。 訪問元素兩種方法：
- 迭代器矛物。適用于鏈表
- get和set方法隨機(jī)訪問茫死。適用于數(shù)組
ArrayList 數(shù)組列表，封裝了一個(gè)動(dòng)態(tài)再分配的對(duì)象數(shù)組泽谨。比較 Vector璧榄，其方法都是同步的，一個(gè)線程訪問 Vector, 代碼要在同步操作上耗費(fèi)大量的時(shí)間吧雹。在不需要同步時(shí)使用 ArrayList, 而不要使用 Vector。
散列集
鏈表和數(shù)組可以按照人們的意愿排列元素的次序涂身。但是如果想要査看某個(gè)指定的元素雄卷， 卻又忘記了它的位置， 就需要訪問所有元素蛤售， 直到找到為止丁鹉。所以，數(shù)據(jù)結(jié)構(gòu)散列表上場(chǎng)啦
散列表為每個(gè)對(duì)象計(jì)算一個(gè)整數(shù)悴能， 稱為散列碼（hash code)揣钦，是由對(duì)象的實(shí)例域產(chǎn)生的一個(gè)整數(shù)。
在 Java 中漠酿，散列表用鏈表數(shù)組實(shí)現(xiàn)冯凹。每個(gè)列表被稱為桶 （ bucket ) 。
對(duì)象位置的計(jì)算：計(jì)算它的散列碼炒嘲， 然后與桶的總數(shù)取余宇姚。
例如， 如果某個(gè)對(duì)象的散列碼為 76268, 并且有 128 個(gè)桶夫凸， 對(duì)象應(yīng)該保存在第 108 號(hào)桶中（ 76268除以 128余 108 )直接插入到桶中即可浑劳。 不幸的是，當(dāng)桶被占滿時(shí)夭拌，發(fā)生散列沖突（ hash collision) 魔熏，需要用新對(duì)象與桶中的所有對(duì)象進(jìn)行比較衷咽，査看這個(gè)對(duì)象是否已經(jīng)存在 。
通常蒜绽， 將桶數(shù)設(shè)置為預(yù)計(jì)元素個(gè)數(shù)的 75% ~ 150%镶骗。
如果散列表太滿， 就需要再散列 （rehashed)滓窍。 如果要對(duì)散列表再散列卖词， 就需要?jiǎng)?chuàng)建一個(gè)桶數(shù)更多的表，并將所有元素插入到這個(gè)新表中吏夯， 然后丟棄原來的表此蜈。裝填因子（ load factor) 決定何時(shí)對(duì)散列表進(jìn)行再散列。如果裝填因子為 0.75 (默認(rèn)值噪生，) 而表中超過 75%的位置已經(jīng)填人元素裆赵， 這個(gè)表就會(huì)用雙倍的桶數(shù)自動(dòng)地進(jìn)行再散列。
散列表可以用于集Set中跺嗽，Set的add方法首先在集中查找要添加的對(duì)象战授，如果不存在才添加進(jìn)去。
散列集迭代器將依次訪問所有的桶桨嫁。 由于散列將元素分散在表的各個(gè)位置上植兰，所以訪問它們的順序幾乎是隨機(jī)的。只有不關(guān)心集合中元素的順序時(shí)才應(yīng)該使用 HashSet璃吧。
可以看到HashSet實(shí)際就是HashMap
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
樹集
TreeSet 比散列集有所改進(jìn)楣导，是有序集。實(shí)現(xiàn)使用的是紅黑樹畜挨。
SortedSet<Item> parts = new TreeSet<>();
parts.add(new Item("Hello", 1));
parts.add(new Item("This", 2));
parts.add(new Item("Is", 3));
NavigableSet<Item> sortByDescription = new TreeSet<>(
Comparator.comparing(Item::getDescription));
sortByDescription.addAll(parts);
隊(duì)列與雙端隊(duì)列
支持在頭部/尾部添加或刪除元素筒繁。不支持在隊(duì)列中間添加元素。ArrayDeque和LinkedList都提供了雙端隊(duì)列
優(yōu)先級(jí)隊(duì)列
priorityQueue 可以按照任意的順序插入元素巴元。優(yōu)先級(jí)隊(duì)列并沒有對(duì)所有的元素進(jìn)行排序毡咏，卻總是按照排序的順序進(jìn)行檢索。使用的數(shù)據(jù)結(jié)構(gòu)為堆逮刨。堆是一個(gè)可以自我調(diào)整的二叉樹呕缭，對(duì)樹執(zhí)行添加 （ add) 和刪除（remove) 操作， 可以讓最小或最大的元素移動(dòng)到根禀忆，而不必花費(fèi)時(shí)間對(duì)元素進(jìn)行排序臊旭。
迭代不是按照元素的排列順序訪問。
而無論何時(shí)調(diào)用 remove 方法箩退，總會(huì)獲得當(dāng)前優(yōu)先級(jí)隊(duì)列中最小的元素离熏。
可以指定比較器進(jìn)行排序。
PriorityQueue<Item> itemPriorityQueue = new PriorityQueue<>(Comparator.comparing(Item::getPartNumber));
itemPriorityQueue.addAll(parts);
映射
鍵-值對(duì)戴涝。HashMap 和 TreeMap
- 散列映射對(duì)鍵進(jìn)行散列滋戳。
- 樹映射用鍵的整體順序?qū)υ剡M(jìn)行排序钻蔑， 并將其組織成搜索樹
- 散列或比較函數(shù)只能作用于鍵。
- 與集一樣奸鸯， 散列稍微快一些咪笑， 如果不需要按照排列順序訪問鍵， 就最好選擇散列
- 設(shè)值時(shí)候需要之一NullPointerExp情況
HashMap<String, String> hashMap = new HashMap<>();
hashMap.putIfAbsent("word", "");
hashMap.put("word", hashMap.get("word") + "string");
hashMap.put("word", hashMap.getOrDefault("word", "defaultStr"));
hashMap.merge("word","defaultStr",String::concat);
映射視圖
鍵集娄涩、值集合窗怒、鍵/值對(duì)集。
Set<String> hashMapKeySet = hashMap.keySet();
Collection<String> hashMapValues = hashMap.values();
Set<Map.Entry<String,String>> hashMapEntrySet = hashMap.entrySet();
遍歷鍵值對(duì)集更快速方法：
hashMap.forEach((k,v) -> {
// do sth. with k v
});
弱散列映射
假定對(duì)某個(gè)鍵的最后一次引用已經(jīng)消亡蓄拣，不再有任何途徑引用這個(gè)值的對(duì)象了扬虚。為什么垃圾回收器不能夠刪除它呢？答：垃圾回收器跟蹤活動(dòng)的對(duì)象球恤。只要映射對(duì)象是活動(dòng)的辜昵，其中的所有桶也是活動(dòng)的， 它們不能被回收咽斧。
WeakHashMap 當(dāng)對(duì)鍵的唯一引用來自散列條目時(shí)堪置， 這一數(shù)據(jù)結(jié)構(gòu)將與垃圾回收器協(xié)同工作一起刪除鍵 / 值對(duì)。
機(jī)制：WeakHashMap 使用弱引用保存鍵张惹。如果某個(gè)對(duì)象只能由 WeakReference 引用舀锨， 垃圾回收器仍然回收它，但要將引用這個(gè)對(duì)象的弱引用放入隊(duì)列中宛逗。一個(gè)弱引用進(jìn)人隊(duì)列意味著這個(gè)鍵不再被他人使用雁竞， 并且已經(jīng)被收集起來。于是拧额， WeakHashMap 將刪除對(duì)應(yīng)的條目。
鏈接散列集與映射
LinkedHashSet LinkedHashMap 記住插入元素的順序彪腔。
訪問順序?qū)τ趯?shí)現(xiàn)高速緩存的“ 最近最少使用” 原則十分重要侥锦。
枚舉集與映射
EnumSet 枚舉類型元素集。
可以使用 Set 接口的常用方法來修改 EnumSet德挣。
EnumSet<Weekday> weekdays = EnumSet.allOf(Weekday.class);//返回一個(gè)包含給定枚舉類型的所有值的集恭垦。
EnumSet<Weekday> none = EnumSet.noneOf(Weekday.class);//返回一個(gè)空集，并有足夠的空間保存給定的枚舉類型所有的值
EnumSet<Weekday> workday = EnumSet.range(MONDAY, FRIDAY);//返回一個(gè)包含 from ? to 之間的所有值（包括兩個(gè)邊界元素）的集
EnumMap 是一個(gè)鍵類型為枚舉類型的映射格嗅。
視圖
方法返回一個(gè)包裝了接口的對(duì)象番挺。這種對(duì)象集合稱為視圖。
獲取不可修改的視圖
視圖的更改器方法拋出一個(gè) UnsupportedOperationException屯掖。
Collections 還有幾個(gè)方法玄柏， 用于產(chǎn)生集合的不可修改視圖。運(yùn)行時(shí)執(zhí)行檢查贴铜，如果發(fā)現(xiàn)試圖對(duì)集合進(jìn)行修改粪摘， 就拋出一個(gè)異常瀑晒，同時(shí)這個(gè)集合將保持未修改的狀態(tài)。
Collections.unmodifiableCollection(parts);
Collections.unmodifiableList(linkedList);
Collections.unmodifiableSet(parts);
Collections.unmodifiableSortedSet(parts);
Collections.unmodifiableNavigableSet(sortByNumber);
Collections.unmodifiableMap(hashMap);
Collections.unmodifiableSortedMap(hashMap);
Collections.unmodifiableNavigableMap(hashMap);
視圖只是包裝了接口而不是實(shí)際的集合對(duì)象徘意， 所以只能訪問接口中定義的方法苔悦。不可修改視圖并不是集合本身不可修改。仍然可以通過集合的原始引用（在這里是 hashMap / parts / linkedList)對(duì)集合進(jìn)行修改椎咧。
視圖 unmodifiableCollection 返回的集合玖详，它的 equals 方法不調(diào)用底層集合的 equals 方法，繼承的是Object 類的 equals 方法勤讽，檢測(cè)兩個(gè)對(duì)象是否是同一個(gè)對(duì)象蟋座。以同樣的方式處理 hashCode 方法。
視圖 unmodifiableSet 類和 unmodifiableList 類卻使用底層集合的 equals 方法和hashCode 方法地技。
同步視圖
視圖的方法同步蜈七。如果一個(gè)線程試圖將元素添加到散列表中，同時(shí)另一個(gè)線程正在對(duì)散列表進(jìn)行再散列莫矗，其結(jié)果將是災(zāi)難性的飒硅。
類庫(kù)的設(shè)計(jì)者使用視圖機(jī)制來確保常規(guī)集合的線程安全， 而不是實(shí)現(xiàn)線程安全的集合類作谚。
Map<String, Item> map = Collections.synchronizedMap(new HashMap<String,Item>());
便可以多線程訪問map對(duì)象三娩，get 和 put都是同步操作
受查視圖
用來對(duì)泛型類型發(fā)生問題時(shí)提供調(diào)試。插入一個(gè)錯(cuò)誤類型的元素妹懒，視圖的方法拋出一ClassCastException雀监。
Collections.checkedList(strings， String.class);
