使用工厂方法Set.of()和Map.of()创建的集合和地图的时间复杂度是多少? [英] What is a time complexity for sets and maps created with a factory methods Set.of() and Map.of()?
问题描述
在Java中,当我使用 Set.of()
或 set
时> map 与 Map.of()
包含 和
获取
操作?是O(1)吗?
In Java, when I create a set
with Set.of()
or a map
with Map.of()
what is the time complexity of the contains
and get
operations? Is it O(1)?
推荐答案
Set.of
和 Map.of
API返回JDK私有实现的实例。规范不能保证这些实现的性能。但是,API确实会返回有关可以进行性能说明的特定实现。因此,该问题是合理的,并且与(假设的)问题不同,例如 Map.get
的性能如何?这是一个很糟糕的问题,因为有许多不同的 Map
实现。
The Set.of
and Map.of
APIs return instances of JDK-private implementations. The performance of these implementations is not guaranteed by the specification. However, the APIs do return specific implementations about which performance statements can be made. Thus, the question is reasonable and is distinct from a (hypothetical) question such as "What is the performance of Map.get
?" which is a poor question because there are many different Map
implementations.
无论如何,在<$之后的实现c $ c> Set.of (对于大于两个的大小)和 Map.of
(对于大于一个的大小)使用简单的开放式寻址具有线性探测以解决冲突的哈希算法。如果元素的(键)哈希为,则 Set.contains
和 Map.get
操作为O(1)。分布合理。
In any case, the implementations behind Set.of
(for size greater than two) and Map.of
(for size greater than one) use a simple open addressed hashing scheme with linear probing for collision resolution. The Set.contains
and Map.get
operations are O(1) if the elements' (keys') hashes are reasonably well distributed.
这篇关于使用工厂方法Set.of()和Map.of()创建的集合和地图的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!