質問: なぜstd :: mapはツリーベースであるのに対し、pythonのdictはハッシュテーブルとして実装されていますか? なぜ1つの言語がツリーを使用し、別の言語が一見類似したデータ構造のためにハッシュテーブルを使用するのか? C ++のマップとPythonのdict 関連する質問は、ハッシュテーブルのパフォーマンスに関するものです。 下記のハッシュテーブルの理解に感謝してください。 ツリーにはO(log n)があることが保証されています。 ハッシュテーブルは、衝突の可能性があるため入力が以前に分かっていない限り保証されません。 問題サイズが大きくなるにつれて、ハッシュテーブルのパフォーマンスはO(n)に近づくと思う傾向があります。 なぜなら、問題サイズが大きくなるにつれてテーブルサイズを動的に調整するハッシュ関数について聞いたことがないからです。 したがって、ハッシュテーブルは特定の範囲の問題サイズにのみ役立ちます。そのため、ほとんどのDBはハッシュテーブルよりもツリーを使用しています。
回答: 新しいC ++標準には、 `std :: unordered_map` 型のがあります。ハッシュテーブル。 IIRCはこれまでの標準にも入りたいと思っていましたが、議論の中で十分な時間がなかったので省略されました。しかし、ほとんどの一般的なコンパイラは何年も何らかの形でそれを提供していました。 言い換えれば、あまり心配しないでください。手元のタスクに適切なデータ構造を使用してください。 ハッシュテーブルについての理解は、不正確です。 > テーブルを動的に調整するハッシュ関数について聞いたことがありません > 問題のサイズが大きくなるにつれてサイズが大きくなる > > すべての深刻なハッシュテーブルの実装は、より大きな配列を割り当て、すべてのキーを再ハッシュすることによって、入力を増やすために動的に調整します。この操作は高価ですが、(まれにしか実行されないように)正しく設計されていれば、パフォーマンスはまだ償却されます(O)。