Как использовать LINQ ToDictionary для оптимизации join

Что проверяют

Знаете ли вы, как устроен Join в LINQ to Objects, и отличаете ли оптимизацию от мифа. Следом спрашивают про дубликаты ключей и про то, как тот же код поведёт себя в EF Core.

Как отвечать

Начните с поправки к постановке. Enumerable.Join не перебирает пары вложенным циклом: он один раз строит хэш-таблицу (Lookup) по внутренней последовательности и проходит внешнюю, то есть уже работает за O(n + m). Поэтому ToDictionary вместо Join на однократном соединении выигрыша почти не даёт.

Проблема, которую словарь действительно решает, выглядит так: orders.Select(o => users.First(u => u.Id == o.UserId)). Это O(n·m), и на десятках тысяч элементов разница в порядки. Замена: var byId = users.ToDictionary(u => u.Id); и дальше byId[o.UserId].

Когда словарь уместнее Join:

• многократные поиски: словарь строится один раз и используется в нескольких местах или в цикле с произвольными обращениями;
• семантика left join: byId.TryGetValue(o.UserId, out var user) честно обрабатывает отсутствие пары, а индексатор бросит KeyNotFoundException;
• один ко многим: нужен ToLookup, он хранит несколько значений на ключ и на отсутствующий ключ возвращает пустую последовательность;
• строковые ключи: передайте компаратор, например StringComparer.OrdinalIgnoreCase, иначе ключи в разном регистре не совпадут;
• справочник только для чтения: с .NET 8 есть ToFrozenDictionary(), такой словарь дольше строится, но быстрее читается.

Помните о материализации: Join ленивый, а ToDictionary выполняет запрос сразу и держит всё в памяти.

Где спотыкаются

Утверждают, что Join работает за O(n·m) и словарь его ускоряет. Интервьюер сразу видит, что вы не замеряли и не знаете реализацию.

Не учитывают дубликаты. ToDictionary на повторяющемся ключе бросает ArgumentException, и код, работавший на тестовых данных, падает на боевых.

Применяют приём к IQueryable в EF Core. context.Users.ToDictionary(...) вытягивает всю таблицу в память, хотя база сделала бы JOIN сама. Если словарь всё же нужен, сначала отфильтруйте: Where(u => ids.Contains(u.Id)).