我应该为一个非常大的数据集使用`HashSet`或`TreeSet`吗？

Question

我需要String在数据结构中存储2到1,500万个帐户(长度为15),以便查找和检查唯一性.最初我计划将它们存储在a中HashSet,但是我怀疑由于散列冲突,查找的速度会很慢,并且最终会比TreeMap慢(使用二进制搜索).

不需要对数据进行排序.我正在使用Java 7.我有64G系统,48G专用于此应用程序.

这个问题不是HashSet和TreeSet性能测试的重复,因为这个问题是关于向a添加元素Set的性能,这个问题是关于检查现有的重复值的性能.Set

Answer 1

如果您的200万到1500万条记录有48 GB的专用内存,那么您最好的选择可能是使用a HashMap<Key, Record>,其中您的密钥是a Integer或者String取决于您的要求.

只要你给了足够的内存Map并且有适当的加载因子,你就可以完成哈希冲突.

我建议使用以下构造函数:(new HashMap<>(13_000_000);比预期的记录数多30% - 这将通过实现自动扩展HashMap到2^24单元格).告诉您的应用程序,这Map将从一开始就非常大,因此它不需要在填充时自动增长.

HashMapO(1)对其成员使用访问时间,而TreeMap使用O(log n)查找时间,但内存更高效,不需要聪明的散列函数.但是,如果您正在使用String或Integer键,则无需担心设计散列函数,并且恒定时间查找将是一个巨大的改进.此外,TreeMap/的另一个优点TreeSet是排序顺序,你说你不关心; 用HashMap.

如果列表的唯一目的是检查唯一的帐号,那么我上面所说的一切仍然是正确的,但正如你在问题中所述,你应该使用a HashSet<String>而不是a HashMap.性能建议和构造函数参数仍然适用.

进一步阅读:HashSet和TreeSet性能测试

Answer 2

当我们尝试使用适当的初始化参数在 HashMap 中存储 5000 万条记录时，插入速度开始变慢，尤其是在 3500 万条记录之后。更改为 TreeMap 可以提供稳定的插入和检索性能。

观察：对于大型输入集，TreeMap 将提供比 HashMap 更好的性能。对于较小的集合，HashMap 当然会提供更好的性能。