C ++: предложения о хэш-функции для последовательности строк, где порядок строк не имеет значения
Допустим, у вас есть эти две последовательности строк
abc cba bc
bc abc cba
Я пытаюсь создать отображение для таких последовательностей (последовательность также является строкой), чтобы две вышеупомянутые последовательности отображались в одном и том же сегменте.
Моей первоначальной мыслью было бы добавить результаты хеширующей функции, которая применяется к каждой строке отдельно. Таким образом, их порядок не имеет значения. Если бы я применил функцию хеширования к строке последовательности в целом, то, конечно, результат хеширования был бы другим.
Однако я очень новичок в мире функций хеширования строк и не знаю, будет ли этот подход эффективным.
На этом сайте http://www.partow.net/programming/hashfunctions/index.html
Я нашел много разных реализаций для хеширования строк, однако я не уверен, какая из них будет «лучшей» для моих нужд.
Некоторые технические детали каждой строки в последовательности состоят в том, что каждая из них будет содержать не более 25 символов. Также каждая последовательность не будет иметь более 3 строк.
Вопросы
1. Будет ли этот подход добавления результатов функции хеширования строки к каждой строке последовательности работать?
2. Если да, какую функцию хеширования строк я должен использовать, это дало бы небольшое количество коллизий и также было бы эффективным по времени?
заранее спасибо
Решение
Просто демонстрация идеи (очень неэффективное копирование строк), сложность 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;
}
Другие решения
Какую бы функцию хеширования вы ни выбрали, вам нужен оператор для окончательной комбинации каждого отдельного хеша, который будет:
- коммутативной
- ассоциативный
сумма, продукт и эксклюзив или приходят на ум в качестве кандидатов на интегральные ценности. Так что да, добавление будет работать. У вас все равно будут коллизии на несвязанных последовательностях, которые необходимо разрешить, поэтому вам потребуется функция сравнения строк, но перестановки одного и того же набора строк окажутся в одном и том же сегменте.
Вы также можете изменить порядок операций: сначала добавьте строки по символам (например, добавьте «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 двух одинаковых хеш-значений равен нулю. И хэш одинаковых строк идентичен. Так что наивный хор может привести к ( a,a,b ) а также ( c,c,b ) иметь тот же хэш-вывод, который отстой.