Explication détaillée de l'exemple de code de l'itérateur dans le cadre de collection Java

Cet article vous fournit principalement une brève introduction aux informations pertinentes sur l'itérateur dans le cadre de collection Java. Il a une certaine valeur de référence. Les amis intéressés peuvent se référer à

Les données de tableau en Java peuvent être obtenues via. index, qu'en est-il des objets ? Également via l'index ? Aujourd'hui, nous allons analyser la méthode itération-Iterator pour obtenir des objets de collection dans les collections Java.

Cet article analyse principalement la partie itérateur dans le framework de collection Java, Iterator. L'analyse du code source est basée sur JDK1.8, outil d'analyse, AndroidStudio. Veuillez me corriger s'il y a des lacunes dans l'analyse de l'article !

1. Introduction

Nous utilisons souvent l'interface d'itération fournie par JDK pour itérer les collections Java.

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

Ce qui précède est le modèle de base utilisé par les itérateurs. En fait, l'itération peut être simplement comprise comme un parcours, qui est une classe de méthodes standardisée pour parcourir tous les objets dans divers conteneurs. Il contrôle toujours l'itérateur et lui envoie les commandes "forward", "backward" et "get current element" pour parcourir indirectement toute la collection. En Java, Iterator est une interface qui ne fournit que des règles de base pour l'itération :

  public interface Iterator<E> {
  //判断容器内是否还有可供访问的元素
  boolean hasNext();
  //返回迭代器刚越过的元素的引用，返回值是 E
  E next();
  //删除迭代器刚越过的元素
  default void remove() {
    throw new UnsupportedOperationException("remove");
  }
}

Ce qui précède est la déclaration de base d'un itérateur, que nous analysons à travers des collections spécifiques.

2. Classification des collections

2.1 Itérateur d'ArrayList

On peut savoir en analysant le code source d'ArrayList qu'une classe interne est d'abord définie à l'intérieur ArrayList Itr, cette classe interne implémente l'interface Iterator, comme suit :

private class Itr implements Iterator<E> {
  //....
}

La classe interne implémente l'interface Iterator, et l'Iterator d'ArrayList renvoie sa classe interne Itr, donc nous Voyez principalement comment Itr est implémenté.

  public Iterator<E> iterator() {
    return new Itr();
  }

Ensuite, nous analysons l'implémentation de sa classe interne Itr.

  private class Itr implements Iterator<E> {

    protected int limit = ArrayList.this.size;

    int cursor;    // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
      return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      int i = cursor;
      if (i >= limit)
        throw new NoSuchElementException();
      Object[] elementData = ArrayList.this.elementData;
      if (i >= elementData.length)
        throw new ConcurrentModificationException();
      cursor = i + 1;
      return (E) elementData[lastRet = i];
    }

    public void remove() {
      if (lastRet < 0)
        throw new IllegalStateException();
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

      try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
        limit--;
      } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
      }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
      Objects.requireNonNull(consumer);
      final int size = ArrayList.this.size;
      int i = cursor;
      if (i >= size) {
        return;
      }
      final Object[] elementData = ArrayList.this.elementData;
      if (i >= elementData.length) {
        throw new ConcurrentModificationException();
      }
      while (i != size && modCount == expectedModCount) {
        consumer.accept((E) elementData[i++]);
      }
      // update once at end of iteration to reduce heap write traffic
      cursor = i;
      lastRet = i - 1;

      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  }

Tout d'abord, analysons la variable définie :

    protected int limit = ArrayList.this.size;

    int cursor;    // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

Parmi elles, la limite est la taille de l'ArrayList actuelle, et le curseur représente l'élément suivant . Index, et lastRet est l'index de l'élément précédent. Sinon, il renvoie -1 - ExpectModCount est de peu d'utilité. Nous analyserons ensuite et verrons comment déterminer s'il y a des éléments ultérieurs lors de l'itération.

  public boolean hasNext() {
      return cursor < limit;
  }

C'est très simple, il s'agit de déterminer si l'index de l'élément suivant a atteint la capacité du tableau. Si c'est le cas, ce sera fini !

Ensuite, analysons ensuite la méthode d'obtention de l'élément de l'index actuel

    public E next() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      int i = cursor;
      if (i >= limit)
        throw new NoSuchElementException();
      Object[] elementData = ArrayList.this.elementData;
      if (i >= elementData.length)
        throw new ConcurrentModificationException();
      cursor = i + 1;
      return (E) elementData[lastRet = i];
    }

Pourquoi devons-nous déterminer modCount dans la méthode suivante ? Autrement dit, il est utilisé pour déterminer si la collection a été modifiée pendant le processus de parcours. modCount est utilisé pour enregistrer le nombre de modifications de la collection ArrayList. Il est initialisé à 0. A chaque fois que la collection est modifiée (modifications sur la structure, les mises à jour internes ne sont pas comptées), comme l'ajout, la suppression et d'autres méthodes, modCount vaut 1. , donc si modCount reste inchangé, alors indique que le contenu de la collection n'a pas été modifié. Ce mécanisme est principalement utilisé pour implémenter le mécanisme de défaillance rapide de la collection ArrayList. Parmi les collections Java, une grande partie des collections ont des mécanismes de défaillance rapide. Par conséquent, pour garantir qu'aucune erreur ne se produit pendant le processus de parcours, nous devons nous assurer qu'aucune modification structurelle n'est apportée à la collection pendant le processus de parcours (à l'exception de la méthode Remove, bien sûr, si une erreur anormale se produit, nous devons vérifier attentivement). si le programme contient des erreurs au lieu de Aucun traitement n'est effectué après la capture. Le code ci-dessus est relativement simple, il renvoie simplement la valeur du tableau à l'index.

Pour la méthode d'itération d'ArrayList, elle juge principalement la valeur de l'index et la compare avec la taille du tableau pour voir s'il n'y a pas de données à parcourir, puis obtient les valeurs​​dans le tableau à son tour. Il capture principalement chaque collection. L'implémentation sous-jacente peut être itérée.

Ensuite, nous analyserons la méthode Iterator de HashMap D'autres méthodes sont similaires, à condition que vous compreniez l'implémentation sous-jacente.

2.2 Iterator de HashMap

Dans HashMap, il existe également une classe qui implémente l'interface Iterator, mais ce n'est qu'une classe abstraite, HashIterator. comment il est mis en œuvre.

 private abstract class HashIterator<E> implements Iterator<E> {
    HashMapEntry<K,V> next;    // next entry to return
    int expectedModCount;  // For fast-fail
    int index;       // current slot
    HashMapEntry<K,V> current;   // current entry

    HashIterator() {
      expectedModCount = modCount;
      if (size > 0) { // advance to first entry
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
          ;
      }
    }

    public final boolean hasNext() {
      return next != null;
    }

    final Entry<K,V> nextEntry() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      HashMapEntry<K,V> e = next;
      if (e == null)
        throw new NoSuchElementException();

      if ((next = e.next) == null) {
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
          ;
      }
      current = e;
      return e;
    }

    public void remove() {
      if (current == null)
        throw new IllegalStateException();
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      Object k = current.key;
      current = null;
      HashMap.this.removeEntryForKey(k);
      expectedModCount = modCount;
    }
  }

De même, il définit également une variable

    HashMapEntry<K,V> next;    // next entry to return
    int expectedModCount;  // For fast-fail
    int index;       // current slot
    HashMapEntry<K,V> current;   // current entry

next pour représenter le prochain nœud d'entrée attenduModCount est également utilisé pour déterminer le statut modifié . Mécanisme d’échec rapide pour les collections. Index représente l'index actuel et l'entrée de nœud représentée par l'index actuel. Voyons comment déterminer s'il existe une valeur pour l'élément suivant.

    public final boolean hasNext() {
      return next != null;
    }

Il est très simple de déterminer si next est nul. S'il est nul, cela signifie qu'il n'y a pas de données.

Analysez ensuite la méthode d'obtention des éléments

    final Entry<K,V> nextEntry() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      HashMapEntry<K,V> e = next;
      if (e == null)
        throw new NoSuchElementException();
      // 一个Entry就是一个单向链表
      // 若该Entry的下一个节点不为空，就将next指向下一个节点;
      // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
      if ((next = e.next) == null) {
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
          ;
      }
      current = e;
      return e;
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!