Difference between Lookup() and Dictionary(Of list())

Question

I'm trying to wrap my head around which data structures are the most efficient and when / where to use which ones.

Now, it could be that I simply just don't understand the structures well enough, but how is an ILookup(of key, ...) different from a Dictionary(of key, list(of ...))?

Also where would I want to use an ILookup and where would it be more efficient in terms of program speed / memory / data accessing, etc?

Solution 1

Two significant differences:

• Lookup is immutable. Yay :) (At least, I believe the concrete Lookup class is immutable, and the ILookup interface doesn't provide any mutating members. There could be other mutable implementations, of course.)
• When you lookup a key which isn't present in a lookup, you get an empty sequence back instead of a KeyNotFoundException. (Hence there's no TryGetValue, AFAICR.)

They're likely to be equivalent in efficiency - the lookup may well use a Dictionary<TKey, GroupingImplementation<TValue>> behind the scenes, for example. Choose between them based on your requirements. Personally I find that the lookup is usually a better fit than a Dictionary<TKey, List<TValue>>, mostly due to the first two points above.

Note that as an implementation detail, the concrete implementation of IGrouping<,> which is used for the values implements IList<TValue>, which means that it's efficient to use with Count(), ElementAt() etc.

Solution 2

Interesting that nobody has stated the actual biggest difference (Taken directly from MSDN):

A Lookup resembles a Dictionary. The difference is that a Dictionary maps keys to single values, whereas a Lookup maps keys to collections of values.

Solution 3

Both a Dictionary<Key, List<Value>> and a Lookup<Key, Value> logically can hold data organized in a similar way and both are of the same order of efficiency. The main difference is a Lookup is immutable: it has no Add() methods and no public constructor (and as Jon mentioned you can query a non-existent key without an exception and have the key as part of the grouping).

As to which do you use, it really depends on how you want to use them. If you are maintaining a map of key to multiple values that is constantly being modified, then a Dictionary<Key, List<Value>> is probably better since it is mutable.

If, however, you have a sequence of data and just want a read-only view of the data organized by key, then a lookup is very easy to construct and will give you a read-only snapshot.

Solution 4

Another difference not mentioned yet is that Lookup() supports null keys:

Lookup class implements the ILookup interface. Lookup is very similar to a dictionary except multiple values are allowed to map to the same key, and null keys are supported.

Solution 5

The primary difference between an ILookup<K,V> and a Dictionary<K, List<V>> is that a dictionary is mutable; you can add or remove keys, and also add or remove items from the list that is looked up. An ILookup is immutable and cannot be modified once created.

The underlying implementation of both mechanisms will be either the same or similar, so their searching speed and memory footprint will be approximately the same.

View more solutions

Comments

[nawfal]

one may also want to see what-is-the-point-of-lookuptkey-telement

[Servy]

@JohnBustos In terms of performance, no. It's purely logical. You can pass references to the structure around an not worry about someone else modifying it out from under you. You can make assumptions on the fact that it's immutable that you couldn't if it were mutable.

[John Bustos]

Thanks, Servy, that is a very good point when you're passing around so many variables ByRef often - At least this one you're sure can't be modified. Thanks!

[Servy]

@JohnBustos Keep in mind that the default method of passing a method parameter is by value, you need to explicitly add byref, and that's something that should be done quite rarely. These data structures are classes, which makes them reference types, so passing the value is the value of the reference, which is why passing it to another method can cause visible changes to the caller.

[John Bustos]

Thanks, Servy, that opens up a whole new can of worms for me in terms of what I've been doing :), but I do understand what you're saying. Thanks!!

[paparazzo]

Under the covers do you know if Lookup uses hashbuckets for the key?

[Servy]

@Blam I'm reasonably certain it does, but it's likely not exactly the same, just a similar general algorithm.

[nawfal]

If a nonexistent key lookup results in an empty sequence rather than an exception, then it very much cant be used as a general purpose collection imo. It's kinda ok in case of an immutable collection which is a byproduct of linq queries.

[Martao]

Check the question: it is about the difference between a Lookup<TKey, TValue> and a Dictionary<TKey, List<TValue>>, so that difference is kind of explicit already.

[Niall Connaughton]

@nawfal - that's exactly what Lookups are for. From msdn: "You can create an instance of a Lookup<TKey, TElement> by calling ToLookup on an object that implements IEnumerable<T>."

[jakubiszon]

@Martao some people find this question when googling to understand the difference between lookups and dictionaries. This answer is really useful.

[OfirD]

@Mladen Mihajlovic, I don't understand that MSDN explanation. Dictionary can also map keys to collections of values, for example by passing a list: grouping.ToDictionary(g => g.Key, g => g.ToList()).

[Germán Martínez]

@OfirD Yeah in that sense they are the same. But as the other answers state, there are other differences.

[PM Extra]

I think this performance comparation is unfair. For same result, list.ToLookup(x => x) is equals to list.GroupBy(x => x).ToDictionary(group => group.Key). Because Lookup can enumerate the duplicate elements as you said at the beginning.

[GreatBittern]

For performance it is more interesting to look at retrieval from an ILookup or Dictionary. Typical use is to create it only once, and do frequent lookups. Therefore I would not care so much about the performance of constructing it.

[Dave Black]

One clarification on @Servy comment on 'default method of passing parameters is by value'.....all variables are passed by value by default in C#. In the case of Value Types you are making a copy. And in the case of Reference Types, you are passing the value of the reference (NOT making a copy). Unless, of course, you add the ref keyword which passes either a reference to the ValueType or a reference to the reference of the ReferenceType.

[Mr.Z]

Thank you for this write-up. I want to note that section "Performance Considerations" may need more clarity because it uncomfortably implies that Lookup performs worse when doing things it was not designed for i.e., mapping 1 key to 1 value.