time-complexity - 分離チェーンを使用したハッシュ テーブルの検索操作の時間計算量

Question

通常、ハッシュ テーブルでの検索操作の平均コストは O(1) であると言われています。これは、テーブル上の特定のリストの長さが負荷係数に比例するためです。私が得られないのは、負荷係数が保存するエントリの数に明らかに依存するため、必ずしも一定ではないということです。新しいエントリを頻繁に追加すると仮定すると、平均的なリストの長さはエントリの数にも依存しませんか? 操作 O(1) はどうですか?

私の英語でごめんなさい。それは私の主要な言語ではありません。

Answer 1

多くの実装では、テーブルのサイズを変更して、負荷係数が定数に制限されたままになるようにします。サイズ変更には、保存されているアイテムの数に比例して時間がかかりますが、頻繁に行われないとバランスが取れて、挿入に償却された一定の時間がかかります。