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

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

List

java 的list又分为 ArrayList 和 LinkedList

ArrayList

private class Itr implements Iterator {

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 {

private Node lastReturned;

private Node 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 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();

FDCyLYTpd }

}

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 iterator() {

return map.keySet().http://iterator();

}

HashMap的KeySet

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

final class KeySet extends AbstractSet {

public final int size() { return size; }

public final void clear() { HashMap.this.clear(); }

public final Iterator 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 spliterator() {

return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);

}

public final void forEach(Consumer super K> action) {

Node[] tab;

if (action == null)

throw new NullPointerException();

if (size > 0 && (tab = table) != null) {

int mc = modCount;

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

abstract class HashIterator {

Node next; // next entry to return

Node current; // current entry

int expectedModCount; // for fast-fail

int index; // current slot

HashIterator() {

expectedModCount = modCount;

Node[] 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 nextNode() {

Node[] t;

Node 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 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 {

public final K next() { return nextNode().key; }

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。