java - 哈希集迭代

Question

我有一个关于 Java 中 HashSet 迭代器的查询。 在《Java泛型和集合》一书中，有如下说明:

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 随着您添加更多项目而自行增长时，存储桶的数量将与您到目前为止插入的项目数量成正比，因此速度减慢不会很明显。