Fast string comparison with list

Question

I need a fast method to determine if a given string is in a list of strings.

The list of strings is not known until runtime but thereafter it will not change.

I could simply have a List<String> called strings and then do:

if (strings.Contains(item))

However this will perform poorly if there are many strings in the list.

I could also use a HashSet<String>, but this would necessitate calling GetHashCode on every incoming string as well as Equals, which would be a waste if there are e.g. only 3 strings in the list. Did I mention this needs to be fast?

I could when setting up, decide to use a List or a HashSet depending on the number of strings (e.g. use List for less than 10 strings, HashSet otherwise), rather like the logic in HybridDictionary.

As the strings are unicode, a standard Trie structure will not work, although a Radix tree/Patricia trie might. Are there any good C# implementations out there with benchmarks?

Some have mentioned bypassing String's GetHashCode and using a faster performing hash function. Are there any benchmarks out there?

Using LINQ expressions to essentially create an optimised switch statement is a novel approach which looks very interesting.

What else would work? Setup cost is not important, just the search speed.

If it matters, the incoming string values will rarely appear in the list.

Answer 1

You could use a trie to hold the list of strings; tries were designed for fast re*trie*val. Here's one example of implementing a trie in C#.

Update: Powerpoint presentation on folded tries for Unicode and Ifo on implementation of a folded trie for Unicode (not C#)

Answer 2

Have you considered using the HashSet class (in .NET 3) instead?

Answer 3

Check out these:

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Answer 4

Re your "when the list is small" concern; if you don't mind using non-generic collections, System.Collections.Specialized.HybridDictionary does something like this; it encapsulates a System.Collections.Specialized.ListDictionary when small, or a System.Collections.Hashtable when it gets bigger (>10). Worth a look?

---

Otherwise; you could perhaps use HashSet<T> with a custom comparer? Then you can choose how expensive GetHashCode() is...

using System;
using System.Collections.Generic;

class CustomStringComparer : IEqualityComparer<string> {
    public bool Equals(string x, string y) {
        return string.Equals(x, y);
    }
    public int GetHashCode(string s) {
        return string.IsNullOrEmpty(s) ? 0 :
            s.Length + 273133 * (int)s[0];
    }
    private CustomStringComparer() { }
    public static readonly CustomStringComparer Default
        = new CustomStringComparer();
}
static class Program {
    static void Main() {
        HashSet<string> set = new HashSet<string>(
            new string[] { "abc", "def", "ghi" }, CustomStringComparer.Default);
        Console.WriteLine(set.Contains("abc"));
        Console.WriteLine(set.Contains("abcde"));
    }
}

Answer 5

Perhaps the HybridDictionary is a better option here. Its internal use is dependent on how many items are in the collection.

Answer 6

As an aside, if memory serves, when a String is constructed, its HashValue is precomputed and stored with the String as an optimization for this type of use case. If you're using a character array or StringBuilder, this obviously doesn't apply, but for an immutable String it should.

EDIT: I am incorrect... Java does cache a String's HashCode, C# does not.

Answer 7

I ended up doing this:

private static bool Contains(List<string> list, string value)
{
    bool contains = null != list.Find(str => str.ToLower().Equals(value.ToLower()));

    return contains;
}

I'm guessing you could create an extension method for List<string>, but this was sufficient for my needs.

Answer 8

You could use string interning to do this very quickly. When building the list, you have to store your required string's interned format (the result of string.Intern()). Then, you need to compare against an interned string with object.ReferenceEquals - since interned strings have the same reference.

List<string> BuildList() {
    List<string> result;
    foreach (string str from StringSource())
         result.Add(str.Intern());
    return result;
}

bool CheckList(List<string> list, string stringToFind) { // list must be interned for this to work!
    return list.Find(str => object.ReferenceEquals(str, stringToFind)) != null;
}

This will result in a four-byte comparison for each list, and one pass over the original string. The intern pool of strings is built specifically for quick string comparison and finding if one already exists, so the intern operation should be quite fast.