logo标签列表

如何快速检查 List<String> 是否包含唯一的字符串

javastringperformancelistcontains
71

基本上，我有大约1,000,000个字符串，对于每个请求，我都需要检查一个字符串是否属于列表。

我担心性能问题，那么什么是最好的方法？ArrayList？哈希表？

5
一个好的练习是尝试使用不同的列表/集合/映射，然后通过阅读Java文档来弄清楚为什么会得到不同的时间。 :) - willcodejavaforfood
3
为了确保你的操作正确，学会熟练使用性能分析器。最简单易行的是JDK中自带的jvisualvm。 - Thorbjørn Ravn Andersen
10个回答
105
你最好使用一个 HashSet 并通过 contains() 方法检查字符串是否存在于集合中。 HashSet 通过使用 Object 方法 hashCode() 和 equals() 实现快速访问。 HashSet 的 Javadoc 表明：

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

HashSet 在哈希桶中存储对象，也就是说，hashCode 方法返回的值将确定对象存储在哪个桶中。这样，HashSet 需要通过 equals() 方法执行的相等性检查数量仅限于同一哈希桶中的其他对象。

要有效地使用 HashSets 和 HashMaps，必须遵守 javadoc 中 概述的 equals 和 hashCode 协定。 在 java.lang.String 的情况下，这些方法已经实现了此功能。

1
还有什么？它的添加和包含操作都是O(1)。 - Andreas Dolk
感谢@Andreas_D，我添加了Javadoc中的引用，它说明它具有恒定的时间性能。 - krock
14
当一百万个字符串无法再适应主存储器时，就会变得有趣起来。 - Thorbjørn Ravn Andersen
12

通常情况下，HashSet会给您更好的性能，因为它不必像ArrayList那样查找每个元素并进行比较，但通常最多只比较少量元素，其中哈希码相等。

然而，对于1M个字符串，HashSet的性能可能仍然不够优化。很多缓存未命中将减慢搜索速度。如果所有字符串的出现频率相等，那么这是不可避免的。但是，如果某些字符串比其他字符串更常被请求，那么您可以将常见字符串放入一个小的HashSet中，并在检查大的集合之前先检查该小的集合。小型哈希集的大小应该适合缓存（例如最多几百K）。对小型哈希集的命中将非常快，而对大型哈希集的命中则受到内存带宽限制。

尽管我想到由于字符串是单独分配的，因此特定哈希映射中有多少个字符串总数可能并不特别相关，因为搜索只会触及其中的一小部分。更重要的可能是字符串本身中char数组的实际分配模式，而Java程序员无论如何都无法控制（这是一件好事）。 - Lawrence Dol
@Software Monkey - 目的是通过将最常搜索的字符串放入自己的映射中，使该映射具有高度的命中率。一个包含常用字符串的较小哈希映射将比一个较大的映射具有更高的缓存命中率，因为每个缓存行在映射后备数组中对应于多个经常使用的字符串。当然，正如您所说，这并不能解决字符串本身的分配问题。如果这是一个问题，那么首先分配最常见的字符串可能会更好地利用缓存，因为VM可以从堆的同一区域分配。 - mdma
9

在进一步深入之前，请考虑这个问题：你为什么担心性能？这个检查调用的频率有多高？

至于可能的解决方案：

如果列表已经排序，则可以使用java.util.Collections.binarySearch，其提供与java.util.TreeSet相同的性能特征。否则，您可以使用具有O（1）性能特征的java.util.HashSet。请注意，对于尚未计算哈希值的字符串计算哈希码是一项O（m）操作，其中m = string.length()。还要记住，散列表只在达到给定负载因子时才有效，即散列表将使用比普通列表更多的内存。 HashSet使用的默认负载因子为0.75，这意味着内部具有1.3e6个条目的数组的HashSet将用于1e6个对象。如果HashSet不适用于您（例如，因为存在大量哈希冲突，因为内存紧张或因为存在大量插入），则考虑使用Trie。Trie中的查找的最坏复杂度为O（m），其中m = string.length()。 Trie还具有一些额外的好处，可能对您有用：例如，它可以为您提供搜索字符串的最接近匹配。但请记住，最好的代码是没有代码，因此仅当收益超过成本时才自己编写Trie实现。如果您想要更复杂的查询（例如，匹配子字符串或正则表达式），请考虑使用数据库。
10
他担心性能问题，因为他（a）有一个巨大的数据集，和（b）任何一个像样的程序员都应该考虑算法或数据结构的性能特征是否适合完成任务。 - Lawrence Dol
5

我建议使用Set，在大多数情况下HashSet就可以了。

1
krock的回答在推动OP寻找最优解方面略胜一筹：TreeSet的性能为O(log2(N))，而HashSet理想情况下为O(1)。 - Carl Smotricz
@Carl，假设equals和hashCode（）都是O（1），即不考虑字符串长度。 - Thorbjørn Ravn Andersen
2
在这里进行了测试，以下是我的结果。
private static final int TEST_CYCLES = 4000;
private static final long RAND_ELEMENT_COUNT = 1000000l;
private static final int RAND_STR_LEN = 20;
//Mean time
/*
Array list:18.55425
Array list not contains:17.113
Hash set:5.0E-4
Hash set not contains:7.5E-4
*/

我相信数据说话。哈希集合的查找时间快得多。

2
也许在你的情况下不需要，但我认为值得一提的是有一些高效的概率算法。例如布隆过滤器。
2

有这么多的字符串，我立刻想到一个Trie。它对于字符集较小（如字母）和/或许多字符串起始位置重叠时运作更加高效。

1

如果你有大量的字符串需要处理，最好的选择是使用数据库。可以考虑使用MySQL。

1
一般来说，我同意你的观点，但他担心查找性能 - 这不会增加很多开销吗？ - Rup
1
网络延迟会增加，但你可以充分利用SQL的强大功能。另一个考虑因素是内存 - 一百万个32个字符的字符串意味着大约64MB的RAM。这是经典的CPU与内存之间的权衡。我建议进行基准测试来观察效果。 - duffymo
1
@Rup：完全正确。而且还有很多出错的机会。如果数据适合存储在内存中（而且必须这样，因为它们已经塞进去了），那么应该在内存中查找。 - Carl Smotricz
2
@duffymo：对于存在性的简单测试，无论你在数据库服务器上做什么，都无法接近哈希表中的contains()函数的性能。 - Carl Smotricz
@Carl Smotricz&Rup：我不知道这个。所以感谢你们的评论。 - oopbase
显示剩余6条评论
0
有时候，您想要检查一个对象是否在列表/集合中，同时您还希望列表/集合是有序的。如果您还想轻松地检索对象而不使用枚举或迭代器，您可以考虑同时使用 ArrayList<String> 和 HashMap<String, Integer>。列表由映射支持。
最近我做的一些工作示例：
public class NodeKey<K> implements Serializable, Cloneable{
private static final long serialVersionUID = -634779076519943311L;

private NodeKey<K> parent;
private List<K> children = new ArrayList<K>();
private Map<K, Integer> childrenToListMap = new HashMap<K, Integer>();

public NodeKey() {}

public NodeKey(Collection<? extends K> c){
    List<K> childHierarchy = new ArrayList<K>(c);
    K childLevel0 = childHierarchy.remove(0);

    if(!childrenToListMap.containsKey(childLevel0)){
        children.add(childLevel0);
        childrenToListMap.put(childLevel0, children.size()-1);
    }

    ...

在这种情况下，参数K将是一个字符串String。映射（childrenToMapList）将插入到列表（children）中的字符串Strings作为键存储，而映射值则是列表中的索引位置。
列表和映射的原因是，您可以检索列表的索引值，而无需对HashSet 进行迭代。
0

不仅适用于字符串，您可以在任何需要唯一项的情况下使用Set。

如果项目的类型是基本类型或包装器类型，则可能不需要关心。但如果它是一个类，则必须重写两个方法：

  1. hashCode()
  2. equals()
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接