ConcurrentDictionary on large numbers

Question

Мне интересно узнать, почему метод ConcurrentDictionarygetOrAdd замедляет работу по мере увеличения числа записей.

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

Любое предложение?

Answer 1

Это из-за столкновений. ConcurrentDictionary ведет список ведер, а результат возвращается Метод GetHashCode определяет, в каком ковре будет помещена запись. В идеале каждая запись должна быть в отдельном ковше. Однако на практике это невозможно. Если GetHashCode возвращает то же значение для двух разных ключей, появляется столкновение, и все больше записей помещается в одно и то же ведро.

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

Кстати, стандарт Словарь реализован по-разному, но будет вести себя аналогичным образом. Хорошее описание внутренних структур обеих структур данных можно найти here