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

Question

Всегда ли время поиска для хеш-таблицы или словаря равно O (1), если в нем есть уникальный хэш-код?

Если HashTable имеет 100 миллионов строк, то потребуется ли столько же времени для поиска, чем то, что имеет 1 строку?

Answer 1

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

int bucket = key.GetHashCode() % totalNumberOfBuckets;

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

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

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

Answer 2

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 в обоих случаях.Так что, похоже, ответ будет Да.[Понизился, поэтому я объясню лучше]

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

Answer 3

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

Answer 4

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