我需要确保某个 Set<String>
我创建的代码没有在其他地方修改。当然,我最终使用了 Guava 的 ImmutableSet为此。
这个不可变集非常大(大约 59K 个字符串),我必须执行 Set#contains
每次调用特定方法时检查。所以我想知道是否有任何方法可以指定大集合中的查找。 Guava 的文档说:
A high-performance, immutable Set with reliable, user-specified iteration order. Does not permit null elements.
什么是user-specified iteration
意味着如果不可变集是通过调用 ImmutableSet#copyOf(aHashSet)
创建的?请问性能contains(String)
如果我使用 ImmutableSet#contains
会受到不利影响而不是 HashSet#contains
?更准确地说,我的问题如下:
有了一个不错的散列函数并且没有太多元素进入同一个桶,人们会期望 HashSet#contains
为 O(1)。将使用 copyOf
创建一个 ImmutableSet坚持这个?
我怀疑情况可能并非如此,原因有二:
Guava forum discussion on precisely this question (虽然似乎没有提供决定性的答案)。
我不清楚
ImmutableSet#contains
遵从java.util.Set#contains
(即,在我的例子中,HashSet
中的实现)或com.google.common.collect.ImmutableCollection#contains
.如果是后者,那么ImmutableSet#contains
将是一个 O(n) 操作。
最佳答案
我在 the documentation 中看到的唯一确认是以下内容:
this class's factory methods create hash-based instances, ...
换句话说,您可以期望查找使用类似于 HashSet
的散列机制(因此具有性能特征)。文档故意含糊不清,以便可以进行各种改进(例如,对某些特殊情况使用特殊实现,如单例或空集)。
迭代顺序将取决于创建方法。在 copyOf
的情况下,它将是您传入的 Iterable
的迭代顺序(当然是在创建副本时)。这是有据可查的:
Returns an immutable set containing the given elements, in order.
至于是否服从set的contains方法,没有。因为 ImmutableSet
制作了一个副本(与 Collections.unmodifiableSet()
不同),它显然不能推迟到原始集的任何操作。
关于java - Guava 的 ImmutableSet 成员方法是否模仿 java.util.HashSet#contains?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28391456/