9

假设你有这两个字符串序列

abc cba bc

bc abc cba

我正在尝试为此类序列创建一个映射（该序列也是一个字符串），以便将上述两个序列映射到同一个存储桶中。

我最初的想法是添加分别应用于每个字符串的散列函数的结果。这样他们的顺序就无关紧要了。如果我将散列函数作为一个整体应用于序列字符串，那么散列结果当然会有所不同。

但是，我对字符串散列函数的世界非常陌生，我不知道这种方法是否有效。

在这个网站http://www.partow.net/programming/hashfunctions/index.html

我发现了许多不同的字符串散列实现，但是我不确定哪一个最适合我的需求。

关于序列中每个字符串的一些技术细节是每个字符串不超过 25 个字符。此外，每个序列不会有超过 3 个字符串。

问题

1.这种将字符串散列函数的结果添加到序列的每个字符串的方法是否有效？

2.如果是的话，我应该使用哪个字符串散列函数会产生少量的冲突并且还可以节省时间？

先感谢您

4

3 回答 3

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/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;
}
于 2013-04-01T10:42:26.557 回答
0

无论您选择哪种散列函数，您都需要一个运算符来对每个单独的散列进行最终组合，即：

  • 可交换的
  • 联想

总和、乘积和排他性或作为整数值的候选者。所以是的，添加会起作用。您仍然会在需要解决的不相关序列上发生冲突，因此您需要一个字符串比较函数，但同一组字符串的排列最终会出现在同一个存储桶中。

您还可以颠倒操作顺序：首先将字符串按字符添加在一起（例如，添加“ab”和“cba”变为 ('a' + 'c')('b' + 'b')('\0 ' + 'a') 对 sum 或 product 进行进位传播，因此 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 位数字的“数字”。但这超出了问题的范围。

于 2013-04-01T11:02:57.330 回答
0

我会单独散列每个元素。

然后对这些哈希进行排序。排序 3size_t很快。

然后链接这些哈希。您的库可能具有哈希链函数，甚至可以hash( a+b+c )与溢出包装一起使用。

避免异或，因为异或两个相同的哈希值为零。并且相同字符串的哈希是相同的。因此，一个天真的异或可以导致( a,a,b )并( c,c,b )具有相同的哈希输出，这很糟糕。

于 2013-04-01T12:15:37.020 回答