Блог

Главная - Вопросы по программированию - Вы действительно можете эффективно разделить одинаковые строки на группы с помощью хэшей?

Вы действительно можете эффективно разделить одинаковые строки на группы с помощью хэшей?

#algorithm #hash

#алгоритм #хэш

Вопрос:

Я читаю эту статью в этой статье говорится о хешировании строк. В разделе «Поиск повторяющихся строк в массиве строк» утверждается, что вы можете группировать идентичные строки с временной сложностью O(M*N*log(N)) , используя хеширование строк.

Глядя на этот пример кода, представленный в статье

 vector<vector<int>> group_identical_strings(vector<string> constamp; s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i  )
        hashes[i] = {compute_hash(s[i]), i};

    sort(hashes.begin(), hashes.end());

    vector<vector<int>> groups;
    for (int i = 0; i < n; i  ) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
            groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}

Я очень смущен тем, насколько этот код будет правильным, потому что он создает новую группу только при условии, что hashes[i].first != hashes[i-1].first . Две строки могут быть разными, но иметь одинаковые хэши, и поэтому две строки могут быть добавлены в одну и ту же группу, даже если они разные? Это условие мне кажется недостаточным.

Я ошибаюсь? Правильный ли этот код? Почему?

Если нет, то действительно ли этот алгоритм или, по крайней мере, эта сложность достижима?

Комментарии:

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

Ответ №1:

Вы совершенно правы, что две разные строки могут иметь одинаковый хэш. Это называется столкновением хэшей. Однако это сводится к тому, какую хэш-функцию вы используете. Существуют хеш-функции, для которых обнаружение коллизии настолько маловероятно, что вы можете использовать этот алгоритм, не опасаясь его нарушения. В криптографии мы полагаемся на это свойство криптографически безопасных хеш-функций (см., Например, Здесь ).

Фактически, в самом источнике, который вы упомянули, указано следующее:

Это важная часть, которую вы должны иметь в виду. Использование хеширования не будет на 100% детерминированно корректным, потому что две совершенно разные строки могут иметь один и тот же хэш (хэши сталкиваются). Однако в подавляющем большинстве задач это можно смело игнорировать, поскольку вероятность столкновения хэшей двух разных строк все еще очень мала. И в этой статье мы обсудим некоторые методы, как сохранить вероятность столкновений на очень низком уровне.

Таким образом, алгоритм, как вы говорите, не математически корректен. Но при правильном выборе хэш-функции вероятность ее сбоя на практике ничтожно мала.

Метки: