您好,登錄后才能下訂單哦!
本篇內容主要講解“Java的Iterator,fail-fast機制與比較器怎么使用”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“Java的Iterator,fail-fast機制與比較器怎么使用”吧!
迭代對于我們搞Java的來說絕對不陌生。我們常常使用JDK提供的迭代接口進行Java集合的迭代。
Iterator iterator = list.iterator(); while(iterator.hasNext()){ String string = iterator.next(); //do something }
迭代其實我們可以簡單地理解為遍歷,是一個標準化遍歷各類容器里面的所有對象的方法類,它是一個很典型的設計模式。Iterator模式是用于遍歷集合類的標準訪問方法。
它可以把訪問邏輯從不同類型的集合類中抽象出來,從而避免向客戶端暴露集合的內部結構。 在沒有迭代器時我們都是這么進行處理的。如下:
對于數組我們是使用下標來進行處理的:
int[] arrays = new int[10]; for(int i = 0 ; i < arrays.length ; i++){ int a = arrays[i]; //do something }
對于ArrayList是這么處理的:
List<String> list = new ArrayList<String>(); for(int i = 0 ; i < list.size() ; i++){ String string = list.get(i); //do something }
對于這兩種方式,我們總是都事先知道集合的內部結構,訪問代碼和集合本身是緊密耦合的,無法將訪問邏輯從集合類和客戶端代碼中分離出來。同時每一種集合對應一種遍歷方法,客戶端代碼無法復用。
在實際應用中如何需要將上面將兩個集合進行整合是相當麻煩的。所以為了解決以上問題,Iterator模式騰空出世,它總是用同一種邏輯來遍歷集合。
使得客戶端自身不需要來維護集合的內部結構,所有的內部狀態都由Iterator來維護。客戶端從不直接和集合類打交道,它總是控制Iterator,向它發送"向前","向后","取當前元素"的命令,就可以間接遍歷整個集合。
上面只是對Iterator模式進行簡單的說明,下面我們看看Java中Iterator接口,看他是如何來進行實現的。
在Java中Iterator為一個接口,它只提供了迭代了基本規則,在JDK中他是這樣定義的:對 collection 進行迭代的迭代器。迭代器取代了 Java Collections Framework 中的 Enumeration。迭代器與枚舉有兩點不同:
1、迭代器允許調用者利用定義良好的語義在迭代期間從迭代器所指向的 collection 移除元素。 2、方法名稱得到了改進。
其接口定義如下:
public interface Iterator {   boolean hasNext();   Object next();   void remove(); }
其中:
Object next():返回迭代器剛越過的元素的引用,返回值是Object,需要強制轉換成自己需要的類型 boolean hasNext():判斷容器內是否還有可供訪問的元素 void remove():刪除迭代器剛越過的元素
對于我們而言,我們只一般只需使用next()、hasNext()兩個方法即可完成迭代。如下:
for(Iterator it = c.iterator(); it.hasNext(); ) {   Object o = it.next();    //do something }
==前面闡述了Iterator有一個很大的優點,就是我們不必知道集合的內部結果,集合的內部結構、狀態由Iterator來維持,通過統一的方法hasNext()、next()來判斷、獲取下一個元素,至于具體的內部實現我們就不用關心了。==
但是作為一個合格的程序員我們非常有必要來弄清楚Iterator的實現。下面就ArrayList的源碼進行分析分析。
下面就ArrayList的Iterator實現來分析,其實如果我們理解了ArrayList、Hashset、TreeSet的數據結構,內部實現,對于他們是如何實現Iterator也會胸有成竹的。因為ArrayList的內部實現采用數組,所以我們只需要記錄相應位置的索引即可,其方法的實現比較簡單。
ArrayList的Iterator實現
在ArrayList內部首先是定義一個內部類Itr,該內部類實現Iterator接口,如下:
private class Itr implements Iterator<E> { //do something } 而ArrayList的iterator()方法實現: public Iterator<E> iterator() { return new Itr(); }
所以通過使用ArrayList.iterator()方法返回的是Itr()內部類,所以現在我們需要關心的就是Itr()內部類的實現:
在Itr內部定義了三個int型的變量:cursor、lastRet、expectedModCount。其中cursor表示下一個元素的索引位置,lastRet表示上一個元素的索引位置
int cursor; int lastRet = -1; int expectedModCount = modCount;
從cursor、lastRet定義可以看出,lastRet一直比cursor少一所以hasNext()實現方法異常簡單,只需要判斷cursor和lastRet是否相等即可。
public boolean hasNext() { return cursor != size; }
對于next()實現其實也是比較簡單的,只要返回cursor索引位置處的元素即可,然后修改cursor、lastRet即可。
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; //cursor + 1 return (E) elementData[lastRet = i]; //lastRet + 1 且返回cursor處元素 }
checkForComodification()主要用來判斷集合的修改次數是否合法,即用來判斷遍歷過程中集合是否被修改過。
。modCount用于記錄ArrayList集合的修改次數,初始化為0,,每當集合被修改一次(結構上面的修改,內部update不算),如add、remove等方法,modCount + 1,所以如果modCount不變,則表示集合內容沒有被修改。
該機制主要是用于實現ArrayList集合的快速失敗機制,在Java的集合中,較大一部分集合是存在快速失敗機制的,這里就不多說,后面會講到。
所以要保證在遍歷過程中不出錯誤,我們就應該保證在遍歷過程中不會對集合產生結構上的修改(當然remove方法除外),出現了異常錯誤,我們就應該認真檢查程序是否出錯而不是catch后不做處理。
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } 對于remove()方法的是實現,它是調用ArrayList本身的remove()方法刪除lastRet位置元素,然后修改modCount即可。 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(); } }
這里就對ArrayList的Iterator實現講解到這里,對于Hashset、TreeSet等集合的Iterator實現,各位如果感興趣可以繼續研究,個人認為在研究這些集合的源碼之前,有必要對該集合的數據結構有清晰的認識,這樣會達到事半功倍的效果!!!!
這部分參考http://cmsblogs.com/?p=1220
在JDK的Collection中我們時常會看到類似于這樣的話:
例如,ArrayList:
注意,迭代器的快速失敗行為無法得到保證,因為一般來說,不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗迭代器會盡最大努力拋出ConcurrentModificationException。 因此,為提高這類迭代器的正確性而編寫一個依賴于此異常的程序是錯誤的做法:迭代器的快速失敗行為應該僅用于檢測 bug。
HashMap中:
注意,迭代器的快速失敗行為不能得到保證,一般來說,存在非同步的并發修改時,不可能作出任何堅決的保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此,編寫依賴于此異常的程序的做法是錯誤的,正確做法是:迭代器的快速失敗行為應該僅用于檢測程序錯誤。
在這兩段話中反復地提到”快速失敗”。那么何為”快速失敗”機制呢?
“快速失敗”也就是fail-fast,它是Java集合的一種錯誤檢測機制。當多個線程對集合進行結構上的改變的操作時,有可能會產生fail-fast機制。
記住是有可能,而不是一定。例如:假設存在兩個線程(線程1、線程2),線程1通過Iterator在遍歷集合A中的元素,在某個時候線程2修改了集合A的結構(是結構上面的修改,而不是簡單的修改集合元素的內容),那么這個時候程序就會拋出 ConcurrentModificationException異常,從而產生fail-fast機制。
public class FailFastTest { private static List<Integer> list = new ArrayList<>(); /** * @desc:線程one迭代list * @Project:test * @file:FailFastTest.java * @Authro:chenssy * @data:2014年7月26日 */ private static class threadOne extends Thread{ public void run() { Iterator<Integer> iterator = list.iterator(); while(iterator.hasNext()){ int i = iterator.next(); System.out.println("ThreadOne 遍歷:" + i); try { Thread.sleep(10); } catch (InterruptedException e) { e.printStackTrace(); } } } } /** * @desc:當i == 3時,修改list * @Project:test * @file:FailFastTest.java * @Authro:chenssy * @data:2014年7月26日 */ private static class threadTwo extends Thread{ public void run(){ int i = 0 ; while(i < 6){ System.out.println("ThreadTwo run:" + i); if(i == 3){ list.remove(i); } i++; } } } public static void main(String[] args) { for(int i = 0 ; i < 10;i++){ list.add(i); } new threadOne().start(); new threadTwo().start(); } }
運行結果:
ThreadOne 遍歷:0 ThreadTwo run:0 ThreadTwo run:1 ThreadTwo run:2 ThreadTwo run:3 ThreadTwo run:4 ThreadTwo run:5 Exception in thread "Thread-0" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(Unknown Source) at java.util.ArrayList$Itr.next(Unknown Source) at test.ArrayListTest$threadOne.run(ArrayListTest.java:23)
通過上面的示例和講解,我初步知道fail-fast產生的原因就在于程序在對 collection 進行迭代時,某個線程對該 collection 在結構上對其做了修改,這時迭代器就會拋出 ConcurrentModificationException 異常信息,從而產生 fail-fast。
要了解fail-fast機制,我們首先要對ConcurrentModificationException 異常有所了解。當方法檢測到對象的并發修改,但不允許這種修改時就拋出該異常。同時需要注意的是,該異常不會始終指出對象已經由不同線程并發修改,如果單線程違反了規則,同樣也有可能會拋出改異常。
誠然,迭代器的快速失敗行為無法得到保證,它不能保證一定會出現該錯誤,但是快速失敗操作會盡最大努力拋出ConcurrentModificationException異常,所以因此,為提高此類操作的正確性而編寫一個依賴于此異常的程序是錯誤的做法,正確做法是:ConcurrentModificationException 應該僅用于檢測 bug。下面我將以ArrayList為例進一步分析fail-fast產生的原因。
從前面我們知道fail-fast是在操作迭代器時產生的。現在我們來看看ArrayList中迭代器的源代碼:
private class Itr implements Iterator<E> { int cursor; int lastRet = -1; int expectedModCount = ArrayList.this.modCount; public boolean hasNext() { return (this.cursor != ArrayList.this.size); } public E next() { checkForComodification(); /** 省略此處代碼 */ } public void remove() { if (this.lastRet < 0) throw new IllegalStateException(); checkForComodification(); /** 省略此處代碼 */ } final void checkForComodification() { if (ArrayList.this.modCount == this.expectedModCount) return; throw new ConcurrentModificationException(); } }
從上面的源代碼我們可以看出,迭代器在調用next()、remove()方法時都是調用checkForComodification()方法,該方法主要就是檢測modCount == expectedModCount ? 若不等則拋出ConcurrentModificationException 異常,從而產生fail-fast機制。所以要弄清楚為什么會產生fail-fast機制我們就必須要用弄明白為什么modCount != expectedModCount ,他們的值在什么時候發生改變的。
expectedModCount 是在Itr中定義的:int expectedModCount = ArrayList.this.modCount;所以他的值是不可能會修改的,所以會變的就是modCount。modCount是在 AbstractList 中定義的,為全局變量:
protected transient int modCount = 0; 那么他什么時候因為什么原因而發生改變呢?請看ArrayList的源碼:
public boolean add(E paramE) { ensureCapacityInternal(this.size + 1); /** 省略此處代碼 */ } private void ensureCapacityInternal(int paramInt) { if (this.elementData == EMPTY_ELEMENTDATA) paramInt = Math.max(10, paramInt); ensureExplicitCapacity(paramInt); } private void ensureExplicitCapacity(int paramInt) { this.modCount += 1; //修改modCount /** 省略此處代碼 */ }
public boolean remove(Object paramObject) { int i; if (paramObject == null) for (i = 0; i < this.size; ++i) { if (this.elementData[i] != null) continue; fastRemove(i); return true; } else for (i = 0; i < this.size; ++i) { if (!(paramObject.equals(this.elementData[i]))) continue; fastRemove(i); return true; } return false; }
private void fastRemove(int paramInt) { this.modCount += 1; //修改modCount /** 省略此處代碼 */ } public void clear() { this.modCount += 1; //修改modCount /** 省略此處代碼 */ }
從上面的源代碼我們可以看出,ArrayList中無論add、remove、clear方法只要是涉及了改變ArrayList元素的個數的方法都會導致modCount的改變。
所以我們這里可以初步判斷由于expectedModCount 得值與modCount的改變不同步,導致兩者之間不等從而產生fail-fast機制。知道產生fail-fast產生的根本原因了,我們可以有如下場景:
有兩個線程(線程A,線程B),其中線程A負責遍歷list、線程B修改list。線程A在遍歷list過程的某個時候(此時expectedModCount = modCount=N),線程啟動,同時線程B增加一個元素,這是modCount的值發生改變(modCount + 1 = N + 1)。
線程A繼續遍歷執行next方法時,通告checkForComodification方法發現expectedModCount = N ,而modCount = N + 1,兩者不等,這時就拋出ConcurrentModificationException 異常,從而產生fail-fast機制。
所以,直到這里我們已經完全了解了fail-fast產生的根本原因了。知道了原因就好找解決辦法了。
三、fail-fast解決辦法
通過前面的實例、源碼分析,我想各位已經基本了解了fail-fast的機制,下面我就產生的原因提出解決方案。這里有兩種解決方案:
方案一:在遍歷過程中所有涉及到改變modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList,這樣就可以解決。但是不推薦,因為增刪造成的同步鎖可能會阻塞遍歷操作。
方案二:使用CopyOnWriteArrayList來替換ArrayList。推薦使用該方案。
CopyOnWriteArrayList為何物?ArrayList 的一個線程安全的變體,其中所有可變操作(add、set 等等)都是通過對底層數組進行一次新的復制來實現的。 該類產生的開銷比較大,但是在兩種情況下,它非常適合使用。
1:在不能或不想進行同步遍歷,但又需要從并發線程中排除沖突時。
2:當遍歷操作的數量大大超過可變操作的數量時。遇到這兩種情況使用CopyOnWriteArrayList來替代ArrayList再適合不過了。那么為什么CopyOnWriterArrayList可以替代ArrayList呢?
第一、CopyOnWriterArrayList的無論是從數據結構、定義都和ArrayList一樣。它和ArrayList一樣,同樣是實現List接口,底層使用數組實現。在方法上也包含add、remove、clear、iterator等方法。
第二、CopyOnWriterArrayList根本就不會產生ConcurrentModificationException異常,也就是它使用迭代器完全不會產生fail-fast機制。請看:
private static class COWIterator implements ListIterator { /** 省略此處代碼 */ public E next() { if (!(hasNext())) throw new NoSuchElementException(); return this.snapshot[(this.cursor++)]; }
/** 省略此處代碼 */ }
CopyOnWriterArrayList的方法根本就沒有像ArrayList中使用checkForComodification方法來判斷expectedModCount 與 modCount 是否相等。它為什么會這么做,憑什么可以這么做呢?我們以add方法為例:
public boolean add(E paramE) { ReentrantLock localReentrantLock = this.lock; localReentrantLock.lock(); try { Object[] arrayOfObject1 = getArray(); int i = arrayOfObject1.length; Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1); arrayOfObject2[i] = paramE; setArray(arrayOfObject2); int j = 1; return j; } finally { localReentrantLock.unlock(); } } final void setArray(Object[] paramArrayOfObject) { this.array = paramArrayOfObject; }
CopyOnWriterArrayList的add方法與ArrayList的add方法有一個最大的不同點就在于,下面三句代碼:
Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1); arrayOfObject2[i] = paramE; setArray(arrayOfObject2);
就是這三句代碼使得CopyOnWriterArrayList不會拋ConcurrentModificationException異常。他們所展現的魅力就在于copy原來的array,再在copy數組上進行add操作,這樣做就完全不會影響COWIterator中的array了。
所以CopyOnWriterArrayList所代表的核心概念就是:任何對array在結構上有所改變的操作(add、remove、clear等),CopyOnWriterArrayList都會copy現有的數據,再在copy的數據上修改,這樣就不會影響COWIterator中的數據了,修改完成之后改變原有數據的引用即可。同時這樣造成的代價就是產生大量的對象,同時數組的copy也是相當有損耗的。
Java 中為我們提供了兩種比較機制:Comparable 和 Comparator,他們之間有什么區別呢?今天來了解一下。
Comparable 在 java.lang包下,是一個接口,內部只有一個方法 compareTo():
public interface Comparable<T> { public int compareTo(T o); }
Comparable 可以讓實現它的類的對象進行比較,具體的比較規則是按照 compareTo 方法中的規則進行。這種順序稱為 自然順序。
compareTo 方法的返回值有三種情況:
e1.compareTo(e2) > 0 即 e1 > e2 e1.compareTo(e2) = 0 即 e1 = e2 e1.compareTo(e2) < 0 即 e1 < e2
注意:
1.由于 null 不是一個類,也不是一個對象,因此在重寫 compareTo 方法時應該注意 e.compareTo(null) 的情況,即使 e.equals(null) 返回 false,compareTo 方法也應該主動拋出一個空指針異常 NullPointerException。
2.Comparable 實現類重寫 compareTo 方法時一般要求 e1.compareTo(e2) == 0 的結果要和 e1.equals(e2) 一致。這樣將來使用 SortedSet 等根據類的自然排序進行排序的集合容器時可以保證保存的數據的順序和想象中一致。 有人可能好奇上面的第二點如果違反了會怎樣呢?
舉個例子,如果你往一個 SortedSet 中先后添加兩個對象 a 和 b,a b 滿足 (!a.equals(b) && a.compareTo(b) == 0),同時也沒有另外指定個 Comparator,那當你添加完 a 再添加 b 時會添加失敗返回 false, SortedSet 的 size 也不會增加,因為在 SortedSet 看來它們是相同的,而 SortedSet 中是不允許重復的。
實際上所有實現了 Comparable 接口的 Java 核心類的結果都和 equlas 方法保持一致。 實現了 Comparable 接口的 List 或則數組可以使用 Collections.sort() 或者 Arrays.sort() 方法進行排序。
實現了 Comparable 接口的對象才能夠直接被用作 SortedMap (SortedSet) 的 key,要不然得在外邊指定 Comparator 排序規則。
因此自己定義的類如果想要使用有序的集合類,需要實現 Comparable 接口,比如:
**
description: 測試用的實體類 書, 實現了 Comparable 接口,自然排序
author: shixinzhang
data: 10/5/2016 */ public class BookBean implements Serializable, Comparable { private String name; private int count;
public BookBean(String name, int count) { this.name = name; this.count = count; }
public String getName() { return name; }
public void setName(String name) { this.name = name; }
public int getCount() { return count; }
public void setCount(int count) { this.count = count; }
/**
}
/**
@Override public String toString() { return "BookBean{" + "name='" + name + ''' + ", count=" + count + '}'; }
/**
當向 TreeSet 中添加 BookBean 時,會調用這個方法進行排序
@param another
@return */ @Override public int compareTo(Object another) { if (another instanceof BookBean){ BookBean anotherBook = (BookBean) another; int result;
//比如這里按照書價排序 result = getCount() - anotherBook.getCount();
//或者按照 String 的比較順序 //result = getName().compareTo(anotherBook.getName());
if (result == 0){ //當書價一致時,再對比書名。 保證所有屬性比較一遍 result = getName().compareTo(anotherBook.getName()); } return result;
} // 一樣就返回 0 return 0; }
重寫 hashCode 的計算方法
根據所有屬性進行 迭代計算,避免重復
計算 hashCode 時 計算因子 31 見得很多,是一個質數,不能再被除
@return */ @Override public int hashCode() { //調用 String 的 hashCode(), 唯一表示一個字符串內容 int result = getName().hashCode(); //乘以 31, 再加上 count result = 31 * result + getCount(); return result; }
重寫 equals
@param o
@return */ @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof BookBean)) return false;
BookBean bean = (BookBean) o;
if (getCount() != bean.getCount()) return false; return getName().equals(bean.getName());
上述代碼還重寫了 equlas(), hashCode() 方法,自定義的類將來可能會進行比較時,建議重寫這些方法。
這里我想表達的是在有些場景下 equals 和 compareTo 結果要保持一致,這時候不重寫 equals,使用 Object.equals 方法得到的結果會有問題,比如說 HashMap.put() 方法,會先調用 key 的 equals 方法進行比較,然后才調用 compareTo。
后面重寫 compareTo 時,要判斷某個相同時對比下一個屬性,把所有屬性都比較一次。
Comparable 接口屬于 Java 集合框架的一部分。
Comparator 定制排序
Comparator 在 java.util 包下,也是一個接口,JDK 1.8 以前只有兩個方法:
public interface Comparator<T> { public int compare(T lhs, T rhs); public boolean equals(Object object); }
JDK 1.8 以后又新增了很多方法:
基本上都是跟 Function 相關的,這里暫不介紹 1.8 新增的。
從上面內容可知使用自然排序需要類實現 Comparable,并且在內部重寫 comparaTo 方法。
而 Comparator 則是在外部制定排序規則,然后作為排序策略參數傳遞給某些類,比如 Collections.sort(), Arrays.sort(), 或者一些內部有序的集合(比如 SortedSet,SortedMap 等)。
Comparator的使用方法 使用方式主要分三步:
創建一個 Comparator 接口的實現類,并賦值給一個對象 在 compare 方法中針對自定義類寫排序規則 將 Comparator 對象作為參數傳遞給 排序類的某個方法 向排序類中添加 compare 方法中使用的自定義類 舉個例子:
// 1.創建一個實現 Comparator 接口的對象 Comparator comparator = new Comparator() { @Override public int compare(Object object1, Object object2) { if (object1 instanceof NewBookBean && object2 instanceof NewBookBean){ NewBookBean newBookBean = (NewBookBean) object1; NewBookBean newBookBean1 = (NewBookBean) object2; //具體比較方法參照 自然排序的 compareTo 方法,這里只舉個栗子 return newBookBean.getCount() - newBookBean1.getCount(); } return 0; } }; //2.將此對象作為形參傳遞給 TreeSet 的構造器中 TreeSet treeSet = new TreeSet(comparator); //3.向 TreeSet 中添加 步驟 1 中 compare 方法中設計的類的對象 treeSet.add(new NewBookBean("A",34)); treeSet.add(new NewBookBean("S",1)); treeSet.add( new NewBookBean("V",46)); treeSet.add( new NewBookBean("Q",26));
其實可以看到,Comparator 的使用是一種策略模式。 排序類中持有一個 Comparator 接口的引用:
Comparator<? super K> comparator;
而我們可以傳入各種自定義排序規則的 Comparator 實現類,對同樣的類制定不同的排序策略。
到此,相信大家對“Java的Iterator,fail-fast機制與比較器怎么使用”有了更深的了解,不妨來實際操作一番吧!這里是億速云網站,更多相關內容可以進入相關頻道進行查詢,關注我們,繼續學習!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。