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

Просто демонстрация идеи (очень неэффективное копирование строк), сложность 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/functional/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;
}

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

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

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

Вы также можете изменить порядок операций: сначала сложить строки посимвольно (например, добавление «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 записи означают квазипостоянное время), а затем создать упорядоченную карту с функцией сравнения, рассматривающей строки как «цифру» трехзначного числа. Но это выходит за рамки вопроса.

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

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

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

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