ハッシュテーブル用のコンテンツsha1を生成する方法は？私のプロジェクトで

Question

は、私はこのように、直列化インタフェースを介して、指定されたオブジェクトのためにSHA1を生成する必要があります。

class sha1_sink : public isink{...}; 

sha1_sink sink; 
serialize(sink, obj); 
return sink.get_digest(); 

シリアル化はテンプレート関数であり、異なるタイプのため、オーバーロード。

ハッシュテーブルを除いて、ほとんどの場合うまくいきます。

オブジェクトAがBと同じ内容の場合、同じsha1を持つはずです。順序はハッシュテーブルにとって無意味です。したがって、ハッシュテーブルAとBが同じ要素を持ちますが、順序が異なる場合、それらは同じとみなされます。

1つの解決策は、関数の呼び出しを最初にソートすることですが、明らかに遅くて余分なメモリが必要です。

シリアライズする前に負荷係数を既定値（0.5など）に設定して再ハッシュすることができます。ハッシュテーブルを調整する必要がある場合でも、要素の順序は安定していると思います。

しかし、私は上記のどれも十分ではないと思うし、もっと良い解決策を模索したいと思っています。私は、誰かが正しい道に乗る方法を私に見せることができれば、とても感謝しています。

ハッシュテーブルの場合は、std :: unordered_map/setと同様に汎用コンテナです。

Answer 1

ハッシュテーブルでは、std::unordered_map<K, V>または独自の実装を意味すると思います。

あなたのハッシュテーブルのエントリは、比較的少数であり、挿入、削除の操作が制限されている、あなたはstd::map<K, V>（と私はあなたのserilizationテンプレートがstd::mapするためのメソッドをオーバーロードしました願っています）、または保証は下の順序を並べ替えられます同等のデータ構造を使用できる場合フード（平衡二分探索木）。したがって、直列化されたオブジェクトは、私の希望と同等になります。 std::mapの操作では、10kのエントリに対してログの時間がかかるため、挿入/削除ごとにその操作は妥当なlog2(10k) = 10になります。

あなたが言ったように、あなたは約10kのエントリを持っていますが、固定負荷係数を使用することは、ハッシュテーブルのパフォーマンスに影響する可能性があるので、あまり考えられません。