java - HashSet迭代

Question

我有一个关于 Java 中 HashSet 迭代器的查询。在《Java Generics and Collections》一书中，有如下描述:

The chief attraction of a hash table implementation for sets is the (ideally) constanttime performance for the basic operations of add, remove, contains, and size. Its main disadvantage is its iteration performance; since iterating through the table involves examining every bucket, its cost is proportional to the table size regardless of the size of the set it contains.

它声明迭代器查找基础表的每个桶。但是通过实际实现(JDK 8)，我看到 HashIterator 存储下一个节点引用。所以看起来迭代器不需要访问每个桶。

是书错了还是我理解错了？

Answer 1

文档是正确的。虽然KeyIterator确实调用了nextNode().key，像这样

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

基类HashIterator 中nextNode() 的代码具有文档所讨论的循环:

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

主体为空的 do/while 循环逐个遍历桶，寻找下一个条目。

唯一可能相关的情况是当您迭代一个哈希集时，该哈希集预先分配有大量存储桶，但尚未填充大量项目。当您让 HashSet 在您添加更多项目时自行增长时，桶的数量将与您目前插入的项目数量成正比，因此减速不会很明显。