检查 List<String> 是否包含唯一字符串的最快方法

string performance list contains java

2022-08-31 13:59:41

基本上我有大约1，000，000个字符串，对于每个请求，我必须检查字符串是否属于列表。

我担心性能，那么最好的方法是什么？？散列？ArrayList

答案 1

最好的办法是使用哈希集，并通过该方法检查该集中是否存在字符串。HashSet 是为通过使用 Object 方法和 .状态的 Javadoc：contains()hashCode()equals()HashSet

此类为基本操作（添加、删除、包含和大小）提供恒定时间性能，

HashSet 将对象存储在哈希存储桶中，也就是说，该方法返回的值将确定对象存储在哪个存储桶中。这样，必须通过该方法执行的相等性检查量将减少到同一哈希存储桶中的其他对象。hashCodeHashSetequals()

要有效地使用 HashSets 和 HashMaps，您必须遵守 javadoc 中概述的和协定。在这些方法已经实现的情况下，可以做到这一点。equalshashCodejava.lang.String

答案 2

通常，HashSet将为您提供更好的性能，因为它不必像ArrayList那样查看每个元素并进行比较，而是通常最多比较几个元素，其中哈希码相等。

但是，对于 1M 字符串，哈希集的性能可能仍不是最佳。大量缓存未命中会降低搜索集的速度。如果所有字符串的可能性都相同，那么这是不可避免的。但是，如果某些字符串比其他字符串更频繁地被请求，则可以将公共字符串放入一个小的 hashSet 中，并在检查较大的哈希集之前先检查该字符串。小哈希集的大小应适合缓存（例如，最多几百 K）。然后，对小哈希集的命中将非常快，而对较大哈希集的命中将以受内存带宽限制的速度进行。