100万アイテムのハッシュテーブルと100アイテムのハッシュテーブルのパフォーマンスはどのように異なるのですか

Question

ハッシュテーブルのパフォーマンスに問題があることは知っていますが、100万アイテムのハッシュテーブルは100アイテムのハッシュテーブルより速くなります。

Answer 1

これは、使用されるハッシュアルゴリズムの効率によって異なります。

小さなマップには多くの衝突があり、大きなマップには衝突がない場合は、大きなものが速くなります。

について初期容量と負荷率を学ぶためにHashMap javadocを読んで、ハッシュコード（Object.hashCode()で始まる）について読みました。 （Hashtableは古代遺物であるdon't use itです）

Answer 2

すべてが衝突の数に依存します：100万アイテムのハッシュテーブルに全く衝突がない場合、100個のアイテムと100個のものよりはるかに高速です衝突。

衝突がない場合は、ハッシュキーとモジュロ（完全なハッシュを参照）を使用するだけで、検索はO（1）になります。衝突の場合（配列としてのハッシュテーブルとリンクがリンクリストにチェーンされていると仮定します）、問題のアイテムを見つけるまでそれらをすべて順番に辿る必要があります。最悪の場合は100％の衝突率です（つまり、 O（n）になります。