В чем сложность поиска HashSet <T>(IEqualityComparer <T>)?

Question

В C # .NET мне нравится использовать HashSets из-за предполагаемой сложности времени O (1) для поиска.Если у меня есть большой набор данных, которые будут запрашиваться, я часто предпочитаю использовать HashSet для List, так как он имеет сложность по времени.

Что меня смущает, так это конструктор для HashSet, который принимаетIEqualityComparer в качестве аргумента:

http://msdn.microsoft.com/en-us/library/bb359100.aspx

В приведенной выше ссылке примечания отмечают, что «конструктор является операцией O (1)», но если это так, то яЛюбопытно, если поиск по-прежнему O (1).

В частности, мне кажется, что, если бы мне пришлось написать Comparer для передачи в конструктор HashSet, всякий раз, когда я выполняю поиск, Comparerкод должен быть выполнен на каждом ключе, чтобы проверить, было ли совпадение.Это будет не O (1), а O (n).

Создает ли реализация внутренне таблицу соответствия при добавлении элементов в коллекцию?

В общем, как я могу определитьинформация о сложности .NET структур данных?

Answer 1

A HashSet работает посредством хэширования (через IEqualityComparer.GetHashCode) объектов, которые вы вставляете, и выбрасывает объекты в сегменты в соответствии с хэшем. Сами сегменты хранятся в массиве, следовательно, часть O (1).

Например (это не обязательно точно так, как работает реализация C #, это просто дает представление), он берет первый символ хэша и выбрасывает все с хешем, начинающимся с 1, в сегмент 1. Хэш 2, фрагмент 2 , и так далее. Внутри этого блока находится еще один массив блоков, которые делятся на второй символ в хэше. И так для каждого символа в хэше ....

Теперь, когда вы ищите что-то, оно хэширует его и перепрыгивает через соответствующие корзины. Он должен выполнить несколько поисков в массиве (по одному для каждого символа в хэше), но не увеличивается как функция от N, количества добавленных вами объектов, следовательно, рейтинга O (1).

К вашему другому вопросу, здесь есть запись в блоге со сложностью операций с несколькими коллекциями: http://c -sharp-snippets.blogspot.com / 2010/03 / runtime-сложности-of-net -generic.html

Answer 2

если бы я должен был написать Comparer для передачи в конструктор HashSet, всякий раз, когда я выполняю поиск, код Comparer должен выполняться на каждом ключе, чтобы проверить, было ли совпадение.Это будет не O (1), а O (n).

Давайте назовем искомое значение для значения «query».

Можете ли вы объяснить, почему вы считаете, что компаратор должен выполняться для каждого ключа, чтобы проверить, соответствует ли он запросу?

Это убеждение ложно.(Если, конечно, хеш-код, предоставленный компаратором, одинаков для каждого ключа!) Алгоритм поиска выполняет компаратор равенства для каждого ключа , чей хеш-код соответствует хеш-коду запроса, по модулю количества сегментов вхэш-таблица.Вот как хэш-таблицы получают время поиска O (1).

Внутренне ли конструирует внутреннюю таблицу поиска при добавлении элементов в коллекцию?

Да.

В общем, как я могу получить информацию о сложности структур данных .NET?

Прочитать документацию.

Answer 3

Lookup по-прежнему O (1), если вы передаете IEqualityComparer.Набор хэшей все еще использует ту же логику, как если бы вы не передавали IEqualityComparer;он просто использует реализации IEqualityComparer'а GetHashCode и Equals вместо методов экземпляра System.Object (или переопределений, предоставляемых рассматриваемым объектом).

Answer 4

Это зависит от качества хеш-функции (GetHashCode()), которую обеспечивает ваша реализация IEqualityComparer. Идеальная хеш-функция должна обеспечивать хорошо распределенный случайный набор хеш-кодов. Эти хэш-коды будут использоваться в качестве индекса, который позволяет сопоставить ключ со значением, поэтому поиск значения по ключу становится более эффективным, особенно когда ключ является сложным объектом / структурой.

код сравнения должен быть выполнен на каждом ключе для проверки посмотрим, был ли матч. Это будет не O (1), а O (n).

Это не то, как работает хеш-таблица, это какой-то простой поиск грубой силы. В случае хеш-таблицы у вас будет более интеллектуальный подход, который использует поиск по индексу (хэш-код).