C++：一連の文字列のハッシュ関数についての提案文字列の順序は無関係です

Question

あなたは、文字列

abc cba bc

bc abc cba

私がしようとしているのこれら二つの配列があるとしましょう上記の2つのシーケンスが同じバケットにマッピングされるように、そのようなシーケンスのマッピング（シーケンスも文字列）を作成します。

私の最初の考えは、各文字列に個別に適用されるハッシュ関数の結果を追加することです。このようにして、彼らの秩序は重要ではありません。シーケンス文字列全体にハッシュ関数を適用した場合、もちろんハッシュ結果は異なります。

しかし、私は文字列ハッシング関数の世界では非常に新しいので、このアプローチが効率的かどうかはわかりません。このウェブサイトで

http://www.partow.net/programming/hashfunctions/index.html

しかし私は、私は1つが私のニーズのために「最善」でしょうかわからないんだけど、文字列のハッシュのための多くの異なる実装を見つけました。

シーケンス内の各文字列についての技術的な詳細は、それぞれが25文字を超えないことです。また、各シーケンスは3つ以上の文字列を持ちません。

質問

1.うシーケンス作業の各文字列に文字列のハッシュ関数の結果を追加するこのアプローチは？

2.はいの場合、どの文字列ハッシュ関数を使用すれば、少ない衝突量が得られ、時間効率も良いでしょうか？

は事前

Answer 1

Nは、キーのサイズでジャストアイデアデモ（非常に非効率的な文字列のコピー）、複雑性O（NlogN）でいただきありがとうございます（=== 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 
} 

参照のためのブースト/機能/ 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; 
} 

Answer 2

どのようなハッシュfunctio nはあなたがなり、個々のハッシュの最後の組み合わせのためのオペレータをしたい、選ぶ：

• 可換連想

合計、製品、および排他的または気にしています積分値の候補とする。はい、追加すると機能します。あなたは依然として解決される必要のない無関係のシーケンスにも衝突を起こすので、文字列比較関数が必要ですが、同じ文字列セットの並びは同じバケットになります。

操作順序を逆にすることもできます。文字列を最初に一緒に追加します（例：sumまたはproductのためのキャリー伝播を伴う "ab"と "cba"の加算は（ 'a' + 'c'）（ 'b' + 'b'）（ '\ 0' + 'a'）なので、おそらくxorはここで面白い候補）、ハッシュ関数を適用します。それらを実行しながら、あなたも（擬似コードは以下の）これら2つの操作を組み合わせることができ：

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桁の数字の "数字" 。しかし、これは問題の範囲外です。

Answer 3

それぞれの要素を個別にハッシュします。

これらのハッシュをソートします。ソート3 size_tは高速です。

これらのハッシュをチェーンします。あなたのライブラリには、ハッシュチェーン機能があるかもしれません。また、オーバーフローラップを伴うhash(a+b+c)を使用することもできます。

2つの同一のハッシュ値がゼロであるため、xorを避けてください。同じ文字列のハッシュも同じです。したがって、純粋なxorは、同じハッシュ出力を持つ(a,a,b)と(c,c,b)につながる可能性があります。