重み付けされたハッシュ結合

Question

これは、2つのハッシュを結合して、得られたハッシュに入力の1つの影響がより大きくなるようにする方法が多少異なります。おおよそ対称ケースでは、我々はそのようなブーストなどのアルゴリズムを持って

:: hash_combine：

template <class T> 
inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

私は多分、インターフェイスが似ているだろう、加重バージョンを探しています：

uint64_t weighted_hash_combine(uint64_t hashA, uint16 weightA, uint64_t hashB, uint16 weightB); 

前提入力ハッシュの1つの変化によって影響を受ける出力ハッシュのビットの確率は、weightAとweightBの比の関数である。

これにより、不均衡なツリーのツリーハッシュアルゴリズムを改善できます。ツリーをハッシュする簡単な方法はhereであり、本質的に幅広い最初のトラバースは各ハッシュ（ノード）を累積値にプッシュします。この問題は、結合されたハッシュに混合される最後のノードが、最初のノードよりも結果に大きな影響を及ぼすことになります。

妥当な加重ハッシュの組み合わせが利用可能な場合は、各ハッシュに貢献したノードの数に基づいて組み合わせをバイアスし、ハッシュ関数の公平性を向上させることができます。

は、これまでのところ私は作ってみた：

uint64_t weighted_hash_combine(uint64_t hashA, uint16 weightA, uint64_t hashB, uint16 weightB) 
{ 
    if (weightA > weightB) 
    { 
    return weighted_hash_combine(hashB,weightB,hashA,weightA); 
    } 
    uint64_t ratio = weightA/weightB; 
    uint64_t combined = hashA; 
    for (uint64_t i = 0; i < ratio; i++) 
    { 
    hash_combine(combined, hashB); 
    } 
    return combined; 
}  

これはむしろかかわらず、数値洗練さに欠けているので、私は社会がよりよい解決策を考案/リコールすることができます願っています。

高レベルの目標は、（サイズまたは）ハッシュ値が異なる場合に、ツリー間の等価性テストを短絡することです。ただし、1つまたは2つのリーフでのみ異なることが多く、どちらを推定するかはわかりません。

Answer 1

ハッシュはそのようには機能しません。 の変更がハッシュであれば、結合ハッシュを変更することが保証され、実際にのどちらかをハッシュに変更することで、結合されたハッシュの値を完全に決定することができます。

最も一般的に使用される混合物は上のバリエーションである：P1、P2が異なる奇素数である

h = h1*P2 + h2*P1 

（又は1）。これは、ワードサイズに応じてmod 2^32またはmod 2^64で実行されますが、hのいずれかの値をh1またはh2のいずれかを選択して任意の値にすることができます。私たちはこのように混在しています。