有時(shí)候需要存儲(chǔ)一組數(shù)據(jù)押桃，之前使用數(shù)組伊脓，但是數(shù)組具有固定的容量，但是在寫程序時(shí)并不知道需要多少對(duì)象凤优，在java.util包下提供了一套完整的集合類，包含List蜈彼、Set筑辨、Queue、Map幸逆。java集合類都可以自動(dòng)的調(diào)整自己的大小棍辕。
再創(chuàng)建集合時(shí)暮现，經(jīng)常使用泛型，可以在編譯期防止將錯(cuò)誤的類型放入到集合中楚昭。
集合概念
集合分為兩個(gè)基本接口
集合(Collection)：一個(gè)獨(dú)立元素的序列栖袋，List必須已插入順序保存元素，Set不能包含重復(fù)元素抚太，Queue按照排隊(duì)規(guī)則來(lái)確定對(duì)象產(chǎn)生的順序（一般是插入順序）
-
映射(Map)：一組成對(duì)的"鍵值對(duì)"對(duì)象塘幅，允許使用鍵來(lái)查找值。map允許我們使用一個(gè)對(duì)象來(lái)查找另一個(gè)對(duì)象
Arrays.asList()的輸出是一個(gè)List尿贫，但是底層實(shí)現(xiàn)是數(shù)組电媳，沒(méi)法調(diào)整大小。
List<String> list = Arrays.asList("123","234"); list.add("345");//java.lang.UnsupportedOperationException
List
存儲(chǔ)有序庆亡，可以重復(fù)的元素匾乓，相當(dāng)于動(dòng)態(tài)數(shù)組
集合中元素所在類要重寫equals方法
- ArrayList
- LinkedList
- Vector
兩種類型的list
ArrayList：擅長(zhǎng)隨機(jī)訪問(wèn)元素，但在List中間插入和刪除元素時(shí)速度較慢
LinkedList：擅長(zhǎng)在List中間進(jìn)行插入和刪除操作身冀，提供了優(yōu)化的順序訪問(wèn)钝尸，對(duì)于隨機(jī)訪問(wèn)相對(duì)較慢
List特性
- 允許插入重復(fù)元素
- 允許插入多個(gè)null元素
- List提供了ListIterator迭代器，可以提供雙向訪問(wèn)
ArrayList和Vector的異同點(diǎn)
相同點(diǎn)
兩者都是基于索引的搂根，內(nèi)部使用數(shù)組
兩者維護(hù)插入順序珍促，可以根據(jù)插入順序來(lái)獲取元素
ArrayList和Vector的迭代器實(shí)現(xiàn)都是fail-fast的
ArrayList和Vector兩者都允許null值，也可以使用索引值對(duì)元素進(jìn)行隨機(jī)訪問(wèn)
不同點(diǎn)
- Vector是同步的剩愧，ArrayList不是猪叙，但是已過(guò)時(shí)，使用CopyOnWriteArrayList
- ArrayList比Vector快
LinkedList鏈表
LinkedList添加了一些方法仁卷，使其可以被用作棧穴翩，隊(duì)列和雙向隊(duì)列，方法差異
getFirst()和element()是相同的锦积，都是返回列表的頭部芒帕，而并不刪除它，如果list為空丰介，則拋出NoSuchElementException異常背蟆。peek()方法在列表為空是返回null
removeFirst()和remove()方法相同，刪除并返回列表頭部元素哮幢，在列表為空時(shí)返回NoSuchElementException異常带膀，poll()在列表為空時(shí)返回null
addFirst()在列表頭部插入一個(gè)元素
offer()和add()和addLast()相同，在列表尾部添加一個(gè)元素
removeLast()刪除并返回列表的最后一個(gè)元素
ArrayList和LinkedList的區(qū)別
- ArrayList是由數(shù)組支持的基于索引的數(shù)據(jù)結(jié)構(gòu)橙垢，支持對(duì)元素的隨機(jī)訪問(wèn)垛叨，復(fù)雜度為O(1)，但是LinkedList是基于鏈表的柜某，存儲(chǔ)一系列的節(jié)點(diǎn)數(shù)據(jù)嗽元，每個(gè)節(jié)點(diǎn)都與前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)相連敛纲。雖然存在使用索引獲取元素的方法，但是內(nèi)部實(shí)現(xiàn)是從起始點(diǎn)開(kāi)始遍歷的还棱，時(shí)間復(fù)雜度是O(n)
- 與ArrayList相比载慈，在LinkedList中插入、添加和刪除一個(gè)元素會(huì)更快
- LinkedList比ArrayList消耗更多內(nèi)存珍手，因?yàn)樾枰鎯?chǔ)前后節(jié)點(diǎn)的引用
迭代器Iterators
Iterator
Iterator接口提供了遍歷任何Collection的接口办铡，取代了java集合框架中的Enumeration，迭代器允許調(diào)用者在迭代過(guò)程中移除數(shù)據(jù)
iterator只能單向移動(dòng)
使用iterator()方法使集合返回一個(gè)Iterator琳要。Iterator將準(zhǔn)備好返回序列中的第一個(gè)元素寡具。
使用next()方法獲得序列中的下一個(gè)元素。
使用hasNext()方法檢查序列中是否還有元素稚补。
使用remove()方法將迭代器最近返回的那個(gè)元素刪除童叠。
Enumeration和iterator的區(qū)別
- Enumeration的速度是Iterator的兩倍，使用內(nèi)存也少课幕，但是iterator更加安全厦坛，使得一個(gè)集合在遍歷時(shí)，會(huì)阻止其他線程去修改集合乍惊，Iterator允許移除元素
- Iterator支持fail-fast機(jī)制杜秸，而Enumeration不支持，Iterator遍歷時(shí)润绎，當(dāng)其他線程修改集合內(nèi)容時(shí)撬碟，迭代器會(huì)立馬感知到，引起快速失敗莉撇，拋出ConcurrentModificationException異常
- Enumeration本身不支持同步呢蛤，只是在Vector和hashtable實(shí)現(xiàn)Enumeration時(shí)，添加了同步
ListIterator
- ListIterator是Iterator的子類型棍郎，只能由各種List類生成其障，
- Iterator只能向前移動(dòng)，ListIterator可以雙向移動(dòng)涂佃，可以生成迭代器在列表中指向位置的后一個(gè)和前一個(gè)元素的索引静秆。
堆棧stack
堆棧是后進(jìn)先出(LIFO)，最后壓入(push)棧的元素巡李，第一個(gè)被彈出(pop)棧。
java1.0中有一個(gè)stack類扶认，但是設(shè)計(jì)的不好侨拦，Java6添加了ArrayDeque，其中包含了直接實(shí)現(xiàn)堆棧功能的方法
- push()添加元素到棧底
- peek()和pop()返回對(duì)象辐宾，peek()返回棧頂元素狱从，但不從棧頂刪除膨蛮，而pop()刪除并返回棧頂元素
Set
Set不保存重復(fù)的元素。查找是Set最重要的操作季研，選擇HashSet實(shí)現(xiàn)敞葛，針對(duì)快速查找進(jìn)行了優(yōu)化。
存儲(chǔ)無(wú)序与涡，不可重復(fù)
添加Set集合中的元素所在類要重寫equals和hashCode方法
無(wú)序性：指的是元素在底層存儲(chǔ)的位置是無(wú)序的
HashSet沒(méi)有順序惹谐，使用散列函數(shù)，HashSet維護(hù)順序與TreeSet或LinkedHashSet不同驼卖，因?yàn)樗鼈儗?shí)現(xiàn)具有不同的元素存儲(chǔ)方式
LinkedHashSet 也使用了散列氨肌，使用了鏈表來(lái)維護(hù)元素的插入順序，結(jié)果將按元素的插入順序顯示酌畜。元素必須定義hashCode()和equals()方法怎囚，遍歷元素時(shí)，會(huì)按照添加的進(jìn)去的順序
-
TreeSet將元素存儲(chǔ)在紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)桥胞，可以從Set中獲取有序序列恳守，其中元素必須實(shí)現(xiàn)Comparable接口
要求添加進(jìn)TreeSet的必須是同一個(gè)類的
兩種排序方式
1）自然排序：添加的類要實(shí)現(xiàn)Comparable接口，重寫compareTo方法
2）定制排序: 使用TreeSet(Comparator<? super E> comparator) 構(gòu)造器 重寫compare(T o1, T o2);方法
Map
鍵值
key不可重復(fù)贩虾，一個(gè)key-value組成一個(gè)entry
map的分類
HashMap專為快速訪問(wèn)而設(shè)計(jì)催烘，TreeMap保持鍵始終處于排序狀態(tài)，沒(méi)有HashMap快整胃。LinkedHashMap按插入順序保存其元素颗圣，但使用散列提供快速訪問(wèn)的能力。
- HashMap 基于哈希表的實(shí)現(xiàn)屁使。為插入和定位鍵值對(duì)提供了常數(shù)時(shí)間性能在岂。可以通過(guò)構(gòu)造方法調(diào)整性能蛮寂，這些構(gòu)造方法允許設(shè)置哈希表的容量和裝填因子蔽午。可以添加key為null酬蹋，value為null
- LinkedHashMap 與HashMap類似及老，但是當(dāng)遍歷時(shí)，可以按照插入順序或最近最少使用(LRU)順序獲取鍵值對(duì)范抓。只比HashMap略慢骄恶，一個(gè)例外是在迭代時(shí)，由于其使用鏈表維護(hù)內(nèi)部順序匕垫，所以會(huì)更快些僧鲁，按照添加進(jìn)Map的順序遍歷
- TreeMap 基于紅黑樹(shù)實(shí)現(xiàn)，當(dāng)查看鍵或鍵值對(duì)時(shí)，按排序順序(由Comparable或Comparator確定)寞秃。TreeMap的側(cè)重點(diǎn)在于按排序順序獲得結(jié)果斟叼。TreeMap是唯一使用subMap()方法的Map，返回紅黑樹(shù)的一部分春寿，按照key所在類的指定屬性進(jìn)行排序朗涩，要求key是同一個(gè)類的對(duì)象（同TreeSet）
- WeakHashMap 一個(gè)具有弱鍵的Map，為了解決某些類型的問(wèn)題绑改，它允許釋放Map所引用的對(duì)象谢床。如果Map外沒(méi)有對(duì)特定鍵的引用，則可以對(duì)該鍵進(jìn)行垃圾回收
- ConcurrentHashMap 不使用同步鎖定的線程安全Map
- IdentityHashMap 使用==來(lái)比較鍵绢淀，僅用于解決特殊問(wèn)題
- HashTable 不可添加key為null萤悴，value為null的 子類Properties 處理屬性文件
HashMap工作情況
HashMap在Map.Entry靜態(tài)內(nèi)部類實(shí)現(xiàn)存儲(chǔ)鍵值對(duì)，HashMap使用哈希算法皆的，在put和get方法中覆履，使用hashCode和equals方法，使用put方法時(shí)费薄，使用key的hashcode和哈希算法來(lái)找出存儲(chǔ)鍵值對(duì)的索引硝全，Entry存儲(chǔ)在LinkedList中，如果存在entry楞抡，使用equals檢查傳遞的key是否存在伟众，如果存在，會(huì)覆蓋掉value召廷，如果不存在凳厢，會(huì)創(chuàng)建一個(gè)新的entry然后保存。get的時(shí)候也是先通過(guò)hashcode找到數(shù)組中的索引竞慢，然后使用equals找到正確的Entry先紫，在進(jìn)行取值
HashMap默認(rèn)初始容量是32，負(fù)載因子是0.75筹煮，閾值是容量乘以負(fù)載因子遮精，當(dāng)map的大小比閾值大時(shí)，HashMap會(huì)對(duì)map的內(nèi)容進(jìn)行重新哈希败潦。
HashMap和HashTable的區(qū)別
- HashMap允許key和value為null本冲，HashTable不允許
- HashTable是同步的，HashMap不是
- HashMap可以轉(zhuǎn)為L(zhǎng)inkedHashMap劫扒，使得遍歷有序檬洞，HashTable的順序無(wú)法預(yù)知
- HashMap提供對(duì)key的set進(jìn)行遍歷，所以是fail-fast的沟饥，HashTable提供對(duì)key的Enumeration進(jìn)行遍歷疮胖，不支持fail-fast
- HashTable應(yīng)該被CocurrentHashMap替代
隊(duì)列
隊(duì)列操作
隊(duì)列是一個(gè)先進(jìn)先出(FIFO)集合环戈，LinkedList實(shí)現(xiàn)了Queue接口，并且提供了一些方法支持隊(duì)列行為
offer()在隊(duì)列尾部插入一個(gè)元素
peek()和element()返回隊(duì)列頭而不刪除它澎灸，如果隊(duì)列為空，element()拋出NoSuchElementException遮晚，而peek()返回null
poll()和remove()都刪除并返回隊(duì)頭元素性昭，如果隊(duì)列為空，poll()返回null县遣，remove()拋出NoSuchElementException
PriorityQueue優(yōu)先級(jí)隊(duì)列
優(yōu)先級(jí)隊(duì)列聲明下一個(gè)彈出的元素是最需要的元素糜颠。
BlockingQueue隊(duì)列
是concurrent包下的類，在進(jìn)行檢索或移除一個(gè)元素的時(shí)候萧求，會(huì)等待隊(duì)列變成非空其兴；當(dāng)添加一個(gè)元素的時(shí)候，會(huì)等待隊(duì)列中的可用空間夸政。主要用于實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者模式
Collections工具類
unmodifiableCollection方法
Collections.unmodifiableCollection(list)元旬；Collections.unmodifiableList(list)；使用該方法會(huì)創(chuàng)建一個(gè)只讀集合守问，所有改變集合的操作都會(huì)拋出UnsupportedOperationException
public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
return new UnmodifiableCollection<>(c);
}
synchronizedCollection方法
Collections.synchronizedCollection(list)方法可以創(chuàng)建一個(gè)線程安全的集合
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
return new SynchronizedCollection<>(c);
}
問(wèn)題
1匀归、遍歷時(shí)移除List中的元素
使用forEach和Iterator
在使用forEach遍歷時(shí)，實(shí)際上是使用的Iterator耗帕，使用的核心方法是hasNext()和next()穆端，但是使用的是list.remove，來(lái)看個(gè)例子
//源碼
public class TestList {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("J");
list.add("A");
list.add("V");
list.add("A");
for (String s: list) {
list.remove(s);
}
}
}
//編譯之后
public class TestList {
public TestList() {
}
public static void main(String[] args) {
List<String> list = new ArrayList();
list.add("J");
list.add("A");
list.add("V");
list.add("A");
Iterator var2 = list.iterator();
while(var2.hasNext()) {
String s = (String)var2.next();
list.remove(s);
}
}
}
之前說(shuō)過(guò)仿便，Iterator在遍歷時(shí)体啰，不允許其他線程對(duì)該集合進(jìn)行操作，看一下ArrayList的iterator是怎么實(shí)現(xiàn)的
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
在每次獲取下一個(gè)元素時(shí)嗽仪，都會(huì)比較modCount 和 expectedModCount
然后在調(diào)用的list的remove方法會(huì)導(dǎo)致modCount增加（modCount表示被修改次數(shù)）
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
此時(shí)iterator的next方法中兩個(gè)變量就不一致了荒勇，就會(huì)拋出ConcurrentModificationException異常
再看一下如果使用iterator的remove方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
iterator在remove之后會(huì)將modCount的值賦給expectedModCount，就不會(huì)出現(xiàn)兩個(gè)變量不等的情況了
不使用forEach遍歷
使用普通for循環(huán)钦幔，有兩種方式枕屉，第一種是使用正序遍歷，但是進(jìn)行remove操作之后要把遍歷的索引進(jìn)行修正減一鲤氢，否則在移除下一個(gè)的時(shí)候就會(huì)出錯(cuò)搀擂，第二種就是使用倒序遍歷
// 正序遍歷
for (int i = 0; i < list.size(); i++) {
String s = list.remove(i);
i = i - 1;
System.out.println(s);
}
//倒序遍歷
for (int i = list.size() - 1; i >= 0; i--) {
String s = list.remove(i);
System.out.println(s);
}
2、fail-fast和fail-safe
java.util包中集合類被設(shè)計(jì)為fail-fast的卷玉，而java.util.concurrent中集合為fail-safe的哨颂。fail-fast迭代器拋出ConcurrentModificationException，而fail-safe迭代器從不拋出ConcurrentModificationException
3相种、Arrays.asList
這個(gè)方法返回的是一個(gè)ArrayList威恼，不過(guò)這個(gè)ArrayList是Arrays類的內(nèi)部類，在調(diào)用add方法的時(shí)候會(huì)直接報(bào)錯(cuò)
UnsupportedOperationException這是運(yùn)行時(shí)異常
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
由于本身的博客百度沒(méi)有收錄，博客地址http://zhhll.icu
