c++ - unordered_map はそのハッシュを内部でどのように使用しますか?

Question

unordered_map はハッシュ関数を内部的にどのように使用して、キーに属するバケットにアクセスしますか?

std::hash は size_t 型を返します。これは、コンテナーに存在するバケットの数よりも大きい場合があります。返されたハッシュ値はバケット インデックスにどのようにマッピングされますか?

典型的な unordered_map 実装は size() または max_size() によって返されたハッシュのモジュロを実行しますか、それとももっと複雑なことが起こりますか?

Answer 1

典型的な unordered_map 実装は size() または max_size() によって返されたハッシュのモジュロを実行しますか、それとももっと複雑なことが起こりますか?

ほとんど。モジュロは になりbucket_count()ます。これは、ハッシュ テーブル内のバケットの数だからです。

標準では、モジュロ演算でこれを行う必要はありません。bucket()関数が何らかの方法でキー値を範囲[0,bucket_count)にマップし、同等のハッシュを持つキーが同じバケットにマップされるだけです。ハッシュのモジュラスは、これを行う最も簡単な方法です。