StepOne

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



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