Dart - Is there a performance improvement if I search by a Map's key instead of doing singleWhere in a List?

Question

So, for instance, given I have the following class

class Foo{
  String id;
  Foo(this.id);
}

I want to have some sort of collection of Foos, and then be able to find any Foo by its id. I want to compare these two ways of accomplishing this:

With a Map:

var foosMap  = <String, Foo>{"foo1": new Foo("foo1"), "foo2": new Foo("foo2")}; 
var foo2 = foosMap["foo2"];

With a List:

var foosList = <Foo>[new Foo("foo1"), new Foo("foo2")];
var foo2 = foosList.singleWhere((i) => i.id == "foo2");

Is it more convenient in terms of performance doing it the first way (with a Map)? Are there any other considerations to take into account?

Answer 1

It really depends on the number of items you're searching through. If you know big-O notation, retrieving a value from a map is O(1) or constant time, while searching linearly through a list is O(n) or linear time. That means that the lookup time is the same for a map no matter not many elements are in it, but the lookup time for a list grows with the number of elements.

Because of this lot of programmers use hash maps for everything when for very small sets lists are often faster. If you ever look at performance critical code that does lookups, you'll sometimes see special cases to switch to lists instead of maps for small sets. The only way to know if this is a good strategy is to do performance testing.

Speed isn't everything though, and I prefer the clarity of the map syntax in many situations, assuming you have a map already. If you would have to build a map just to perform a lookup, then singleWhere() or firstWhere() are great.