检查List <String>是否包含唯一string的最快方法
基本上我有大约1,000,000个string，对于每个请求我必须检查一个string是否属于列表。
我担心表演，那么最好的方法是什么？ ArrayList ？ 哈希？
最好的办法是使用HashSet并通过contains()方法检查一个string是否存在于集合中。 HashSets通过使用Object方法hashCode()和equals()来构build，以便快速访问。 Javadoc for HashSet指出：
这个类为基本操作（添加，删除，包含和大小）提供恒定的时间性能，
HashSet 将对象存储在哈希桶中，也就是说，由hashCode方法返回的值将决定一个对象存储在哪个桶中。这样，通过equals()方法检查HashSet必须执行的equals()数量减less到只是在同一个哈希桶中的其他对象。
要有效地使用HashSets和HashMaps，您必须遵守javadoc中概述的equals和hashCode合约。 在java.lang.String的情况下，这些方法已经被实现来做到这一点。
一般来说，HashSet会给你提供更好的性能，因为它不需要像ArrayList那样查看每个元素并进行比较，但通常会比较一些哈希码相等的元素。
但是，对于1Mstring，hashSet的性能可能仍然不是最佳的。 大量的caching未命中会减慢search设置。 如果所有string的可能性相同，那么这是不可避免的。 但是，如果某些string比其他string更频繁请求，那么可以将常用string放入一个小的hashSet中，并在检查较大的set之前先检查它们。 小哈希集的大小应适合高速caching（例如最多几百K）。 对小哈希集的命中将非常快，而对较大哈希集的命中以受存储器带宽限制的速度进行。
在继续之前，请考虑一下：你为什么担心表演？ 多久检查一次？
至于可能的解决scheme：
-
如果列表已经sorting，那么可以使用
java.util.Collections.binarySearch，它提供与java.util.Collections.binarySearch相同的性能特征。 -
否则，您可以使用
java.util.HashSet作为O（1）的性能特征。 请注意，计算尚未计算的string的哈希码是一个O（m）操作，其中m =string.length()。 另外请记住，哈希表只有在达到一个给定的加载因子时才能正常工作，也就是说哈希表将使用比普通列表更多的内存。 HashSet使用的默认加载因子是.75，这意味着内部1e6对象的HashSet将使用具有1.3e6条目的数组。 -
如果HashSet不适合你（例如因为有很多散列冲突，因为内存很紧或者因为有很多插入），所以比考虑使用Trie 。 在Trie中的查找具有O（m）的最坏情况复杂度，其中m =
string.length()。 特里也有一些额外的好处，可能对你有用：例如，它可以给你一个searchstring最适合 。 但请记住，最好的代码是没有代码的，所以如果利益超过成本，那么只能推出自己的Trie实现。 -
如果您想要更复杂的查询，请考虑使用数据库，例如匹配子string或正则expression式。
我会使用一个Set ，在大多数情况下， HashSet是好的。
有了这么多的弦乐，我立即想起了一个Trie 。 它更适合于更有限的一组字符（如字母）和/或许多string重叠的开始。
如果你有这么多的string，最好的机会是使用数据库。 寻找MySQL。
运行这里的练习是我的结果。
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 */
我相信这些数字可以说明一切。 哈希集的查找时间是方式，wayyyy更快。
不仅对于string，您可以使用设置为任何情况下，你需要独特的项目。
如果项目的types是原始的或包装，你可能不在乎。 但是，如果它是一个类，你必须重写两个方法：
- 的hashCode（）
- 等于（）
有时你想检查一个对象是否在列表/集合中，同时你想要列表/集合被sorting。 如果你正在寻找也很容易的检索对象，而不使用枚举或迭代器，你可以考虑同时使用一个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<String>进行迭代。
也许这不是你的情况所必需的，但是我认为知道有一个空间高效的概率algorithm是有用的：
