c++ - CMap - ハッシュテーブルのサイズよりも多くの要素をマップに追加するとどうなりますか?

Question

私の知る限り、CMap::InitHashTable要素がマップに追加される前にメソッドを呼び出す必要があります。つまり、最初の要素が CMap オブジェクトに追加された後は、ハッシュテーブルのサイズを変更できません。

また、MSDN から、To minimize collisions, the size should be roughly 20 percent larger than the largest anticipated data set.

私の質問は、デフォルトのハッシュテーブル サイズ (つまり 17) で CMap オブジェクトを作成し、(たとえば) 約 40 の要素を追加するとどうなるかということです。ここでは、2 つのキーが同様のハッシュを生成しないと想定しています。

Answer 1

ハッシュ テーブルがいっぱいになると、衝突が発生します。衝突するアイテムはリストに入れられ、検索する必要があります。すべてがまだ機能しますが、少し遅くなります。ハッシュ テーブルのサイズが適切で、ハッシュ関数がまともな場合、ハッシュ テーブルへの挿入と検索は一定時間で行われます。過剰なハッシュ テーブルでは、衝突の結果としてリストをたどらなければならないため、これらの時間が増加します。