C++文字列のハッシュが文字列またはメモリアドレスをハッシュしますか？

Question

私はこれまでハッシュアルゴリズムを学んだことがなかったし、std :: unordered_mapを使うとハッシュ関数（実際には）は文字列ではなくメモリアドレスをハッシュしていることがわかった。私が間違っている場合は私を修正してください。しかし、未処理の文字列を変更してunordered_mapに追加するだけで、メモリアドレス（ポインタ）が同じであれば何も追加しませんでした。

とstd :: stringは別の領域のメモリのかに再割り当てするかどうかに依存して新しいキーが追加されているかどうか、以下の場合：直接でのstd ::文字列を使用している場合しかし、

std::unordered_map<const char*, char*> myMap; 

std::string myString = "Key1"; 

myMap[myString.c_str()] = "someVal"; // <--- Adds a new key, size is now 1 
myString = "Key2"; 
myMap[myString.c_str()] = "someVal"; // <--- Doesn't add a new key "Key2" didn't need to be reallocated 

テンプレートを変更すると、別のキーをマップに追加するので、unordered_mapテンプレートはstd :: stringに特化していて、実際には文字列自体をハッシュすることになります。それは文字列自体をハッシュする必要がある場合、この方法は遅いですか？

私がこれを持ってきた理由は、私が見たチュートリアルが、それがハッシュされる実際の文字列そのものであるという意味を伝えているようだということです。ここでもスタックオーバーフローについては、パフォーマンス上の理由から「文字列全体をチェックする必要はなく、必要なだけ多くの文字をどうやって言い換えるか」という言い方を人々は見てきました。

私が得た印象は、文字列リテラルや文字列へのポインタでは間違っていますが、std :: stringクラスでは間違っていますか？

Answer 1

const char*は文字列であると誤解されています。実際にはポインタです。したがって、std::unordered_map<const char*, anything>はポインタ（タイプconst char*）をキーとして使用し、ポインタ（ハッシュするアドレス）のハッシュキーとしてstd::hashの特殊化を使用します。

文字列をキーとして使用する場合は、std::stringを使用する必要があります。 std::unordered_map<std::string, anything>。

---

編集私はまた、ポインタの代わりの文字列を使用すると、少なくとも危険なことが多いことは不可能であると言うべきです。あなたが思うことはしません。問題は、文字列（文字列）とそのアドレス（ポインタ）が必ずしもプログラムの存続期間中にペア設定されているわけではない（一部のconst char*オブジェクトで当てはまるかもしれませんが）。次

std::unordered_map<const char*,int> map; 
char str[11] = "bad"; 
map[str] = 2;   // hashes str = char* 
auto x = map["bad"]; // hashes address of "bad"; x!=2 

を考える。これは、意図したとおりにキーとしてアドレスを使用して動作しないことを例示して：あなたはのための標準的な基本的な専門分野を見れば、あなたは、文字列（"bad"）

Answer 2

から要素を取得することはできませんstd::hash。 const char *の特殊化はありません。これは単に文字配列へのポインタであるためです。

template< class T > struct hash<T*>; 

std::unordered_mapで使用されるものです。しかし、任意のポインタ型のための専門があります。単にアドレスをハッシュします。

---

単にデフォルトのハッシュ関数は、アドレスをハッシュするので、あなたのstd::unordered_mapとデフォルトのハッシュと平等が厄介であるにキーとしてconst char*を使用して、デフォルトの平等の機能は、アドレスを比較します。キーはconst char*であることから、

std::unordered_map<const char*, char*, MyCustomHash, MyCustomEquality> myMap; 

Answer 3

コードが正しく動作している：あなたはは他のあなたのような何かをする必要があり、あなたのキーのstd::stringを好む必要があります。 std::stringをキーとして、探している動作を取得してください。

ので：キーとして、ポインタを使用してstd::unordered_map<std::string, char*> myMap;

Answer 4

はなく、唯一の定数文字列のための解決策になる可能性 - ポインタが最も簡単かつ最速のハッシュです。異なるconst変数を使用して順序付けられていないマップを初期化し、その寿命が適切であることを確認することができます。

Answer 5

文字列またはメモリアドレスをハッシュしますか？

この質問は本当にアイデンティティ対について平等であり、あなたが「文字列」を言うときあなたは何を意味するかに依存します。

• 等価。std::stringクラスを意味する場合、ハッシングはメモリアドレスとは関係ありません。文字列の実際の内容はハッシュされます。 2つのstd::stringインスタンスが等しく、内容が等しい場合は同じハッシュが生成されます。

• アイデンティティ。メモリ内のいくつかの文字へのポインタを意味する場合、そこに保存されるデータにかかわらず、メモリアドレスはハッシュされます。 2つの「文字列」は同一であり、同じメモリ位置を指している場合は同じハッシュを生成します。

---

あなたは、文字列を扱うとき、あなたははほとんど常に平等比較をしたいし、同じデータを表す2つの異なる文字列インスタンスは、データがで住んでいる場合でも、等しいと見なされるべきであるため、std::stringを使用することをお勧めしますさまざまなメモリアドレスを持ち、std::stringは、ハッシュや単純比較（myStr1 == myStr2など）を使用して、それらのセマンティクスを常に提供します。 ^[*]

ハッシングchar const*またはchar*は、多くの実装定義の動作を実行するため、非常に危険です。文字列リテラルは、これの主要な例です。たとえば、次のプログラムを検討してください。

#include <iostream> 

int main() 
{ 
    char const *a = "foo"; 
    char const *b = "foo"; 

    std::cout << reinterpret_cast<void const*>(a) << "\n"; 
    std::cout << reinterpret_cast<void const*>(b) << "\n"; 
} 

C++標準では、アドレスが同一であるかどうかはわかりません。通常、コンパイラはこの動作を制御できます。たとえば、Visual C++には/GFフラグがあります。オンにすると、アドレスは同じになります。さもなければ、彼らはそうしません。

これは、ハッシュに対して非常に劇的な結果をもたらします。以下のプログラムでは、それは実装定義 1か2が印刷される。

#include <iostream> 
#include <unordered_map> 

int main() 
{ 
    char const *a = "foo"; 
    char const *b = "foo"; 

    std::unordered_map<char const*, char*> myMap; 
    myMap[a] = "1"; 
    myMap[b] = "2"; 

    std::cout << myMap.size() << "\n"; // prints 1 or 2 
} 

あなたのコードも実装定義された振る舞いをしています。ていないため、リテラルのが、別の方法で：

そしてstd::stringは別の領域のメモリのかに再割り当てするかどうか に依存して新しいキーが追加されているかどうか、以下の場合：

はい。 2つの異なるstd::stringインスタンスからc_str()ポインターを使用してはならず、std::stringインスタンスが等しいためにのみポインターが同一であると仮定してください。

文字列自体をハッシュする必要がある場合、この方法は遅くなりますか？

号私はあなたが実際に差を測定することができますのための現実的なユースケースを思い付くためにあなたに挑戦。それだけで "遅い"方法です。さもなければ、それは普通の早すぎる最適化です。

しかし、それ以上のことがあります。技術的には、1つのアドレスをハッシュすると、より多くのデータが含まれているため、文字列の内容全体（またはその大部分）を使用してハッシュ値を計算するよりも速くになるはずです。それはかなり明白です。しかし、私はあなたがの "高価な"計算を実行する必要性を見ることを確信していません。これに関連する魔法はありません。あなたのプログラムロジックが文字列の内容を気にするならば、個々の文字を考慮する必要があります。理論的には、読んでいないデータをハッシュすることはできますか？

もっと一般的には、持っていないものをハッシュする方法は？

---

^{[*] 偶然、この区別を考慮する障害は、Javaで非常に一般的なバグの同じ源である、すなわちstr1 == str2はstr1.equals(str2)は異なる意味を有します。}