Как искать хеш-таблицу в .NET?

Question

Я попытался сравнить производительность поиска в хеш-таблице и линейного поиска. Я создал хеш-таблицу, содержащую 1000 элементов, и обнаружил, что время, необходимое для поиска в хэш-таблице, составляет 0,0002 (я использовал DateTime.Now, чтобы узнать системное время до и после поиска и вычел их). У меня были одинаковые 1000 строк в массиве, и я искал одно и то же значение с помощью линейного поиска. И оказалось, что это меньше, чем время поиска хеш-таблицы.

Я думал, что хеш-таблицы быстрее, чем линейный поиск. Как это работает ?

Спасибо

Answer 1

Во-первых, ваш механизм синхронизации не хорош.Если вы хотите протестировать производительность, вы должны использовать таймер с высоким разрешением, например System.Diagnostics.Stopwatch.

Во-вторых, вам нужно найти среднее время поиска по многим поискам, которые случайным и равномернымраспределено по пространству поиска, а не только по времени поиска для одного конкретного элемента.

Answer 2

Ответ можно найти в этой статье:

Обширный анализ структур данных с использованием C # 2.0 ,

в разделе " Класс System.Collections.Hashtable "

Вот (чрезвычайно) краткий обзор:

Добавление в коллекцию (Add(object key, object value)):

1. Получите key и value параметр
2. Применить алгоритм хеширования к параметру key. Это сложная формула, которая использует метод Object.GetHashCode() и дает позицию в индексе между 0 и размером хэша (количество слотов в хэш-таблице (внутренняя структура поиска, используемая System.Collections.HashTable).
3. Вставить объект DictionaryEntry в эту позицию.

Доступ к элементу в коллекции (object this[object key] { set; get; }):

1. Получите параметр key
2. Вычислить позицию в хеш-таблице, используя хеш-алгоритм для параметра key.
3. Возвращает value предмета, хранящегося в этой позиции