Ben*_*Ben 66 java string performance contains list
基本上我有大约1,000,000个字符串,对于每个请求,我必须检查字符串是否属于列表.
我担心性能,所以最好的方法是什么？ArrayList？哈希？
kro*_*ock 96
最好的办法是使用a HashSet并通过contains()方法检查集合中是否存在字符串.HashSets是通过使用Object方法hashCode()和快速访问而构建的equals().HashSet状态的Javadoc :
此类为基本操作(添加,删除,包含和大小)提供恒定的时间性能,
HashSet 将对象存储在散列桶中,也就是说hashCode方法返回的值将决定对象存储在哪个存储桶中.这样,HashSet通过该equals()方法执行的相等性检查量减少到只有其他对象相同的哈希桶.
要有效地使用HashSets和HashMaps,您必须符合javadoc中概述的equals和hashCode合同.在这些方法的情况下已经实现了这样做.java.lang.String
mdm*_*dma 11
通常,HashSet会为您提供更好的性能,因为它不必查看每个元素并进行比较,就像ArrayList那样,但通常最多比较几个元素,其中哈希码是相等的.
但是,对于1M字符串,hashSet的性能可能仍然不是最佳的.大量缓存未命中会降低搜索集的速度.如果所有字符串都同样可能,那么这是不可避免的.但是,如果某些字符串比其他字符串更常被请求,那么您可以将公共字符串放入一个小的hashSet中,并在检查较大的集合之前先检查它.应该调整小哈希集的大小以适应缓存(例如,最多几百K).然后,对小散列集的命中将非常快,而对较大散列集的命中在由内存带宽限制的速度下进行.
在进一步讨论之前,请考虑一下:为什么你担心性能？这张支票多久拨打一次？
至于可能的解决方案:
如果列表已经排序,那么您可以使用java.util.Collections.binarySearch哪个提供与a相同的性能特征java.util.TreeSet.
否则,您可以使用java.util.HashSet它作为O(1)的性能特征.请注意,计算尚未计算的字符串的哈希码是m(m)的O(m)运算string.length().还要记住,哈希表只有在达到给定的加载因子之后才能正常工作,即哈希表将使用比普通列表更多的内存.HashSet使用的默认加载因子是.75,这意味着1e6对象的HashSet内部将使用具有1.3e6条目的数组.
如果HashSet不适合你(例如因为存在大量的哈希冲突,因为内存很紧或因为有很多插入),那么考虑使用Trie.Trie中的查找具有O(m)的最坏情况复杂度,其中m = string.length().Trie还有一些可能对您有用的额外好处:例如,它可以为您提供最适合搜索字符串的功能.但请记住,最好的代码不是代码,所以如果收益超过成本,那么只能推出自己的Trie实现.
如果您想要更复杂的查询,请考虑使用数据库,例如匹配子字符串或正则表达式.