java - Guava 的 ImmutableSet 成员方法是否模仿 java.util.HashSet#contains？

Question

我需要确保某个 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坚持这个？

我怀疑情况可能并非如此，原因有二:

1. Guava forum discussion on precisely this question (虽然似乎没有提供决定性的答案)。

2. 我不清楚ImmutableSet#contains遵从 java.util.Set#contains (即，在我的例子中， HashSet 中的实现)或 com.google.common.collect.ImmutableCollection#contains .如果是后者，那么ImmutableSet#contains将是一个 O(n) 操作。

Answer 1

我在 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() 不同)，它显然不能推迟到原始集的任何操作。