unordered_map - ハッシュ関数は無効です

Question

ハッシュ関数（定数0を返す）が効果を発揮しないように見えるのはなぜですか？

ハッシュ関数が一定に戻っているので、出力としてすべての値が3になると予想していましたが、ハッシュ関数が定数であるかどうかにかかわらず、std::vectorの値を一意の値に一意にマップしているようです。取得

#include <iostream> 
#include <map> 
#include <unordered_map> 
#include <vector> 


// Hash returning always zero. 
class TVectorHash { 
public: 
    std::size_t operator()(const std::vector<int> &p) const { 
    return 0; 
    } 
}; 

int main() 
{ 
    std::unordered_map<std::vector<int> ,int, TVectorHash> table; 

    std::vector<int> value1({0,1}); 
    std::vector<int> value2({1,0}); 
    std::vector<int> value3({1,1}); 

    table[value1]=1; 
    table[value2]=2; 
    table[value3]=3; 

    std::cout << "\n1=" << table[value1]; 
    std::cout << "\n2=" << table[value2]; 
    std::cout << "\n3=" << table[value3]; 

    return 0; 
} 

出力：

1=1 
2=2 
3=3 

予想される出力：

1=3 
2=3 
3=3 

私はハッシュについて何をしないのですか？

Answer 1

あなたはハッシュ関数の使用を誤解：要素を比較するために用いていません。内部的には、マップは要素をバケットに編成し、ハッシュ関数は要素が存在するバケットを決定するために使用されます。要素の比較は別のテンプレートパラメータを用いて行われる、unordered_mapテンプレートの完全な宣言を見て：調理人の後

template< 
    class Key, 
    class T, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator< std::pair<const Key, T> > 
> class unordered_map; 

次のテンプレートパラメータがキーコンパレータです。あなたが期待する動作を取得するには、あなたはこのような何かしなければならないでしょう：

class TVectorEquals { 
public: 
    bool operator()(const std::vector<int>& lhs, const std::vector<int>& rhs) const { 
     return true; 
    } 
}; 

std::unordered_map<std::vector<int> ,int, TVectorHash, TVectorEquals> table; 

を今すぐあなたのマップは、単一の要素を持つことになりますと、すべての結果が3になります。

Answer 2

ハッシュ衝突が存在しても、saneハッシュテーブルの実装は情報を失ってはいけません。衝突の解決を可能にするいくつかの手法があります（通常、実行時パフォーマンスとデータの完全性のトレードオフ）。明らかに、std::unordered_mapがそれを実装します。

参照：Hash Collision Resolution

Answer 3

述語キー比較クラスを追加します。

class TComparer { 
public: 
    bool operator()(const std::vector<int> &a, const std::vector<int> &b) const { 
     return true; // this means that all keys are considered equal 
    } 
}; 

このようにそれを使用します。

std::unordered_map<std::vector<int> ,int, TVectorHash, TComparer> table; 

期待通り次に、あなたのコードの残りの部分が動作します。