イテレータ・パターン

イテレータはコンテナを走査するために使用され、イテレータパターンはオブジェクトのコレクションの走査操作をコレクションクラスからイテレータクラスに分割し、両方の責任をより単一にし、それらの結合を低減します。トラバーサル用の連鎖配列の場合、forループの使用は比較的簡単であると感じるかもしれませんが、複雑なデータ構造の場合は、少し問題になることができる独自のコードのトラバーサルを書くので、イテレータパターンは、ある程度トラバーサルの難しさを軽減します。イテレータで重要なメソッド next, hasNext

java抽象リストを

一般的には、2つの重要な内部クラスItrは、ListItr。 ここでは、ソースコードを介して内部の機能を分析するために、まず、自分の印象を残すために、以下を読んで、後で説明します。

 private class Itr implements Iterator<E> {
 /**
 * Index of element to be returned by subsequent call to next.
 */
 int cursor = 0;
 /**
 * Index of element returned by most recent call to next or
 * previous. Reset to -1 if this element is deleted by a call
 * to remove.
 */
 int lastRet = -1;
 /**
 * The modCount value that the iterator believes that the backing
 * List should have. If this expectation is violated, the iterator
 * has detected concurrent modification.
 */
 int expectedModCount = modCount;
 public boolean hasNext() {
 return cursor != size();
 }
 public E next() {
 checkForComodification();
 try {
 int i = cursor;
 E next = get(i);
 lastRet = i;
 cursor = i + 1;
 return next;
 } catch (IndexOutOfBoundsException e) {
 checkForComodification();
 throw new NoSuchElementException();
 }
 }
 public void remove() {
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();
 try {
 AbstractList.this.remove(lastRet);
 if (lastRet < cursor)
 cursor--;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException e) {
 throw new ConcurrentModificationException();
 }
 }
 final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }
 }

重要な要素

cursor（カーソル） 現在の要素の位置、 lastRet（ラストリセット） 最近アクセスされた要素の位置、 lastRetが-1の場合は、最近アクセスされた要素が削除されたことを示します。 expectedModCount（予想されるモッドカウント） モッドカウントは、ArrayListのレコード配列が変更された回数です。

これらの要素に注目する理由

1.イテレータで要素を削除したり追加したりすると、見逃した要素にトラバーサルして戻ってくることが多く、トラバーサルが許可されていないことにつながるので、要素をトラバースしているときにコンテナ要素が変更されるConcurrentModificationException（）に遭遇しているはずです。要素を追加すると、その要素の走査を繰り返す確率があり、要素を削除すると、その要素を逃します。

2.トラバーサルの精度を確保するために、この予測できない動作や保留中の動作の結果を排除するために、通常2つの方法があります、1つは、トラバース時に要素を追加または削除することはできません、もう一つは、トラバーサルエラーの後に要素を追加または削除することです。前者は実装が難しく、いつトラバーサルが完了するかわかりません。そのため、トラバース中に要素を追加したり削除したりすることはできません。これを実現するには、前述の要素が必要です。

ソース・コードの checkForComodification() メソッドは、コンテナ内の要素が変換されているかどうかを比較し、変換されている場合は例外をスローします。注意深く見ると、remove()メソッドも提供していることがわかるかもしれません。これは、トラバースされる次の要素を削除することができますが、連続して削除することはできません！

AbstractList。this.xxxxは、AbstractListクラスのxxxx個のメソッドまたは要素が、このクラスのメソッドまたは要素の代わりに呼び出されることを示します。

LinkListイテレータの

メソッドは、イテレータメソッドに従って同じですが、唯一のNodeでシーケンスを置き換えるには、イテレータを追加追加し、メソッドを削除するには、要素を追加または削除するには、このイテレータを介して自由にトラバースすることができますLinkListの追加メソッドは、期待されるModCountの値を増加させないため、追加のイテレータを使用することを忘れないでください。

	 private Node<E> lastReturned;
 private Node<E> next;
 private int nextIndex;
 private int expectedModCount = modCount;
public E next() {
 checkForComodification();
 if (!hasNext())
 throw new NoSuchElementException();
 lastReturned = next;
 next = next.next;
 nextIndex++;
 return lastReturned.item;
 }
public void add(E e) {
 checkForComodification();
 lastReturned = null;
 if (next == null)
 linkLast(e);
 else
 linkBefore(e, next);
 nextIndex++;
 expectedModCount++;
 }
public void remove() {
 checkForComodification();
 if (lastReturned == null)
 throw new IllegalStateException();
 Node<E> lastNext = lastReturned.next;
 unlink(lastReturned);
 if (next == lastReturned)
 next = lastNext;
 else
 nextIndex--;
 lastReturned = null;
 expectedModCount++;
 }

私は個人的に要素を削除するには、linkListのトラバーサルプロセスでは、繰り返し読み取り、または読み取りが発生しませんが、トラバーサルプロセスは、彼はまだArrayListに比べて、ConcurrentModificationExceptionをスローされますイテレータによって変更されていない場合、彼はイテレータを使用することができます要素に追加されたと思います。

HashMap

hashMapイテレータ重要なクラスHashIteratorは、彼がイテレータKeyIterator、ValueIterator、EntryIteratorを持っていることを考えることができるはずの方法のより多くのマップのトラバーサル。ソースコードを見るためのパスワードはありません！

abstract class HashIterator {
 Node<K,V> next; // next entry to return
 Node<K,V> current; // current entry
 int expectedModCount; // for fast-fail
 int index; // current slot
 HashIterator() {
 expectedModCount = modCount;
 Node<K,V>[] t = table;
 current = next = null;
 index = 0;
 if (t != null && size > 0) { // advance to first entry
 do {} while (index < t.length && (next = t[index++]) == null);
 }
 }
 public final boolean hasNext() {
 return next != null;
 }
 final Node<K,V> nextNode() {
 Node<K,V>[] t;
 Node<K,V> e = next;
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 if (e == null)
 throw new NoSuchElementException();
 if ((next = (current = e).next) == null && (t = table) != null) {
 do {} while (index < t.length && (next = t[index++]) == null);
 }
 return e;
 }
 public final void remove() {
 Node<K,V> p = current;
 if (p == null)
 throw new IllegalStateException();
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 current = null;
 K key = p.key;
 removeNode(hash(key), key, null, false, false);
 expectedModCount = modCount;
 }
 }

この点では、バーの内部のコードのいくつかは、結局のところ、ソースコードや興味深いことに自分自身を読むには、その雄牛を鑑賞することができます。

.next) == null , この部分が来るたびに実行され、nextは毎回次の要素を指し、eは常に現在の要素です。この式がnullであるとき、この連鎖表が終わりに達したことを証明し、次の要素は次のバケツに入る必要があるため、next = t[index++]となり、nextは次の要素を指し示すことに成功し、eは今指し示すべき要素を指し示すことになります。

この抽象クラスは、KeyIterator、ValueIterator、EntryIteratorのサブクラスで、ソースコードを見ると、実際にあなたのforeach、上位のトラバーサルがわかります。

final class KeyIterator extends HashIterator
 implements Iterator<K> {
 public final K next() { return nextNode().key; }
 }
 final class ValueIterator extends HashIterator
 implements Iterator<V> {
 public final V next() { return nextNode().value; }
 }
 final class EntryIterator extends HashIterator
 implements Iterator<Map.Entry<K,V>> {
 public final Map.Entry<K,V> next() { return nextNode(); }
 }

KeyIteratorは中のkeyを、ValueIteratorはvalueを取り出します。KeyIteratorをトラバースした後にmap.get(key)を使わないでください。foreachはイテレータのための構文糖であることを言い忘れていたようです。デコンパイルすればわかります。 javap -cは次のようにデコンパイルします。

スナップショット

前述したように、彼はこの配列の他のスレッドの追加と削除につながる読み取るように、元の配列の走査では、ConcurrentModificationExceptionがスローされます、あなたが考えることができるスナップショットスナップを構築するイテレータの使用ではありません。私はここでスナップショットを構築する方法についての私の見解を分析します。

1.直接イテレータを構築する場合、元の配列を直接コピーすることができます。実装はよりシンプルになりますが、イテレータの数はコンテナ参照のサイズを増加させます、同時にあまりにも多くの反復は、メモリ占有率はまだ非常に大きい場合！

2. MVCCパターンを模倣するために、mysqlトランザクションに関連付けられません。

2.1 コンテナ内の各オブジェクトに時間が追加されます（追加時刻、削除時刻）。すべての追加と削除の時間が計測され、データは論理的に削除されます。

2.2 コンテナに連鎖リストを追加し、各イテレータの作成時刻と完了まで走査されたかどうかを記録。

2.3 イテレータ・トラバーサルは、コンテナ内のデータの時刻を比較し、分離を実現します。つまり、このイテレータの作成時に削除されたものは見えず、このイテレータの作成後に追加されたものは見えません。イテレーションの完了後にチェーン・テーブルから削除

2.4 続いて、後でアクセスできないデータの削除が行われます。つまり、すべてのイテレータが作成された時刻よりも後の時刻に作成された場合、要素は再び使用されることはありませんし、リアルタイムで削除することができます。順番に保存するためにチェーンリストを持つコンテナなので、時間がこのイテレータの作成時刻よりも小さい場合は比較する最初のイテレータのより多くのチェーンリストの要素の時間を削除することができ、要素を削除することができますので、個人の比較をトラバースするたびに時間のかかるくだらない感じ。

2.5あなたは、この削除は非常にエレガントではないと思うかもしれませんが、私もそう思うので、もう一度考えてみてください。確かに少ないインデックスを高速化したい、インデックスから考えて、時間のためのスペース！ ................ 長い間考えた後、私はお粗末な解決策を思い付きました。ソフト削除コンテナという名前のコンテナの削除された要素を保存するためにコンテナを増やすには、各イテレータは、自分の場所にコピーのデータ浅いコピーのコンテナが作成され、その後、イテレータの反復は、最初のイテレータチェーンテーブルを確認するために完了した場合、要素の論理的な削除でコンテナの内部の削除に反復され、その後、コンテナのソフト削除でそれらの参照を削除します。

最後にもうひとつ。これだけ考えたら、例外を投げる方が簡単です。