Насколько быстро возвращается KeyCollection в Dictionary.Keys?(.СЕТЬ)

Question

IDictionary<TK, TV> определяет метод IDictionary.ContainsKey(in TK) и свойство IDictionary.Keys (типа ICollection). Меня интересует (асимптотическая) сложность этого метода и свойства в Dictionary реализации IDictionary<TK, TV>.

Рассмотрим определения

IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();

и учтите, что мы добавили в словарь dict n уникальных KeyValuePair с.

Какова ожидаемая (асимптотическая) сложность вызова dict.ContainsKey(k)? Я надеюсь, что это в O(1), но я не нашел его в документации Dictionary.ContainsKey.

Какова ожидаемая (асимптотическая) сложность вызова dict.Keys.Contains(k)? Я надеюсь, что это в O(1), но я не нашел его в документации Dictionary.Keys и документации Dictionary.KeyCollection. Если оно в O(1), я не понимаю, почему тип свойства IDictionary.Keys равен ICollection, а не ISet (как, например, в Java).

Answer 1

Поскольку IDictionary<K,V> является только интерфейсом, а не реализацией, то он не дает никаких гарантий производительности.

Для встроенного типа Dictionary<K,V>, ContainsKey метод должен быть O (1):

Этот метод подходит к операции O (1).

Keys.Contains* Метод 1018 * фактически вызывает метод ContainsKey родительского словаря, поэтому он также должен быть O (1):

Этот метод является операцией O (1).

(Обе цитаты взяты из раздела «Замечания» на соответствующих страницах документации.)

Answer 2

первая ссылка , которую вы указали, в примечаниях:

Этот метод приближается к операции O (1).

Кроме того, если вы нажмете Contains метод , вы увидите то же самое в комментариях:

Этот метод является операцией O (1).