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 是 key 的大小(=== O(1) 如果您的 key 在编译时具有已知的恒定长度)，我不知道不认为你可以做得更好的复杂性:

#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;
}