HashSet迭代

Question

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

对于集的哈希表实现的主要吸引力是(理想情况下)基本操作添加、删除、包含和大小的恒定时间性能。它的主要缺点是它的迭代性能；因为迭代遍历表需要检查每个桶，因此它的成本与表的大小成正比，而不管它包含的集合大小如何。

它指出迭代器在底层表的每个桶中查找。但是通过实际实现(JDK 8)，我看到HashIterator存储下一个节点引用。因此，迭代器似乎不需要访问每个桶。

这里的书是错的还是我的理解错了？

Answer 1

文件是对的。虽然KeyIterator确实调用了nextNode().key，但如下所示

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

基类nextNode()中的HashIterator代码具有文档正在讨论的循环：

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自行增长时，存储桶的数量将与插入到目前为止的项目数量成正比，因此减速不会显着。