Словарь и метод Add. Помогите!

[Dima2607]

Читал исходный код Dictionary, нашел такую строку

int targetBucket = hashCode % buckets.Length

У меня есть словарь вместимостью 40000, с типом ключа - int. Hash от int это само число. Пробовал добавлять в словарь 40000 элементов с ключами, такими, чтобы остаток от деления был одинаков. Чтобы было больше коллизий. Однако словарь все-равно работает быстро. Я что-то не правильно понял? Когда Add работает за O(n)?
Когда операция словаря Add работает за O(n), если предположить, что он имеет нужную емкость, то есть никогда не расширяется при добавлении?

[pu4koff]

Коллизии больше влияют на получение элемента, а не на его добавление.

[Selestis]

На что делите, чтобы получить

Пробовал добавлять в словарь 40000 элементов с ключами, такими, чтобы остаток от деления был одинаков

?
Предположу, что 40000. А это неверно, потому что в качестве bucket.length используется не capacity(=40000), а простое число сверху (но походу не ближайшее. какое именно - надо смотреть в исходники). В данном случае 43627. Попробуйте делить на него и увидите разницу.
P.S.
Результат сравнения вот такого кода

            for (var i = 0; i < 30000; ++i)
            {
                dict.Add(i * stride, i);
            }

на моей машине:
stride=1: 0мс
stride=43627: 1320мс

То есть всё как и должно быть.