Как может hashset.contains O (1) с этой реализацией?

Question

HashSet. Содержит реализацию в. Net is:

    /// <summary>
    /// Checks if this hashset contains the item
    /// </summary>
    /// <param name="item">item to check for containment</param>
    /// <returns>true if item contained; false if not</returns>
    public bool Contains(T item) {
        if (m_buckets != null) {
            int hashCode = InternalGetHashCode(item);
            // see note at "HashSet" level describing why "- 1" appears in for loop
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) {
                    return true;
                }
            }
        }
        // either m_buckets is null or wasn't found
        return false;
    }

И я читал во многих местах "сложность поиска в hashset - O (1)". Как? Тогда почему это для -l oop существует?

Редактировать:. net ссылка: https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs

Answer 1

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

Мы не живем в идеальном безупречный мир. Прежде всего, рассмотрим хеширование строк. В. NET, есть (2 ^ 16) ^ n возможных строк длины n; GetHashCode возвращает long, и есть 2 ^ 64 возможных значений long. Этого вполне достаточно, чтобы иметь sh каждую строку длиной 4 с уникальным long, но если мы хотим, чтобы строки были длиннее, то должно существовать два разных значения, которые дают одинаковое га sh - это называется столкновение . Кроме того, мы все равно не хотим поддерживать 2 ^ 64 сегмента. Обычный способ справиться с этим - взять хеш-код и вычислить его значение по модулю количества блоков, чтобы определить номер блока ¹ . Итак, вы получите: нам нужно учесть коллизии .

Ссылочная . NET Каркасная реализация использует самый простой способ борьбы с коллизиями - каждое ведро содержит связанный список всех объектов, которые приводят к определенному ха sh. Вы добавляете объект A, он назначается корзине i. Вы добавляете объект B, он имеет тот же ha sh, поэтому он добавляется в список в сегменте i сразу после A. Теперь, если вы ищете какой-либо элемент, вам нужно просмотреть список всех объектов и вызвать действительный метод Equals, чтобы выяснить, действительно ли это то, что вы ищете. Это объясняет, что для l oop - в худшем случае вам придется go по всему списку .

Хорошо, так как "сложность поиска в hashset is O (1) "? Это не так. В худшем случае сложность пропорциональна количеству предметов. Это O (1) в среднем . ² Если все объекты попадают в одно и то же место, запрашивая элементы в конце списка (или те, которые не являются в структуре, но попадет в то же ведро) будет будет O (n).

Так что люди имеют в виду под «это в среднем O (1)»? Структура отслеживает, сколько объектов пропорционально количеству сегментов, и, если оно превышает некоторый порог, называемый коэффициентом загрузки, оно изменяет размер. Легко видеть, что это делает среднее время поиска пропорциональным коэффициенту нагрузки.

Вот почему важно, чтобы функции ha sh были равномерными , что означает, что вероятность того, что два случайно выбранные различные объекты получают одинаковые long, назначенные 1/2 ^ 64 ³ . Это обеспечивает равномерное распределение объектов в таблице ha sh, поэтому мы избегаем патологических случаев, когда одна корзина содержит огромное количество элементов.

Обратите внимание, что если вы знаете функцию ha sh и алгоритм, используемый таблицей ha sh, вы можете вызвать такой патологический случай и O (n) поиск. Если сервер принимает входные данные от пользователя и сохраняет их в таблице ha sh, злоумышленник, которому известны функции ha sh и реализации таблиц ha sh, может использовать это как вектор для атаки DDoS. Есть способы справиться с этим тоже . Рассматривайте это как демонстрацию того, что да, наихудший случай может быть O (n) и что люди обычно знают об этом.

Существуют десятки других, более сложных способов, которыми можно реализовать таблицы sh. Если вы заинтересованы, вам нужно исследовать самостоятельно. Поскольку структуры поиска настолько распространены в компьютерных науках, люди придумали всевозможные сумасшедшие оптимизации, которые сводят к минимуму не только теоретическое количество операций, но и такие вещи, как потери в кеше процессора.

---

[1] Это именно то, что происходит в заявлении int i = m_buckets[hashCode % m_buckets.Length] - 1

[2] По крайней мере, те, которые используют наивные цепочки, не являются. Существуют таблицы sh с наихудшей постоянной сложностью времени . Но обычно они хуже на практике по сравнению с теоретически (в отношении сложности времени) более медленными реализациями, в основном из-за пропусков кэша ЦП.

[3] Я предполагаю, что область возможных хэшей является установленной из всех long с, так что их 2 ^ 64, но все, что я написал, обобщает любой другой непустой, конечный набор значений.