14 
#include <iostream>

int main() {
    std::hash<int> hash_f;
    std::cout << hash_f(0) << std::endl;
    std::cout << hash_f(1) << std::endl;
    std::cout << hash_f(2) << std::endl;
    std::cout << hash_f(3) << std::endl;
}

「g++ main.cpp -std=c++11」でコンパイルすると、結果は次のようになります。

0
1
2
3

なぜこうなった？私はライブラリを使用しておらず、特殊なハッシュ関数も持っていません。

補遺: セットのハッシュがそのコンポーネントのハッシュの合計である int の unordered_set の unordered_set のハッシュを定義したかったのですが、{2,4} のハッシュが{1,5} のハッシュ。これを回避する最も簡単な方法は、 std::hash double 関数を使用することです。

4

3 に答える 3

7

ハッシュ関数int→<code>int が同一性であることは完全に理にかなっているように思えますが、なぜそれに驚いたのかは明らかではありません。これ以上の計算を実行しても意味がありません。実際、これは用語のあらゆる意味で完全なハッシュです。

は、値を暗号化するのではなく、std::hash(ほぼ一意に)識別することになっていることに注意してください。

uint9999999_t値をハッシュのサイズに「圧縮」するために何らかの作業を行う必要があるのは、ハッシュ自体 (たとえば ) よりも大きな型をハッシュしたい場合のみです。

于 2016-07-11T11:00:18.703 に答える
6

他の答えは、アイデンティティ関数の背後にある理論的根拠を非常によくカバーしています。補遺に対処するには：

unordered_set のハッシュをそのコンポーネントのハッシュの合計として定義したかったのですが、{2,4} のハッシュが {1,5} のハッシュと同じであるため、それが単なる ID である場合はクールではありません。これを回避する最も簡単な方法は、 std::hash 関数を使用することです。

ご覧のとおり、+演算子を使用してハッシュを結合することは最善のアイデアではありません。より堅牢にするために、XOR ( ) 演算子を使用するか、たとえば(この SO 投稿の詳細^) によって採用されたアプローチからインスピレーションを得ることができます。boost::hash_combine

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

例として、2 つの整数のペア (1,5 / 2,4) と aseedが 0 の場合、これは次のようになります。

uint32_t seed = 0;
seed ^= 1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 5 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077526

uint32_t seed = 0;
seed ^= 2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 4 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077584
于 2016-07-11T12:01:03.097 に答える