Shulou(Shulou.com)06/02 Report--

This article mainly explains "the Iterator,fail-fast mechanism of Java and how to use the comparator". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "Java's Iterator,fail-fast mechanism and how to use the comparator"!

Iterator

Iteration is no stranger to us in Java. We often use the iteration interface provided by JDK to iterate over the Java collection.

Iterator iterator = list.iterator (); while (iterator.hasNext ()) {String string = iterator.next (); / / do something}

In fact, iteration can be simply understood as traversal, which is a method class that standardizes traversing all objects in various containers. It is a typical design pattern. The Iterator pattern is a standard access method for traversing collection classes.

It abstracts the access logic from different types of collection classes, thus avoiding exposing the internal structure of the collection to the client. This is what we all do when there is no iterator. As follows:

We use subscripts to deal with arrays:

Int [] arrays = new int [10]; for (int I = 0; I

< arrays.length ; i++){ int a = arrays[i]; //do something } 对于ArrayList是这么处理的: List list = new ArrayList(); for(int i = 0 ; i < list.size() ; i++){ String string = list.get(i); //do something } 对于这两种方式，我们总是都事先知道集合的内部结构，访问代码和集合本身是紧密耦合的，无法将访问逻辑从集合类和客户端代码中分离出来。同时每一种集合对应一种遍历方法，客户端代码无法复用。 在实际应用中如何需要将上面将两个集合进行整合是相当麻烦的。所以为了解决以上问题，Iterator模式腾空出世，它总是用同一种逻辑来遍历集合。 使得客户端自身不需要来维护集合的内部结构，所有的内部状态都由Iterator来维护。客户端从不直接和集合类打交道，它总是控制Iterator，向它发送"向前"，"向后"，"取当前元素"的命令，就可以间接遍历整个集合。 上面只是对Iterator模式进行简单的说明，下面我们看看Java中Iterator接口，看他是如何来进行实现的。 java.util.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的源码进行分析分析。 各个集合的Iterator的实现 下面就ArrayList的Iterator实现来分析，其实如果我们理解了ArrayList、Hashset、TreeSet的数据结构，内部实现，对于他们是如何实现Iterator也会胸有成竹的。因为ArrayList的内部实现采用数组，所以我们只需要记录相应位置的索引即可，其方法的实现比较简单。 ArrayList的Iterator实现 在ArrayList内部首先是定义一个内部类Itr，该内部类实现Iterator接口，如下： private class Itr implements Iterator { //do something}而ArrayList的iterator()方法实现：public Iterator 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) / / if the fetch element is greater than the number of collection elements, throw an exception 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 and returns the element at cursor}

CheckForComodification () is mainly used to determine whether the number of changes to the set is legal, that is, to determine whether the set has been modified during traversal.

. ModCount is used to record the number of changes to the ArrayList collection, initialized to 0, and every time the collection is modified (the structure above is modified, the internal update is not counted), such as add, remove and other methods, modCount + 1, so if the modCount remains unchanged, it means that the content of the collection has not been modified.

This mechanism is mainly used to implement the fast failure mechanism of ArrayList collections. In Java collections, there is a fast failure mechanism in a large part of the collections. I won't say much here, but I'll talk about it later.

So to ensure that there are no errors in the traversal process, we should ensure that there will be no structural changes to the collection during traversal (except for the remove method, of course). If an exception occurs, we should carefully check whether the program is wrong instead of not dealing with it after catch.

Final void checkForComodification () {if (modCount! = expectedModCount) throw new ConcurrentModificationException ();} is the implementation of the remove () method, which calls the remove () method of the ArrayList itself to delete the lastRet location element, and then modifies the 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实现，各位如果感兴趣可以继续研究，个人认为在研究这些集合的源码之前，有必要对该集合的数据结构有清晰的认识，这样会达到事半功倍的效果！！！！ fail-fast机制 这部分参考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机制。 fail-fast示例public class FailFastTest { private static List 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 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 遍历:0ThreadTwo run：0ThreadTwo run：1ThreadTwo run：2ThreadTwo run：3ThreadTwo run：4ThreadTwo run：5Exception 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产生原因 通过上面的示例和讲解，我初步知道fail-fast产生的原因就在于程序在对 collection 进行迭代时，某个线程对该 collection 在结构上对其做了修改，这时迭代器就会抛出 ConcurrentModificationException 异常信息，从而产生 fail-fast。 要了解fail-fast机制，我们首先要对ConcurrentModificationException 异常有所了解。当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。同时需要注意的是，该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出改异常。 诚然，迭代器的快速失败行为无法得到保证，它不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常，所以因此，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是：ConcurrentModificationException 应该仅用于检测 bug。下面我将以ArrayList为例进一步分析fail-fast产生的原因。 从前面我们知道fail-fast是在操作迭代器时产生的。现在我们来看看ArrayList中迭代器的源代码： private class Itr implements Iterator { 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也是相当有损耗的。 Comparable 和 Comparator Java 中为我们提供了两种比较机制：Comparable 和 Comparator，他们之间有什么区别呢？今天来了解一下。 Comparable Comparable 在 java.lang包下，是一个接口，内部只有一个方法 compareTo()： public interface Comparable { public int compareTo(T o);} Comparable 可以让实现它的类的对象进行比较，具体的比较规则是按照 compareTo 方法中的规则进行。这种顺序称为 自然顺序。 compareTo 方法的返回值有三种情况： e1.compareTo(e2) >

E 1 > e2e1.compareTo (e 2) = 0, e 1 = e2e1.compareTo (e 2) < 0, e 1 < e 2

Note:

1. Since null is neither a class nor an object, you should pay attention to the case of e.compareTo (null) when rewriting the compareTo method, and even if the e.equals (null) returns the false,compareTo method, you should actively throw a null pointer exception NullPointerException.

When the 2.Comparable implementation class overrides the compareTo method, it generally requires that the result of e1.compareTo (e2) = = 0 be consistent with that of e1.equals (e2). In this way, when you use collection containers such as SortedSet, which are sorted according to the natural order of the class in the future, you can ensure that the order of the saved data is the same as expected. One may wonder what happens if the second point above is violated.

For example, if you add two objects an and b to a SortedSet to satisfy (! a.equals (b) & & a.compareTo (b) = = 0) and do not specify another Comparator, then when you add an and then add b, you will add a failed return false, and the size of SortedSet will not increase, because they are the same in SortedSet's view, and repetition is not allowed in SortedSet.

In fact, the results of all Java core classes that implement the Comparable interface are consistent with the equlas method. List or normal arrays that implement the Comparable interface can be sorted using the Collections.sort () or Arrays.sort () method.

Only objects that implement the Comparable interface can be directly used as the key of SortedMap (SortedSet), otherwise the Comparator collation will have to be specified outside.

So if your self-defined classes want to use ordered collection classes, you need to implement the Comparable interface, such as:

**

Description: entity class books for testing, implementing Comparable interface, natural sorting

Author: shixinzhang

Data: 10Accord 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 +'}';}

/ * *

This method is called to sort when BookBean is added to the TreeSet

@ param another

@ return * / @ Override public int compareTo (Object another) {if (another instanceof BookBean) {BookBean anotherBook = (BookBean) another; int result

/ / for example, result = getCount ()-anotherBook.getCount () sorted by book price here

/ / or in the order of String comparison / / result = getName () .compareTo (anotherBook.getName ())

If (result = = 0) {/ / when the price of the book is the same, compare the title. Make sure all attributes are compared once result = getName () .compareTo (anotherBook.getName ());} return result

} / / the same returns 0 return 0;}

The calculation method of rewriting hashCode

Iterative calculation based on all attributes to avoid repetition

When calculating hashCode, there are a lot of calculation factors 31, which are prime numbers and can no longer be divided.

@ return * / @ Override public int hashCode () {/ / calls hashCode () of String, which uniquely represents the content of a string int result = getName (). HashCode (); / / multiplied by 31, plus count result = 31 * result + getCount (); return result;}

Rewrite 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 ())

The above code also overrides the equlas (), hashCode () methods, which are recommended when custom classes may be compared in the future.

What I want to express here is that in some scenarios, the results of equals and compareTo should be consistent. If equals is not rewritten, there will be problems with the results obtained by using the Object.equals method, such as the HashMap.put () method. The equals method of key will be called first to compare, and then compareTo will be called.

When you rewrite the compareTo later, compare all the attributes once to determine that one is the same and compare the next attribute.

Comparable

The Comparable interface is part of the Java collection framework.

Comparator customized sorting

Comparator is also an interface under the java.util package. Before JDK 1.8, there were only two methods:

Public interface Comparator {public int compare (T lhs, T rhs); public boolean equals (Object object);}

Many new methods have been added since JDK 1.8:

Basically all of them are related to Function, so we won't introduce the new 1.8 for the time being.

You can see from the above that using natural sorting requires the class to implement Comparable and override the comparaTo method internally.

Comparator, on the other hand, makes collations externally and passes them as sorting policy parameters to certain classes, such as Collections.sort (), Arrays.sort (), or some internally ordered set (such as SortedSet,SortedMap, etc.).

The usage of Comparator is mainly divided into three steps:

Create an implementation class of the Comparator interface and assign a value to an object in the compare method to write a collation for the custom class to pass the Comparator object as a parameter to a method of the sort class to add a custom class used in the compare method to the sort class, for example:

/ / 1. Create an object that implements the Comparator interface 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 / / the specific comparison method refers to the compareTo method of natural sorting. Here only give an example of chestnut return newBookBean.getCount ()-newBookBean1.getCount ();} return 0;}}; / / 2. Pass this object as a formal parameter to the constructor of TreeSet TreeSet treeSet = new TreeSet (comparator); / / 3. Add the object treeSet.add (new NewBookBean ("A", 34)) of the class designed in the compare method in step 1 to TreeSet; treeSet.add (new NewBookBean ("S", 1)); treeSet.add (new NewBookBean ("V", 46)); treeSet.add (new NewBookBean ("Q", 26))

In fact, you can see that the use of Comparator is a strategic mode. The sort class holds a reference to the Comparator interface:

Comparator

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.