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

Ответ 1

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

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

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

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

Ответ 2

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

Позвольте вызвать значение, которое вы ищете для значения запроса.

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

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

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

Да.

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

На самом деле время поиска HashSet<T> не всегда равно O (1).

Как уже упоминали другие, HashSet использует IEqualityComparer<T>.GetHashCode().
Теперь рассмотрим структуру или объект, который всегда возвращает один и тот же хэш-код x.

Если вы добавите n элементов в ваш HashSet, в нем будет n элементов с одинаковым хешем (если объекты не равны).
Таким образом, если вам нужно проверить, существует ли элемент с хеш-кодом x в вашем HashSet, он запустит проверки на равенство для всех объектов с хеш-кодом x, чтобы проверить, содержит ли HashSet элемент