C++: предложения о хэш-функции для последовательности строк, где порядок строк не имеет значения

Допустим, у вас есть эти две последовательности строк

abc cba bc

bc abc cba

Я пытаюсь создать отображение для таких последовательностей (последовательность также является строкой), чтобы две вышеупомянутые последовательности отображались в одном и том же сегменте.

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

Однако я очень новичок в мире функций хеширования строк и не знаю, будет ли этот подход эффективным.

На этом сайте http://www.partow.net/programming/hashfunctions/index.html

Я нашел много разных реализаций для хеширования строк, однако я не уверен, какая из них будет "лучшей" для моих нужд.

Некоторые технические детали каждой строки в последовательности состоят в том, что каждая из них будет содержать не более 25 символов. Также каждая последовательность не будет иметь более 3 строк.

Вопросы

1. Будет ли работать этот подход добавления результатов функции хеширования строки к каждой строке последовательности?

2. Если да, какую функцию хеширования строк мне следует использовать, это даст небольшое количество коллизий, а также будет эффективным по времени?

заранее спасибо

Источник

3 ответа

Решение

Просто демонстрация идеи (очень неэффективное копирование строк), сложность O(NlogN), где N - размер ключа (=== O(1), если ваши ключи имеют постоянную длину, известную во время компиляции), я не думаю, что вы может сделать лучшую сложность:

#include <boost/functional/hash.hpp>
#include <set>
#include <algorithm>

std::size_t make_hash(
  std::string const& a,
  std::string const& b,
  std::string const& c)
{
    std::string input[] = {a,b,c};
    std::sort(input, input + (sizeof(input)/sizeof(*input)));
    return boost::hash_range(input, input + (sizeof(input)/sizeof(*input)));
}

#include <iostream>
// g++ -I.../boost_1_47_0 string_set_hash.cpp
int main()
{
    std::cout << make_hash("abc", "bcd", "def") << std::endl; // 46247451276990640
    std::cout << make_hash("bcd", "def", "abc") << std::endl; // 46247451276990640
}

Фрагмент boost/functions /hash.hpp для справки:

template <class T>
inline void hash_combine(std::size_t& seed, T const& v)

{
    boost::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

template <class It>
inline std::size_t hash_range(It first, It last)
{
    std::size_t seed = 0;

    for(; first != last; ++first)
    {
        hash_combine(seed, *first);
    }

    return seed;
}
Источник

Я бы хэшировал каждый элемент в отдельности.

Затем сортируйте эти хеши. Сортировка 3 size_t это быстро.

Затем соедините эти хеши. Ваша библиотека может иметь функции цепочки хеширования или даже использовать hash( a+b+c ) с переполнением.

Избегайте xor, потому что xor двух одинаковых хеш-значений равен нулю. И хэш одинаковых строк идентичен. Так что наивный хор может привести к ( a,a,b ) а также ( c,c,b ) иметь тот же хэш-вывод, который отстой.

Источник

Какую бы функцию хеширования вы ни выбрали, вам нужен оператор для окончательной комбинации каждого отдельного хеша, который будет:

  • коммутативной
  • ассоциативный

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

Вы также можете изменить порядок операций: сначала добавьте строки символьно вместе (например, добавление "ab" и "cba" становится ('a' + 'c')('b' + 'b')('\0' + 'a') с переносом переноса для суммы или произведения, поэтому, возможно, xor является интересным кандидатом здесь), а затем примените хеш-функцию. Вы даже можете объединить эти две операции при их выполнении (псевдокод следует):

int hash(string a, string b, string c){
    int r = 0, k;
    int m = max(a.length(), max(b.length(), c.length()));
    for (int i = 0; i < m; i++) {
        k = ( i < a.length()? a[i] : 0) ^
              (i < b.length()? b[i] : 0) ^
              (i < c.length()? c[i] : 0);
        r = hash(r,k);
    }
    return r;
}

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

Совершенно другое (и лучше?) Решение состоит в том, чтобы просто отсортировать последовательность (3 записи означают квазипостоянное время), а затем составить упорядоченную карту с функцией сравнения, рассматривая строки как "цифру" из трехзначного числа. Но это выходит за рамки вопроса.

Источник
Другие вопросы по тегам