Guava的ImmutableSet成员方法模仿java.util.HashSet＃是否包含？

Question

我需要确保我创建的某个Set<String>未在代码中的其他位置修改。当然，我最终为此使用了Guava的ImmutableSet。

这个不可变的集合非常大（大约59K字符串），并且每次调用某个特定的方法时都必须执行Set#contains检查。所以我想知道是否有任何方法来指定大集合中的查找。番石榴的文档说：

一个高性能，不可变的集可靠，用户指定的 迭代顺序。不允许空元素。

user-specified iteration如果不可变集是通过调用ImmutableSet#copyOf(aHashSet)创建的，那么它是什么意思？如果我使用ImmutableSet#contains而不是HashSet#contains，contains(String)的性能会受到不利影响吗？更精确地说，我的问题是：

一个体面的哈希函数并没有太多的因素让在同一个桶中，人们所期望的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看到的唯一确认的是以下几点：

此类的工厂方法创建基于散列的情况下，...

换句话说，你可以期待查找使用哈希机制（并因此具有性能特征），类似于HashSet。文档是故意模糊的，因此可以进行各种改进（例如，对于某些特殊情况使用特殊实现，例如单例或空集）。

迭代顺序将取决于创建方法。在copyOf的情况下，它将是您通过的Iterable的迭代顺序（当然，在进行复制时）。这是强烈记录：

按顺序返回包含给定元素的不可变集合。

至于它是否遵循set的contains方法，no。由于ImmutableSet使复制（不像Collections.unmodifiableSet()），它显然不能推迟到任何操作的原始设置。

Answer 2

只是Mark Peters答案的一小部分。

随着RegularImmutableSet通过存储元素两次（一旦命令，一旦散列），订单得到保留。这仍然比原来的HashSet便宜，它代表HashMap，它为存储的每个元素创建一个条目。

有优化的实现SingletonImmutableSet和EmptyImmutableSet。当你从一个不可变的集合或地图开始时，还有许多其他的东西会被使用。

如果您想了解更多信息，请使用source（但仅取决于文档）。

您链接的性能讨论只处理散列冲突。通常，性能为O(1)，只是在散列函数非常糟糕的情况下，它会退化。这适用于所有哈希数据结构，但效果不同。 RegularImmutableSet具有更好的数据局部性，HashSet使用链接并可以更好地处理冲突。

曾经有一个problem，其中某种冲突会导致过多的冲突，但它很久以前就已经修复了。现在，偶然遇到类似的事情是不可能的。