私は Java コレクションのパフォーマンス特性、Big O 表記法、複雑さなどを研究しています。現実世界の部分について理解できない部分があり、それが HashMap やその他のハッシュ コンテナーが O(1) と見なされる理由です。 1,000 エントリ テーブルのキーによるエントリの検索には、1,000,000 エントリ テーブルとほぼ同じ時間がかかるはずです。
名と姓のキーで格納された HashMap myHashMap があるとします。myHashMap.get("FredFlinstone") を呼び出した場合、Fred Flinstone の Person オブジェクトを即座に見つけるにはどうすればよいでしょうか? オブジェクトへのポインターを見つけるために、HashMap に格納されている一連のキーを反復処理する必要がないのはどうしてでしょうか? HashMap に 1,000,000 のエントリがあった場合、キーのリストも 1,000,000 の長さになり (衝突がないと仮定して)、並べ替えられたとしても、1.000 のリストよりも時間がかかるはずです。では、n によって get() または containsKey() の時間が変わらないのはなぜでしょうか?
注: 私の質問はJava ハッシュマップは本当に O(1) ですか?で答えられると思いました。しかし、答えはこの点に実際には対処していませんでした。私の質問も衝突に関するものではありません。