HashSet上的迭代成本还取决于支持映射的能力？ [英] What the iteration cost on a HashSet also depend on the capacity of backing map?

问题描述

从 HashSet的JavaDocs ： b
$ b

这个类为基本操作
（add，remove，contains和size）提供了恒定的时间性能， ，假设散列函数将桶元素正确分散
元素。迭代此集合
需要的时间与HashSet实例的大小
（元素数量）加上支持HashMap
实例（桶的数量）的容量的总和成正比。因此，如果
的迭代性能很重要，则不要设置
的初始容量太高（或者负载因子太低）。

为什么迭代需要的时间与总和（集合中的元素数量+支持映射的容量）成正比，而不仅仅与集合中元素的数量本身有关系？

。

解决方案 code>使用 HashMap 来实现，其中元素是地图关键字。由于映射具有定义数量的可以包含一个或多个元素的存储桶，所以迭代需要检查每个存储桶是否包含元素。

From the JavaDocs of HashSet:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important

Why does iteration takes time proportional to the sum(number of elements in set+ capacity of backing map) and not only to the number of elements in the set itself ?

.

解决方案

HashSet is imlemented using a HashMap where the elements are the map keys. Since a map has a defined number of buckets that can contain one or more elements, iteration needs to check each bucket, whether it contains elements or not.

这篇关于HashSet上的迭代成本还取决于支持映射的能力？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！