目錄介紹
- 1.什么是集合
- 1.1 概念
- 1.2 和數(shù)組區(qū)別
- 1.3 java集合框架圖
- 2.Iterator、Iterable和ListIterator
- 2.1 簡介
- 2.2 Iterable接口
- 2.3 Iterator接口
- 2.4 ListIterator接口
- 3.Iterable和ListIterator具體實(shí)現(xiàn)(以ArrayList為例)
- 3.1 Iterable具體實(shí)現(xiàn)----Itr
- 3.2 ListIterator具體實(shí)現(xiàn)----ListItr
- 4.fail-fast機(jī)制
- 4.1 簡介
- 4.2 如何邊遍歷邊操作集合
1.什么是集合
1.1 概念
- java集合框架的用途是“保存對象”首妖，并將其劃分為兩個不同的概念：
- （1）Collection破衔。 一個獨(dú)立的元素序列冠王，這些元素都服從一條或多條規(guī)則澄暮。List必須按照插入的順序保存元素月帝，而Set不能有重復(fù)的元素搅荞。Queue按照排隊(duì)的規(guī)則來確定對象的產(chǎn)生順序（通常與他們被插入的順序相同）
- （2）Map。一組成對的“鍵值對”對象框咙，允許你使用鍵來查找值咕痛。
1.2 集合和數(shù)組的區(qū)別
- （1）數(shù)組長度固定，集合長度不固定
- （2）數(shù)組可以儲存基本數(shù)據(jù)類型和引用數(shù)據(jù)類型喇嘱，集合只能存儲引用數(shù)據(jù)類型
1.3 java集合框架圖
下圖是java集合框架的總圖：
2.Iterator茉贡、Iterable和ListIterator
2.1 簡介
Collection是java序列集合的根接口，繼承Iterable接口者铜；Iterable接口提供foreach能力腔丧，并且要求實(shí)現(xiàn)者返回一個Iterator，從本質(zhì)上來說Iterator是java序列容器之間的共性作烟，AbstractCollection等抽象類都是通過Iterator來實(shí)現(xiàn)collection接口的方法愉粤，由于java的單繼承性，我們的類在已經(jīng)繼承其他類的基礎(chǔ)上拿撩，不能再繼承AbstractCollection衣厘；而繼承Collection代價又略微偏高，可以通過實(shí)現(xiàn)Iterable接口來實(shí)現(xiàn)一個Collection压恒。
2.2 Iterable接口
Iterable接口是Collection接口的父接口影暴，他要求實(shí)現(xiàn)類返回一個迭代器，并且提供foreach遍歷的能力探赫。
public interface Iterable<T> {
// 返回一個在一組 T 類型的元素上進(jìn)行迭代的迭代器型宙。
Iterator<T> iterator();
// foreach遍歷
default void forEach(Consumer<? super T> action) {}
// 返回一個可分割的迭代器
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
2.3 Iterator接口
Iterator接口的定義也十分簡單，提供迭代器往后面元素迭代的能力
public interface Iterator<E> {
// 是否還有元素可以迭代
boolean hasNext();
// 返回迭代的下一個元素
E next();
// 移除迭代器返回的最后一個元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 對剩下的元素執(zhí)行給定操作
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
2.4 ListIterator接口
ListIterator是List集合特有的迭代器
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
// 判斷游標(biāo)前面是否有元素
boolean hasPrevious();
// 返回游標(biāo)前面的元素伦吠，同時游標(biāo)前移一位妆兑。
E previous();
// 返回游標(biāo)后邊元素的索引位置，初始為0
int nextIndex();
// 返回游標(biāo)前面元素的位置毛仪，初始時為-1
int previousIndex();
// 刪除迭代器最后一次操作的元素
void remove();
// 更新迭代器最后一次操作的元素為 E
void set(E e);
// 在游標(biāo)前面插入一個元素
void add(E e);
}
3.Iterable和ListIterator具體實(shí)現(xiàn)(以ArrayList為例)
3.1 Iterable具體實(shí)現(xiàn)----Itr
private class Itr implements Iterator<E> {
// 游標(biāo)位置
int cursor;
// 上次迭代的位置
int lastRet = -1;
// 用來判斷是否fail-fast的變量
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public E next() {
// fail-fast校驗(yàn)
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 游標(biāo)+1
cursor = i + 1;
// 更新lastRet并且返回對應(yīng)元素
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 調(diào)用外部類的remove方法移除元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 更新expectedModCount
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// fail-fast校驗(yàn)
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
3.2 ListIterator具體實(shí)現(xiàn)----ListItr
ListItr的實(shí)現(xiàn)也并不復(fù)雜箭跳，主要是對游標(biāo)進(jìn)行操作，這里關(guān)注一下set()和add()方法的實(shí)現(xiàn)潭千，可以看到方法內(nèi)部也對expectedModCount進(jìn)行了更新谱姓，所以他們也是可以幫助我們完成遍歷時對容器的操作的.
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
4.fail-fast機(jī)制
4.1 簡介
我們在使用Iterator對容器進(jìn)行迭代時如果修改容器，可能會導(dǎo)致ConcurrentModificationException異常刨晴。這是因?yàn)樵谖覀兊娜萜黝愔芯S護(hù)了一個int型的成員變量modCount屉来，每次對容器進(jìn)行操作時路翻，都會使modCount自增，而在Iterator接口的實(shí)現(xiàn)類中茄靠，有一個變量expectedModCount茂契，在遍歷開始時初始化賦值為modCount。每次遍歷時慨绳，都會去比較expectedModCount和modCount是否相等掉冶，如果不等，就會拋出異常脐雪。這就是java的fail-fast機(jī)制厌小，該機(jī)制主要是用于實(shí)現(xiàn)集合的快速失敗機(jī)制，在Java的集合中战秋，較大一部分集合是存在快速失敗機(jī)制的璧亚。所以要保證在遍歷過程中不出錯誤，我們就應(yīng)該保證在遍歷過程中不會對集合產(chǎn)生結(jié)構(gòu)上的修改脂信，出現(xiàn)了異常錯誤癣蟋，我們就應(yīng)該認(rèn)真檢查程序是否出錯而不是catch后不做處理。
// ArrayList中移除元素時modCount自增
public E remove(int index) {
rangeCheck(index);
// modCount自增
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;
}
// ArrayList中Itr校驗(yàn)modCount
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
4.2 如何邊遍歷邊操作集合
這里推薦使用迭代器iterator提供的方法進(jìn)行操作容器狰闪，當(dāng)然疯搅，也有其他方式能夠解決這個問題，比如說在遍歷時刪除元素可以采用倒序遍歷的方式埋泵，但是都不夠通用秉撇。
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
if (next.equals("dd")) {
iterator.remove();
}
}
之所以我們能夠這樣操作的原因是因?yàn)樵诘鞣椒▋?nèi)部，對expectedModCount進(jìn)行了重新賦值秋泄，使得下一次遍歷的時候琐馆，expectedModCount是等于modCount的.
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// expectedModCount重新賦值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
