最快的方式来查找以特定字符开头的String集合中的字符串 [英] Fastest way to find Strings in String collection that begin with certain chars

问题描述

我有一个大集合的字符串。我想要能够找到以Foo开头的字符串或以Bar结尾的字符串。什么是最好的集合类型，以获得最快的结果？ （我使用Java）

我知道一个HashSet对于完全匹配来说是非常快的，但是对于部分匹配我不会觉得。所以，我可以使用而不是只是循环通过一个列表？我应该查看LinkedList或类似类型吗？是否有为此类查询优化的任何集合类型？

解决方案

此问题的最佳集合类型是 SortedSet 。您实际上需要其中两个：

1. 以正常顺序排列的字词。



$ b

一旦这些 SortedSet 已创建，您就可以使用方法 subSet 找到您要查找的内容。例如：




1. 以Foo p>
   
   

     forwardSortedSet.subSet（Foo，Fop）; 
     




2. 以Bar结尾的词：

     backwardSortedSet.subSet（raB，raC）; 
     




最后一个搜索字符是获取整个范围。 从子集中排除，因此没有问题。





在标准Java库中实现 SortedSet 的两个具体类中，使用 TreeSet 。另一个（ ConcurrentSkipListSet ）面向并发程序，因此没有针对这种情况进行优化。




I have a large collection of Strings. I want to be able to find the Strings that begin with "Foo" or the Strings that end with "Bar". What would be the best Collection type to get the fastest results? (I am using Java)

I know that a HashSet is very fast for complete matches, but not for partial matches I would think? So, what could I use instead of just looping through a List? Should I look into LinkedList's or similar types? Are there any Collection Types that are optimized for this kind of queries?

解决方案

The best collection type for this problem is SortedSet. You would need two of them in fact:

1. Words in regular order.
2. Words with their characters inverted.

Once these SortedSets have been created, you can use method subSet to find what you are looking for. For example:

1. Words starting with "Foo":

    forwardSortedSet.subSet("Foo","Fop");
   

2. Words ending with "Bar":

    backwardSortedSet.subSet("raB","raC");
   

The reason we are "adding" 1 to the last search character is to obtain the whole range. The "ending" word is excluded from the subSet, so there is no problem.

EDIT: Of the two concrete classes that implement SortedSet in the standard Java library, use TreeSet. The other (ConcurrentSkipListSet) is oriented to concurrent programs and thus not optimized for this situation.

这篇关于最快的方式来查找以特定字符开头的String集合中的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！