Время поиска в HashTable или Dictionary

Нет. Это технически возможно, но было бы крайне редко получить такое же количество накладных расходов. Хеш-таблица разбита на сегменты. Dictionary ‹> (и Hashtable) вычисляют номер ведра для объекта с помощью такого выражения:

int bucket = key.GetHashCode() % totalNumberOfBuckets;

Таким образом, два объекта с разным хеш-кодом могут заканчиваться в одинаковом сегменте. Корзина - это List ‹>, затем индексатор ищет в этом списке ключ, который равен O (n), где n - количество элементов в корзине.

Dictionary ‹> динамически увеличивает значение totalNumberOfBuckets, чтобы поиск по ведру был эффективным. При прокачивании ста миллионов элементов в словаре будут тысячи ведер. Шансы на то, что корзина пуста, когда вы добавляете предмет, будут довольно небольшими. Но если это случайно, то да, на получение предмета уйдет столько же времени.

Объем накладных расходов увеличивается очень медленно по мере увеличения количества элементов. Это называется амортизированной O (1).

Может быть полезно: .NET HashTable Vs Словарь - Может ли словарь работать так же быстро?

Пока нет коллизий с хешами, да.

var dict = new Dictionary<string, string>();
for (int i = 0; i < 100; i++) {
    dict.Add("" + i, "" + i);
}
long start = DateTime.Now.Ticks;

string s = dict["10"];

Console.WriteLine(DateTime.Now.Ticks - start);

for (int i = 100; i < 100000; i++) {
    dict.Add("" + i, "" + i);
}
start = DateTime.Now.Ticks;
s = dict["10000"];
Console.WriteLine(DateTime.Now.Ticks - start);

Это напечатает 0 в обоих случаях. Думаю, ответ будет положительным. [Был изменен, поэтому я объясню получше]

Вроде постоянно. Но это зависит от функции Hash, дающей разный результат для всех ключей. Поскольку нет хэш-функции, которая могла бы это сделать, все сводится к Данным, которые вы вводите в Словарь. Поэтому вам придется проверить свои данные, чтобы убедиться, что они постоянны.