Take the 2-minute tour ×

I have a list of strings and need to find which strings match a given input value. what is the most efficient way (memory vs execution speed) for me to store this list of strings and be able to search through it? The start-up and loading of the list of strings isnt important, but the response time for searching is.

should i be using a List or HashSet or just a basic string[] or something else?

share|improve this question
How "big" is the list of strings? –  Kris Krause Dec 28 '11 at 15:31
Don't forget about the StringCollection class - msdn.microsoft.com/en-us/library/… –  Kris Krause Dec 28 '11 at 15:33
Can any string be a duplicate? Do you need to match entire words/strings or can it be contained within a string? –  Jason Down Dec 28 '11 at 15:33
@KrisKrause StringCollection is heinously slow. It uses an ArrayList under the covers. –  vcsjones Dec 28 '11 at 15:35
@Kris Krause: StringCollection is not fast. –  Jason Dec 28 '11 at 15:36
show 2 more comments

4 Answers

up vote 10 down vote accepted

It depends very much on the nature of the strings and the size of the collection. Depending on characteristics of the collection, and the expected search strings, there are ways to organize things very cleverly so that searching is very fast. You haven't given us that information.

But here's what I'd do. I'd set a reasonable performance requirement. Then I'd try a n-gram index (why? because you said in a comment you need to account for partial matches; a HashSet<string> won't help you here) and I'd profile reasonable inputs that I expect against this solution and see if it meets my performance requirements or not. If it does, I'd accept the solution and move on. If it doesn't, I'd think very carefully about whether or not my performance requirements are reasonable. If they are, I'd start thinking about whether or not there is something special about my inputs and collection that might enable me to use some more clever solutions.

share|improve this answer
A HashSet can't meet his needs for partial matches (and if strings "can be duplicated" this implies that there's some information to distinguish the duplicates, so it'd be a Dictionary anyway, rather than a HashSet) –  Random832 Dec 28 '11 at 16:38
@Random832: His question doesn't say anything about partial matches nor duplicates! –  Jason Dec 28 '11 at 16:38
A followup comment did - in your rush to be the FGITW you didn't stop to ask what was required - the original wording does not come close to implying a problem that a HashSet can solve. A careful reading of "which strings match a given input value" reveals that the plural implies partial matches (only one string can exactly match) –  Random832 Dec 28 '11 at 16:40
@Random832: Rush to what? I have no idea what the acronym means. Regardless, I wasn't rushing to anything. Suggesting that I carefully read a question that wasn't even carefully written (if it took a clarification in a comment later to get some necessary details out of the OP) is, well, silly. Note the title: "C# efficient way to search for string in list of string?" Note the OP himself asked if a HashSet is appropriate. –  Jason Dec 28 '11 at 17:00
It means "fastest gun in the west". If the question didn't provide necessary details, that's what comments are for. "Note the OP himself asked if a HashSet is appropriate" - and the answer was no. And to most people, "search" means text search in e.g. a document, which doesn't generally even have an option for "match whole line only" let alone it being the default –  Random832 Dec 28 '11 at 17:06
add comment

It seems the best way is to build a suffix tree of your input in O(input_len) time then do queries of your patterns in O(pattern_length) time. So if your text is really big compared to your patterns, this will work well.

See Ukkonen's algorithm for building a suffix tree.

If you want inexact matching...see the work of Gonzalo Navarro.

share|improve this answer
tx for de edit. :) –  Cris Stringfellow Dec 28 '11 at 16:01
"just build a 256 or more likely 128 character/byte array for each node in the trie." - the array would be of 256/128 pointers to nodes, not bytes. –  Random832 Dec 28 '11 at 16:33
Or...even more correctly... an array, indexed by the character's ascii (or other charset) code, of object references/pointers Node node* = new Node[128]. Thank you Random832 for your improvement. –  Cris Stringfellow Dec 28 '11 at 16:54
Is this the fastest? or the most memory efficient? I was thinking it's the latter. –  Odnxe Dec 28 '11 at 17:02
Given the need for partial matching, a prefix trie doesn't really help. –  Jason Dec 28 '11 at 17:05
add comment

Use a Dictionary<string>() or an HashSet<string> is probably good for you.

share|improve this answer
+1: that's also the first thing that came to my mind when thinking about optimizing search string in list of string: the first common solution is "indexing", with a dictionary as the most common solution. –  Stephane Rolland Dec 28 '11 at 16:59
@StephaneRolland Yes somethime the simplest is the better, but even the gotafex solution worth a +1 –  Felice Pollano Dec 28 '11 at 17:03
add comment

Dictionary and Hashtable are going to be the fastest at "searching" because it is O(1) speed. There are some downfalls to Dictionaries and Hashtables in that they are not sorted.

Using a Binary search tree you will be able to get O(Log N) searching.

Using an unsorted list you will be O(N) speed for searching.

Using a sorted list you will get O(Log N) searching but keep in mind the list has to be sorted so that adds time to the overall speed.

As for memory use just make sure that you initialize the size of the collection.

So dictionary or hash table are the fastest for retrieval.

Speed classifications from best to worst are O(1) O(log n) O(n) O(n log n) O(n^2) O(2^n)

n being the number of elements.

share|improve this answer
@FelicePollano I don't think you quite have the meaning of O(1) correct. –  Random832 Dec 28 '11 at 16:34
@Random832 it is O(1) in insert. In searching it is O(1) locating the list and then it performs a linear search. What is wrong in order to you ? –  Felice Pollano Dec 28 '11 at 16:50
The fact that the "list" that has to be linearly searched [i.e. the collision chain] is generally short, and not in proportion to the total number of items in the dictionary (provided there are an appropriate number of buckets) means it's still O(1) amortized, unless a large number of items with the same hash code [unlikely unless deliberately constructed this way] are inserted. –  Random832 Dec 28 '11 at 16:53
add comment

Your Answer


