algorithm - ハッシュテーブル：検索と後継時間の複雑さ

Question

スキーナのアルゴリズム設計の本では、ハッシュテーブルが最大mバケットを持つことができ、要素の総数がであるとnすると、次のような最悪の場合の時間計算量が観察されます。

探す：O(n)

後継：O(n + m)

なぜ2つが違うのですか？次の要素を検索するという意味でも後継者を見つけることはありませんか？

Answer 1

ハッシュは、順序を破壊することを犠牲にして、一定時間の検索を実現します。要素を検索するときは、その要素をハッシュして（O(1)）、選択したバケットを調べます（O(n)他のすべてのバケットが空である可能性があるため、線形スキャンの場合、最悪の場合）。

特定の要素の次の要素が必要な場合、それが同じバケットに含まれるという保証はありません。実際、私はそれがどこにあるのか全く知りません。後継者がまだ何であるかわからないので、そのバケットを見つけるためにそれをハッシュすることはできません。代わりに、私は各バケットを調べることを余儀なくされています（O(m)。）

バケットをスキャンするときにアイテムを順番にプローブすると、アイテムの数（）で合計線形作業も実行することになりO(n)ます。これにより、全体の複雑さが。になりO(n + m)ます。