0

私はstd::unordered_map<std::string, int> map;

次に、これに大量の要素を挿入しますが、文字列キーはすべて一意です。

次のシナリオは可能で、どのように処理されますか?

map[x] = 5;
map[y] = 3;

xとは異なる文字列であると仮定しyますが、同じハッシュを生成するため、5 と 3 は同じバケットに配置されます。

値を取得しようとするとmap[x]、マップはどのように正しい値 5 を返しますか? ハッシュxは、2 つの要素 5、3 を含むバケットを提供しますが、比較するキー自体がないと、正しい値を取得する方法がわかりません。

私は何が欠けていますか？

4

2 に答える 2

3

の完全な宣言はunordered_map次のようになります。

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

キータイプに対してハッシュ関数と等値比較子の両方が必要であることに注意してください。

特定のキーを持つ要素を検索する場合、コンテナーは最初にハッシュ関数を使用して正しいバケットを見つけ、次にそのバケット内の要素を調べて、等値比較子を使用して各要素のキーを比較します。

于 2013-10-24T02:18:26.463 に答える
1

バケツはまさにバケツです。unordered_map は実際にはテンプレートであり、とりわけキーと値の型、およびキーの等価性をチェックする関数 (デフォルトはstd::equal_to<KeyType>) を取ります。等価比較を使用して、検索している値に一致するバケット内の要素を見つけます。為に。

あなたが完全に悪であり、かなりの数の衝突でキーを供給する場合、一般にハッシュテーブルは線形またはログ時間に縮退します。実際には、それらは一般にO(1)に近いです。

于 2013-10-24T02:18:38.403 に答える