Какова сложность времени поиска HashSet<T>(IEqualityComparer<T>)?
В 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?
4 ответа
HashSet работает через хеширование (через IEqualityComparer.GetHashCode) объекты, которые вы вставляете, и помещают объекты в сегменты в соответствии с хешем. Сами сегменты хранятся в массиве, следовательно, часть O(1).
Например (это не обязательно точно так, как работает реализация C#, это просто дает представление), он берет первый символ хэша и выбрасывает все с хэшем, начинающимся с 1, в сегмент 1. Хэш 2, сегмент 2 и т. Д. на. Внутри этого блока находится еще один массив блоков, которые делятся на второй символ в хэше. Так что для каждого символа в хэше....
Теперь, когда вы ищите что-то, оно хэширует это и перебирает соответствующие корзины. Он должен выполнить несколько поисков в массиве (по одному для каждого символа в хэше), но не увеличивается как функция от N, количества добавленных вами объектов и, следовательно, рейтинга O(1).
На ваш другой вопрос, вот сообщение в блоге со сложностью ряда операций коллекций: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html
если бы я должен был написать Comparer для передачи в конструктор HashSet, всякий раз, когда я выполняю поиск, код Comparer должен был бы выполняться для каждого ключа, чтобы проверить, было ли совпадение. Это будет не O(1), а O(n).
Давайте назовем значение, которое вы ищете, значением "запроса".
Можете ли вы объяснить, почему вы считаете, что компаратор должен выполняться для каждого ключа, чтобы увидеть, соответствует ли он запросу?
Эта вера ложна. (Если, конечно, хеш-код, предоставленный компаратором, одинаков для каждого ключа!) Алгоритм поиска выполняет компаратор равенства для каждого ключа , хеш-код которого соответствует хеш-коду запроса, по модулю количества сегментов в хеш-таблице. Вот как хеш-таблицы получают O (1) время поиска.
Создает ли реализация внутреннюю таблицу поиска при добавлении элементов в коллекцию?
Да.
В общем, как я могу получить информацию о сложности структур данных.NET?
Прочитайте документацию.
Фактически время поиска HashSet<T> не всегда O(1).
Как уже упоминалось другими, HashSet использует IEqualityComparer<T>.GetHashCode().
Теперь рассмотрим структуру или объект, который всегда возвращает один и тот же хэш-код.x.
Если вы добавите n элементов в свой HashSet, в нем будет n элементов с одинаковым хешем (до тех пор, пока объекты не равны).
Итак, если бы вы должны были проверить, есть ли элемент с хеш-кодомx существует в вашем HashSet, он будет запускать проверки равенства для всех объектов с хеш-кодом x чтобы проверить, содержит ли HashSet элемент
Это зависит от качества хеш-функции (GetHashCode()) ваш IEqualityComparer реализация обеспечивает. Идеальная хеш-функция должна обеспечивать хорошо распределенный случайный набор хеш-кодов. Эти хеш-коды будут использоваться в качестве индекса, который позволяет сопоставить ключ со значением, поэтому поиск значения по ключу становится более эффективным, особенно когда ключ является сложным объектом / структурой.
код Comparer должен быть выполнен на каждом ключе, чтобы проверить, было ли совпадение. Это будет не O(1), а O(n).
Это не то, как работает хеш-таблица, это какой-то простой поиск грубой силы. В случае хеш-таблицы у вас будет более интеллектуальный подход, который использует поиск по индексу (хэш-код).
Поиск по-прежнему O(1), если вы передаете IEqualityComparer. Хэш-набор все еще использует ту же логику, как если бы вы не передавали IEqualityComparer; он просто использует реализации IEqualityComparer'а GetHashCode и Equals вместо методов экземпляра System.Object (или переопределений, предоставляемых рассматриваемым объектом).