std :: unordered_setのKeyEqualとは何ですか？

Question

第3パラメータKeyEqualの目的はstd::unordered_setですか？ハッシュの一意性は十分ではありませんか？

template< 
    class Key, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator<Key> 
> class unordered_set; 

申し訳ありませんが、この質問は素朴に聞こえる。 Python/PHPからC++に移動しています:)

今のところ私の実装はKeyEqualです。Hash implとなります。だから私は正しくそれをするのだろうかと思っていた。

Answer 1

しかし、ハッシュの衝突があった場合はどうなりますか？

ピクチャが等しいハッシュ値を有するために、2つの異なる要素が、起こる場合を示しています。その結果、ハッシュ値はでなく、となることがあります。

std::unordered_setの ref引用

---

：

内部的には、unordered_setの要素がどの 特定の順序で並べ替えられますが、高速アクセスを可能にするために彼らのハッシュ 値に応じて、バケットに編成されていませんが個々の要素に直接それらの値（平均で一定の平均時間複雑度を持つ）を で追加します。

バケットには複数の要素が含まれることがあります。これら2つの要素は同じハッシュ値を持ちますが、一意になることは保証されていません！

---

ユニークあることが保証されている唯一のものはキーです！

Answer 2

かなり単純に、セットは2つのキーが等しいかどうかを知る必要があります。 KeyEqualはこれを行うための仕組みです。

等価を比較しない2つのキーが同じ値にハッシュする可能性があることに注意してください。また、その値をチェックできる必要があります。

Answer 3

異なる値に必ずしも異なるハッシュがあるとは限りません。たとえば、std::stringのオブジェクトは実質的に無限ですが、std::hash<std::string>()(s)という結果のオブジェクトは2^N std::size_tなので、アルゴリズムではそうしたことは起こりませんが、ハッシュの衝突は避けられません。

したがって、std::unordered_setおよびstd::unordered_mapは、ハッシュ値が等しい場合でも要素が等しいかどうかをテストする方法が必要です。

Answer 4

のは、単純なモッズ%操作を行いハッシュ関数で、例えばint秒のセットを見てみましょう

struct IntMod { 
    constexpr std::size_t operator()(int i) const { return i % 10; } 
}; 

std::unordered_set<int, IntMod> s; 

これは簡単にハッシュ衝突につながることができ、そしてそれはあなたがする必要が発生したときキーが既に存在するかどうかを知るためにキーを比較することができる。

s.insert(25); // hash == 5 
s.insert(35); // hash == 5 
assert(*s.find(25) == 25); // both 25 and 35 are present despite the same hash 
assert(*s.find(35) == 35); 

私たちは、同様のハッシュ関数を使用しています（あなたはそれがデフォルトで行う提案のように）、それは第2の挿入に壊しKeyEqualを追加した場合。

struct IntEq { 
    constexpr bool operator()(int a, int b) const { 
    return IntMod{}(a) == IntMod{}(b); 
    } 
}; 

std::unordered_set<int, IntMod, IntEq> s; 
s.insert(25); // hash == 5 
s.insert(35); // hash == 5 
assert(*s.find(25) == 25); 
assert(*s.find(35) == 35); // now this fails. s.find(35) returns iterator to 25