对于非常大的数据集，我应该使用 `HashSet` 还是 `TreeSet`？
Should I use a `HashSet` or a `TreeSet` for a very large dataset?
我需要在数据结构中存储 2 到 1500 万个帐户（长度为 15 的 String）以供查找和检查唯一性。最初我计划将它们存储在 HashSet 中，但我怀疑查找速度会因为哈希冲突而变慢，最终会比 TreeMap（使用二进制搜索）慢。
不需要对数据进行排序。我正在使用 Java 7. 我有 64G 系统和 48G 专用于此应用程序。
这个问题不是 HashSet and TreeSet performance test 的重复问题，因为那个问题是关于 添加元素到 Set 的性能，而这个问题是关于检查现有 Set 重复值的性能。
如果您的 200 万到 1500 万条记录有 48 GB 的专用内存，您最好的选择可能是使用 HashMap<Key, Record>，其中您的密钥是 Integer 或 String 取决于您的要求。
只要您为 Map 提供足够的内存并具有适当的负载因子，就散列冲突而言，您会没事的。
我建议使用以下构造函数：new HashMap<>(13_000_000);（比您预期的记录数多 30% - HashMap 的实现会自动扩展到 2^24 个单元格） .
告诉您的应用程序此 Map 从一开始就非常大，因此它不需要在您填充它时自动增长。
HashMap 为其成员使用 O(1) 访问时间，而 TreeMap 使用 O(log n) 查找时间，但可以更有效地使用内存并且不需要一个聪明的散列函数。但是，如果您使用 String 或 Integer 键，则无需担心哈希函数的设计，恒定时间查找将是一个巨大的改进。另外， TreeMap / TreeSet 的另一个优点是排序顺序，您说您不关心；使用 HashMap.
如果列表的唯一目的是检查唯一帐号，那么我上面所说的一切仍然是正确的，但正如你在问题中所说的那样，你应该使用 HashSet<String>，而不是 HashMap。性能建议和构造函数参数仍然适用。
进一步阅读：HashSet and TreeSet performance test
当我们尝试使用适当的初始化参数在 HashMap 中存储 5000 万条记录时，插入速度开始变慢，尤其是在 3500 万条记录之后。更改为 TreeMap 可提供恒定的插入和检索性能。
观察：对于大型输入集，TreeMap 将提供比 HashMap 更好的性能。对于较小的集合，HashMap当然会提供更好的性能。
我需要在数据结构中存储 2 到 1500 万个帐户（长度为 15 的 String）以供查找和检查唯一性。最初我计划将它们存储在 HashSet 中，但我怀疑查找速度会因为哈希冲突而变慢，最终会比 TreeMap（使用二进制搜索）慢。
不需要对数据进行排序。我正在使用 Java 7. 我有 64G 系统和 48G 专用于此应用程序。
这个问题不是 HashSet and TreeSet performance test 的重复问题，因为那个问题是关于 添加元素到 Set 的性能，而这个问题是关于检查现有 Set 重复值的性能。
如果您的 200 万到 1500 万条记录有 48 GB 的专用内存，您最好的选择可能是使用 HashMap<Key, Record>，其中您的密钥是 Integer 或 String 取决于您的要求。
只要您为 Map 提供足够的内存并具有适当的负载因子，就散列冲突而言，您会没事的。
我建议使用以下构造函数：new HashMap<>(13_000_000);（比您预期的记录数多 30% - HashMap 的实现会自动扩展到 2^24 个单元格） .
告诉您的应用程序此 Map 从一开始就非常大，因此它不需要在您填充它时自动增长。
HashMap 为其成员使用 O(1) 访问时间，而 TreeMap 使用 O(log n) 查找时间，但可以更有效地使用内存并且不需要一个聪明的散列函数。但是，如果您使用 String 或 Integer 键，则无需担心哈希函数的设计，恒定时间查找将是一个巨大的改进。另外， TreeMap / TreeSet 的另一个优点是排序顺序，您说您不关心；使用 HashMap.
如果列表的唯一目的是检查唯一帐号，那么我上面所说的一切仍然是正确的，但正如你在问题中所说的那样，你应该使用 HashSet<String>，而不是 HashMap。性能建议和构造函数参数仍然适用。
进一步阅读：HashSet and TreeSet performance test
当我们尝试使用适当的初始化参数在 HashMap 中存储 5000 万条记录时，插入速度开始变慢，尤其是在 3500 万条记录之后。更改为 TreeMap 可提供恒定的插入和检索性能。
观察：对于大型输入集，TreeMap 将提供比 HashMap 更好的性能。对于较小的集合，HashMap当然会提供更好的性能。