221

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?

Servy
  • 202,030
  • 26
  • 332
  • 449
John Bustos
  • 19,036
  • 17
  • 89
  • 151
  • 1
    one may also want to see [what-is-the-point-of-lookuptkey-telement](http://stackoverflow.com/questions/1403493/what-is-the-point-of-lookuptkey-telement) – nawfal May 22 '14 at 14:41

6 Answers6

330

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.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 3
    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. – nawfal May 22 '14 at 14:40
  • @nawfal - that's exactly what Lookups are for. From [msdn](https://msdn.microsoft.com/en-us/library/vstudio/bb460184(v=vs.100).aspx): "You can create an instance of a Lookup by calling ToLookup on an object that implements IEnumerable." – Niall Connaughton Aug 26 '15 at 06:06
  • The only way to remove an item from a lookup is to recreate it less the removed item. Lookup does not have a delete option, where as a dictionary has a remove method. – Golden Lion Nov 15 '22 at 16:34
  • 1
    @GoldenLion: That's covered by "Lookup is immutable" surely. – Jon Skeet Nov 15 '22 at 16:36
  • @GoldenLion: No, that's not the case. `Dictionary` was introduced in .NET 2.0; `Lookup` was introduced in .NET 3.5 as part of LINQ. You should use whichever meets your needs more appropriately though. – Jon Skeet Nov 15 '22 at 16:40
  • suppose you have a billion rows of data would the Lookup work because it is iqueryable and the dictionary fail because of memory limitations – Golden Lion Nov 15 '22 at 18:12
  • @GoldenLion: Please don't start trying to use comment threads to ask additional questions. Post a new question (with research and effort into making it very clear and concrete) if you want to know. – Jon Skeet Nov 15 '22 at 18:25
106

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.

Mladen Mihajlovic
  • 6,095
  • 7
  • 40
  • 55
  • 66
    Check the question: it is about the difference between a Lookup and a Dictionary>, so that difference is kind of explicit already. – Martao Jun 21 '14 at 18:25
  • 27
    @Martao some people find this question when googling to understand the difference between lookups and dictionaries. This answer is really useful. – jakubiszon Jun 09 '20 at 22:07
  • @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())`. – OfirD Feb 18 '21 at 16:22
  • @OfirD Yeah in that sense they are the same. But as the other answers state, there are other differences. – Mladen Mihajlovic Feb 19 '21 at 23:44
39

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.

James Michael Hare
  • 37,767
  • 9
  • 73
  • 83
15

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.

Noble_Bright_Life
  • 569
  • 3
  • 9
  • 16
13

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.

Servy
  • 202,030
  • 26
  • 332
  • 449
  • 1
    @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. – Servy Nov 13 '12 at 14:36
  • 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! – John Bustos Nov 13 '12 at 14:41
  • 2
    @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. – Servy Nov 13 '12 at 14:58
  • 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!! – John Bustos Nov 13 '12 at 15:00
  • Under the covers do you know if Lookup uses hashbuckets for the key? – paparazzo Nov 13 '12 at 15:08
  • @Blam I'm reasonably certain it does, but it's likely not *exactly* the same, just a similar general algorithm. – Servy Nov 13 '12 at 15:11
  • 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. – Dave Black Feb 25 '22 at 16:55
9

When exception is not a option, go for Lookup

If you are trying to get a structure as efficient as a Dictionary but you dont know for sure there is no duplicate key in input, Lookup is safer.

As mentioned in another answer, it also supports null keys, and returns always a valid result when queried with arbitrary data, so it appears as more resilient to unknown input (less prone than Dictionary to raise exceptions).

And it is especially true if you compare it to the System.Linq.Enumerable.ToDictionary function :

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

The alternative would be to write your own duplicate key management code inside of a foreach loop.

Performance considerations, Dictionary: a clear winner

If you don't need a list and you are going to manage a huge number of items, Dictionary (or even your own custom tailored structure) would be more efficient:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

As Lookup has to maintain a list of items for each key, it is slower than Dictionary (around 3x slower for huge number of items)

Lookup speed: Creation: 00:00:01.5760444

Dictionary speed: Creation: 00:00:00.4418833

Community
  • 1
  • 1
Fab
  • 14,327
  • 5
  • 49
  • 68
  • 4
    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. – PM Extra Jun 09 '21 at 18:23
  • 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. – GreatBittern Sep 24 '21 at 05:58
  • 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. – Mr.Z Apr 27 '22 at 23:17