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

问题描述

来自 HashSet 的 JavaDocs:

此类为基本操作提供恒定时间性能(添加、删除、包含和大小)，假设散列函数分散桶中的元素正确.迭代这个集合所需时间与 HashSet 实例大小的总和成正比(元素的数量)加上支持 HashMap 的容量"实例(桶的数量).因此，不要设置是非常重要的初始容量太高(或负载系数太低)如果迭代性能很重要

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 使用 HashMap 实现，其中元素是映射键.由于地图有定义数量的桶，可以包含一个或多个元素，迭代需要检查每个桶，是否包含元素.

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屋！