Add() Производительность: HashSet <T>, словарь <Key,Value> и список <T>

Question

Что такое лучший оптимизированный альтернатива выбрать среди Dictionary<TKey,TValue>, HashSet<T> и List<T> по:

Добавить значения (без дубликатов)

LookUps

Удалить значения.

Я должен избегать добавлений повторяющихся значений в коллекцию я знаю HashSet хорошо, так как он пропускает оный, если дубликат обнаружен, словарь с другой стороны, вызывает исключение, если дубликат найден. Чтобы добавить значение, список должен будет дополнительно проверить ifExists на существующие элементы. Но добавление значений в HashSet<T> без дубликатов, по-видимому, занимает около 1 минуты для записей 10K. Есть ли способ оптимизировать это.

Answer 1

Это прекрасно отвечает на статистику производительности для Dictionary, List и HashSet w.r.t: Добавить, Удалить словари и

http://theburningmonk.com/2011/03/hashset-vs-list-vs-dictionary/

Answer 2

ОК ... С точки зрения теории, все структуры данных, о которых вы говорили (HashSet, словарь и список), имеют асимптотически O (1) временную сложность для добавления элементов. Хеширующие структуры данных также имеют O (1) для удаления. Для списков многое зависит от того, где вы выполняете операцию удаления: если вы удаляете в произвольной позиции «i», то у вас есть сложность O (N) из-за того, что все элементы из i + 1 в конец списка должны сдвигаться влево на одну позицию. Если вы всегда удаляете последний элемент, то это сложность O (1).

Но самое главное, структуры данных, основанные на хэшировании, имеют большой бонус: O (1) сложность поиска. Но это только в теории. На практике, если вы определяете очень плохой хэш-код для своих типов, вы можете отказаться от сложности O (N). Простым примером может быть переопределение функции gethashcode и возвращение константы int. Я подозреваю, что ваша плохая производительность исходит из плохого дизайна GetHashCode.

Еще одна вещь, которую нужно запомнить: словарь и HashSet - это структуры данных, которые будут использоваться в разных сценариях. Вы можете просмотреть словарь как своего рода массив, для которого индексом может быть любой тип, а HashSet - особым списком, который не допускает дублирования.

Answer 3

Когда дело доходит до производительности и хранения уникальных значений, я бы предпочел набор или набор хэшей в зависимости от мое требование. hashSet используется, когда у вас нет пары ключевых значений для входа, и вы все равно не хотите дублировать в своей коллекции. Таким образом, hashset представляет собой коллекцию для хранения уникальных значений без пары ключевых значений. где, когда у меня есть пара ключей и значение, я предпочитаю словарь для хранения уникальных значений.