Почему LightInject использует ImmutableHashTree для хранения регистраций вместо простого словаря?

Question

Я смотрю на несколько IoC-содержимого, чтобы выбрать один для использования в моей работе, и, глядя на кодовую базу LightInject, я наткнулся на то, чего не понимаю...

В СервисКонтейнер GetInstance(Type serviceType, string serviceName) метод, он формирует ключ из параметров и вызывает 'Search' для 'namedDelegates':

var key = Tuple.Create(serviceType, serviceName);
var instanceDelegate = namedDelegates.Search(key);

namedDelegates является ImmutableHashTree<TKey, TValue>внутренний класс, который реализует (из своих собственных комментариев):

/// A balanced binary search tree implemented as an AVL tree.

Причина, по которой я смотрю на LightInject, состоит в том, что он показывает отличные результаты в Сравнении производительности IoC Дэниела Пальме, и я озадачен, почему алгоритм двоичного поиска O(log n) предпочтительнее использования словаря O(1) в этом случае?

Кто-нибудь может научить меня здесь?

Answer 1

Не использовал, просто заглянул в исходный код

Моя теория такова, что дубликаты ключей могут использоваться по мере необходимости либо с точки зрения API, либо с точки зрения потребителя. Search(TKey) обрабатывает поиск дубликатов, найденных в дереве, и вот что привело меня к этому.

Другой также, вероятно, для производительности - как вы упомянули в своем вопросе, это выглядит довольно быстро. Их поиск на ImmutableHashTree милостиво решает проблему не найденного значения, а просто возвращает default(TValue),

Кажется, что это будет быстрее, чем следующее с Dictionary<TKey, TValue> которая уже выполняет большую часть той же работы, чтобы найти вашу ценность на основе данного ключа.

if (myDictionary.ContainsKey(myKey))
    return myDictionary[myKey]; // Practically double the work has been done
else
    return default(TValue);

try
{
    return myDictionary[myKey];
}
catch(Exception ex)
{
    // Exceptions can be expensive.
    return default(TValue);
}

Их способ выполняет поиск только один раз и не беспокоится об обнаружении исключений для обработки того факта, что ключа не было.

Опять же, это то, что я собрал, лишь кратко рассмотрев исходный код, и его не следует рассматривать как конкретный.