C++:关于字符串序列的哈希函数的建议,其中字符串的顺序是无关紧要的

Question

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

abc cba bc

bc abc cba

我正在尝试为这些序列创建映射(序列也是一个字符串),以便将上述两个序列映射到同一个桶中.

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

但是我对字符串散列函数的世界很新,我不知道这种方法是否有效.

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

我发现了很多不同的字符串散列实现,但是我不确定哪一个对我的需求来说是"最好的".

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

问题

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

2. 如果是,我应该使用哪个字符串散列函数,这会产生少量的冲突并且也是时间有效的？

先感谢您

Answer 1

只是想法演示（非常低效的字符串复制），复杂度为 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;
}