Testing if a value is contained within a Dictionary<TKey, List<TValue>>

Question

I need to determine if any of the Lists contained in the Dictionary contain the specified value. I'm new to LINQ, so is the following the correct way to achieve this?

Dictionary lotsOfStuff = new Dictionary<string, List<string>>();
string searchString;

// populate lotsOfStuff and searchString...

// detemine if any of the values of lotsOfStuff contain searchString
bool existsInDictionary = lotsOfStuff.Values.Any(values => values.Contains(searchString));

And if the above will work, is there any way to make it more correct or more optimal/concise?

Thanks and Happy New Year! :)

Answer 1

This code works and is about as efficient as it can be. Because you are searching values there is no index/hash to guide the search. Hence you must search all objects to determine if the value does or does not exist.

Answer 2

Your code will work, and is the best way to do it, assuming that you want a case-sensitive match.

If you want a case-insensitive match, pass a StringComparer, like this:

lotsOfStuff.Values.Any(values => values.Contains(searchString, StringComparer.OrdinalIgnoreCase));

By the way, if you want to get all of the values, you can write

var allValues = lotsOfStuff.Values.SelectMany(v => v);

Answer 3

There's a potential problem with that code. If one of the lists is null (even if the value exists in another list), you'll possibly get a NullReferenceException. To fix, try:

bool existsInDictionary = lotsOfStuff.Values
             .Any(values => values != null && values.Contains(searchString));

Answer 4

Your code will work, but two things immediately come to mind. The first is that it will be slow if the dictionary is large or the value lists are large. The second thing that comes to mind is the fact that you're attempting to do this search at all tells me that you've put the dictionary together backwards. If you've got a dictionary:

"Frob" --> "Foo", "Bar", "Baz"
"Blob" --> "Baz", "ABC"

and the question you're asking is "is ABC in any value list?" then you've built the dictionary backwards. The dictionary you want to be building is

"Foo" --> "Frob"
"Bar" --> "Frob"
"Baz" --> "Frob", "Blob"
"ABC" --> "Blob"

and the question you should be asking is "is ABC a key of the dictionary?" Why are you building the dictionary backwards?

Answer 5

Your linq is fine, here's how I would do it

bool existsInDictionary = lotsOfStuff
  .SelectMany(kvp => kvp.Value)
  .Any(valString => valString == searchString);

---

Eric Lippert had a good suggestion. If this kind of search occurs frequently, you want to use a different datastructure - specifically, something hashed on the values of this dictionary. Here's how I would make and use that.

ILookup<string, string> reverseLookup =
(
  from kvp in lotsOfStuff
  from valString in kvp.Value
  select new {key = valString, value = kvp.Key}
).ToLookup(x => x.key, x => x.value);

bool existsInDictionary = reverseLookup[searchString].Any();