Hashing std ::アイテムに依存しないベクトルorder

Question

std::vectorのハッシュ関数を探していますが、これはベクトルのアイテムの順序とは関係ありません。

は、言い換えれば、私はこれを実現する方法を上

std::vector<int> v1(1,2,3); 
std::vector<int> v2(2,3,1); 
std::vector<int> v3(1,3,2); 

任意のアイデアのために私に同じ結果を与えるだろうハッシュの実装、 を探していますか？

Answer 1

template<template<class...>class element_hash=std::hash> 
struct symmetric_range_hash { 
    template<class T> 
    std::size_t operator()(T const& t) const { 
    std::size_t r = element_hash<int>{}(0); // seed with the hash of 0. 
    for (auto&& x:t) { 
     using element_type = std::decay_t<decltype(x)>; 
     auto next = element_hash<element_type>{}(x); 
     r = r + next; 
    } 
    return r; 
    } 
}; 

これでいいはずです。対称的な+でハッシュを集めます。

+は、サイクルを取得するのに時間がかかるため、^より優れています。 ^の場合、{1,1}と{2,2}は同じものをハッシュします（一般に偶数のものは「消えます」）。 +で代わりにそれらは乗算されます。

最終結果は、その値のハッシュとそのカウント、mod "max（size_t）+1"との合計値です。

unordered_mapには、ハッシュと等価性の両方が必要であることに注意してください。衝突が必要な場合は、==も書き込む必要があります。

struct unordered_equal { 
    template<class C> 
    bool operator()(C const& lhs, C const& rhs)const { 
    using std::begin; 
    using K = std::decay_t< *decltype(begin(lhs)) > >; 
    std::unordered_map< K, std::size_t > counts; 
    for (auto&& k : lhs) { 
     counts[k]++; 
    } 
    for (auto&& k : rhs) { 
     counts[k]--; 
    } 
    for (auto&& kv : counts) 
     if (kv.second != 0) return false; 
    return true; 
    } 
};