ハッシュマップ挿入/探索の計算量 (Big-O)

ハッシュマップはハッシュ関数により挿入・探索・削除を期待値 O(1) で行います。多くのキーが衝突する最悪ケースは O(n)、空間は O(n) です。

主要データ

よくある質問

ハッシュマップ挿入の計算量は？

期待値 O(1)、衝突が多い最悪で O(n) です。

なぜ最悪 O(n) なのですか？

多くのキーが同じバケットに集まると線形走査に劣化するためです。

関連ページ

• HTTP 200 OK
• HTTP 301 Moved Permanently
• HTTP 401 Unauthorized
• HTTP 403 Forbidden
• HTTP 404 Not Found
• HTTP 429 Too Many Requests
• HTTP 500 Internal Server Error
• HTTP 502 Bad Gateway

Hash Map の計算量 は GOAT Lab の DevRef Hub の一部です。登録不要・オフラインでも使える無料リファレンスで、上のツールから任意の値を計算できます。

広告掲載

GOAT Lab の一部 — 科学・エンジニアリング・開発者向けの無料ブラウザツール26種。登録不要。