当前位置: 首页 > 编程笔记 >

Java中Set&List的迭代器实现步骤解析

袁泓
2023-03-14
本文向大家介绍Java中Set&List的迭代器实现步骤解析,包括了Java中Set&List的迭代器实现步骤解析的使用技巧和注意事项,需要的朋友参考一下

List

Java 的list又分为 ArrayList 和 LinkedList

ArrayList

private class Itr implements Iterator<E> {
    int cursor;    // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {}

    public boolean hasNext() {
      return cursor != size;
    }

    @SuppressWarnings("unchecked")
    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;
      return (E) elementData[lastRet = i];
    }

    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();
      }
    }
  }

从代码中我们不难看出迭代器维护上一次return的元素下边和下一个将要return的元素下标,并且迭代器在进行修改操作时会检查在本次操作与上次操作之间是否有迭代器以外的操作,并且适时抛出ConcurrentModificationException(并发修改异常)来阻止更多错误的发生

LinkedList

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
      // assert isPositionIndex(index);
      next = (index == size) ? null : node(index);
      nextIndex = index;
    }

    public boolean hasNext() {
      return nextIndex < size;
    }

    public E next() {
      checkForComodification();
      if (!hasNext())
        throw new NoSuchElementException();

      lastReturned = next;
      next = next.next;
      nextIndex++;
      return lastReturned.item;
    }

    public boolean hasPrevious() {
      return nextIndex > 0;
    }

    public E previous() {
      checkForComodification();
      if (!hasPrevious())
        throw new NoSuchElementException();

      lastReturned = next = (next == null) ? last : next.prev;
      nextIndex--;
      return lastReturned.item;
    }

    public int nextIndex() {
      return nextIndex;
    }

    public int previousIndex() {
      return nextIndex - 1;
    }

    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++;
    }

    public void set(E e) {
      if (lastReturned == null)
        throw new IllegalStateException();
      checkForComodification();
      lastReturned.item = e;
    }

    public void add(E e) {
      checkForComodification();
      lastReturned = null;
      if (next == null)
        linkLast(e);
      else
        linkBefore(e, next);
      nextIndex++;
      expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
      Objects.requireNonNull(action);
      while (modCount == expectedModCount && nextIndex < size) {
        action.accept(next.item);
        lastReturned = next;
        next = next.next;
        nextIndex++;
      }
      checkForComodification();
    }

    final void checkForComodification() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  }

LinkedList的迭代器类的实现逻辑与ArrayList大致相近但是其访问元素的方式由原来的下标变为 "指针"(Java强引用)

Set

通过看Java源码可以知道Set全家桶基本上都包含了Map,相当于是一种组合的方式

HashSet

构造方法

HashSet有多个构造方法但都是初始化一个HashMap或其子类

/**
   * Constructs a new, empty set; the backing {@code HashMap} instance has
   * default initial capacity (16) and load factor (0.75).
   */
  public HashSet() {
    map = new HashMap<>();
  }

  /**
   * Constructs a new set containing the elements in the specified
   * collection. The {@code HashMap} is created with default load factor
   * (0.75) and an initial capacity sufficient to contain the elements in
   * the specified collection.
   *
   * @param c the collection whose elements are to be placed into this set
   * @throws NullPointerException if the specified collection is null
   */
  public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
  }

  /**
   * Constructs a new, empty set; the backing {@code HashMap} instance has
   * the specified initial capacity and the specified load factor.
   *
   * @param   initialCapacity  the initial capacity of the hash map
   * @param   loadFactor    the load factor of the hash map
   * @throws   IllegalArgumentException if the initial capacity is less
   *       than zero, or if the load factor is nonpositive
   */
  public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
  }

  /**
   * Constructs a new, empty set; the backing {@code HashMap} instance has
   * the specified initial capacity and default load factor (0.75).
   *
   * @param   initialCapacity  the initial capacity of the hash table
   * @throws   IllegalArgumentException if the initial capacity is less
   *       than zero
   */
  public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
  }

  /**
   * Constructs a new, empty linked hash set. (This package private
   * constructor is only used by LinkedHashSet.) The backing
   * HashMap instance is a LinkedHashMap with the specified initial
   * capacity and the specified load factor.
   *
   * @param   initialCapacity  the initial capacity of the hash map
   * @param   loadFactor    the load factor of the hash map
   * @param   dummy       ignored (distinguishes this
   *       constructor from other int, float constructor.)
   * @throws   IllegalArgumentException if the initial capacity is less
   *       than zero, or if the load factor is nonpositive
   */
  HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
  }

iterator方法

该接口在HashSet中的实现相当的简单,可以看到iterator返回了keySet().iterator()

public Iterator<E> iterator() {
    return map.keySet().iterator();
  }

HashMap的KeySet

从这一处代码可以看到iterator()返回了对象 KeyIterator

final class KeySet extends AbstractSet<K> {
    public final int size()         { return size; }
    public final void clear()        { HashMap.this.clear(); }
    public final Iterator<K> iterator()   { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
      return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
      return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
      Node<K,V>[] tab;
      if (action == null)
        throw new NullPointerException();
      if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (Node<K,V> e : tab) {
          for (; e != null; e = e.next)
            action.accept(e.key);
        }
        if (modCount != mc)
          throw new ConcurrentModificationException();
      }
    }
  }

HashMap的KeyIterator

KeyIterator是HashIterator一个子类在此一并展示了,这个类从字段结构上跟LinkedList的ListItr还是很像的

获取next的机制 Node<K,V> 内部本身包含一个next引用当HashIterator或其子类对象调用方法nextNode时,若该引用非空者优先返回该引用指向的对象,否则掩盖引用的index在HashMap内部的 Node<K,V> 数组table中向后找, 直到找到一个不为空的引用,或者到table结束也没有找到, 那么此时返回空引用

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;
      removeNode(p.hash, p.key, null, false, false);
      expectedModCount = modCount;
    }
  }

  final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
  }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持小牛知识库。

 类似资料:
  • 本文向大家介绍C++ 模拟实现list(迭代器)实现代码,包括了C++ 模拟实现list(迭代器)实现代码的使用技巧和注意事项,需要的朋友参考一下 C++ 模拟实现list(迭代器) 实现代码: 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

  • 当前:Bag$Node@1786F9D5下一个:Bag$Node@704D6E83 看起来很清楚,至少在我看来,下一个节点每次都会设置一个新节点。我将所有四个元素都添加到包中,但条目丢失,并为每个索引返回null。toArray()函数显示 我敢肯定这是一件简单得让人眼花缭乱的事情。下面是整个实现。

  • 本文向大家介绍Docker容器连接实现步骤解析,包括了Docker容器连接实现步骤解析的使用技巧和注意事项,需要的朋友参考一下 一般来说,容器启动后,我们都是通过端口映射来使用容器提供的服务,实际上,端口映射只是使用容器服务的一种方式,除了这种方式外,还可以使用容器连接的方式来使用容器服务。 例如,有两个容器,一个容器运行一个SpringBoot项目,另一个容器运行着mysql数据库,可以通过容器

  • 问题内容: 什么是迭代器和集合?这两个有关系吗? 接口迭代器是否只预定义了这些方法名称,还是用户定义了这些方法名称?下面的这四行实际上说明了什么? 谢谢。我正在看一本藏书。 问题答案: 顾名思义,Java集合是事物的集合。如果您不知道该单词,请在字典中查找。 有很多类型的集合。以集合的数学概念为例。您可以将任意事物放入集合中,但是永远不会包含同一事物。在集中的东西是没有顺序的,那就是你不能说 A

  • 本文向大家介绍Node.js中的异步生成器与异步迭代详解,包括了Node.js中的异步生成器与异步迭代详解的使用技巧和注意事项,需要的朋友参考一下 前言 生成器函数在 JavaScript 中的出现早于引入 async/await,这意味着在创建异步生成器(始终返回 Promise 且可以 await 的生成器)的同时,还引入了许多需要注意的事项。 今天,我们将研究异步生成器及其近亲——异步迭代。

  • 本文向大家介绍Java实现布隆过滤器的方法步骤,包括了Java实现布隆过滤器的方法步骤的使用技巧和注意事项,需要的朋友参考一下 前言 记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法。因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器。 布隆过滤器