Is It a Bad Practice to Use Dictionary with Dummy Value

Question

Let's say I have two collections of items, and I want to find their intersection.

Since these are just values, not key-value pairs, one would normally use a List and not a Dictionary.

However, finding the intersection of two lists requires a nested loop, hence O(n^2) complexity whereas with a Dictionary the time required is O(n).

If we're dealing with large number of items, obviously we would try to avoid O(n^2) so the answer is simple. My question is more about cases where the number of items are small, and unlikely to grow.

Is it considered a bad practice to use a Dictionary with:

• Key = ItemType
• Value = {Dummy}

just for constant look-up capability even though the performance is not a concern? The disadvantages I can think of are:

1. Using a more complicated data structure than necessary.
2. Confusing for the reader since the value is dummy.

Answer 1

In nearly every case you should favor readability and maintainability over performance, particularly when in this case unless your collections are massive the difference is probably trivial.

As a result, unless you can prove that there is a significant performance issue by using an intersection of lists, you will have introduced a large maintainability issue with very little gained.

Finally, consider that if using a dictionary with dummy values, you've traded memory for cpu/time. That may not matter in some cases and may be a deal breaker in others.

At the end of the day, this feels like premature optimization and should probably be avoided. As mentioned by others in the comments, other options such as HashSet<T> could meet your performance goals without writing obfuscated code AND it would utilize less memory.

Answer 2

The HashSet<T> class is functionally like a Dictionary<T> with dummy values. It's also design for just these kind of set operations:

var hashset = new HashSet(myList1);    // this is O(n)
hashset.IntersectWith(myList2);        // this is O(n+m)

https://msdn.microsoft.com/en-us/library/bb293080(v=vs.110).aspx

But as in @DavidL's answer, it really might not be worth the trouble if your collections are relatively small.