Dictionary vs Lookup

В коммерческой практике часто встречается задача преобразовать некий список в словарь по определённому ключу, чтобы получать элементы коллекции за константное время O(1).

Допустим, у нас есть некоторые сообщения, и требуется возможность выбирать нужное сообщение по отправителю:

record Message(string Sender, string Content);

List<Message> messages = [
    new Message(Sender: "Alex", Content: "abc"),
    new Message(Sender: "Bob", Content: "123"),
    new Message(Sender: "Jim", Content: "=-+")
];

С этим конечно справится метод LINQ ToDictionary:

var messagesBySender = messages
    .ToDictionary(x => x.Sender, x => x);

Однако, если в коллекции появится несколько сообщений с одним отправителем:

List<Message> messages = [
    new Message(Sender: "Alex", Content: "abc"),
    // ...
    new Message(Sender: "Alex", Content: "xyz")
];

То мы получим необработанное исключение при выполнении программы:

System.ArgumentException: An item with the same key has already been added. Key: Alex

Как этого избежать? Использовать метод ToLookup, который даже не потребует селектора значения:

var messagesBySender = messages
    .ToLookup(x => x.Sender);

В чём вообще разница между этими структурами данных?

Lookup

🔠 Работает за O(1), но возвращает IEnumerable<T>, поскольку одному ключу соответствует несколько значений

🔠 Если записи по ключу не существует, то возвращает пустую коллекцию

🔠 Относится к неизменяемым (immutable) структурам данных

Dictionary

🔠 Работает за O(1), возвращая единственный элемент, соответствующий ключу

🔠 Если записи по ключу не существует, то кидает KeyNotFoundException

🔠 Позволяет обновлять своё состояние