0

ハッシュマップのBigOは次のようになっていることを示すリンクがたくさんあります。

get   O(1)
add   O(1)
contains O(1)
next item O(c / n)    c = table capacity (number of buckets) n = size

get / add / containsがO（1）である理由は明らかですが、繰り返しがO（c / n）である理由を知りたいと思います。

そして、私がそれに取り組んでいる間、BigOがConcurrentHashmapやTreeMapなどに何であるかを知りたいです。

誰かが良いリンクを手に入れましたか？

4

1 に答える 1

2

リンクされた論文は、反復がであるとは述べていませんO(c/n)。「次のエントリ」はO(c/n)です。反復は、nごとの「次のエントリ」です。

まず、これc (capacity) > n (entries)は不変であり、cはnの関数であることに注意してください。したがってO(c/n)> O(1/n)。（注：コメントによると、衝突解決にチェーンを使用するHashMap実装の不変条件についての私の主張について完全に確信しているわけではありません。）

つまり、これが効果的に言うのは、標準のHashMapでは、「次のエントリ」の実行中に表示される一部のバケットは空であり、スキップする必要があるということです。O(1/n)したがって、境界は「次のエントリ」の「以上」です。ただし、この境界を読み取るときは注意が必要です。これは、反復が多いほど速くなることを意味するものではなくn、エントリの総数という観点から「次のエントリ」の境界を表すだけnです。

反復は事実上すべてのnの「次のエントリ」であるため、HashMapの反復では次のようになります。

O(1/n * n) -> O(n)
O(c/n * n) -> c*O(n) -> ~O(n)

（これcは関数であるため、さまざまな状況で定数として引き出すと少し誤解を招く可能性があります。したがって、波線が発生しますn。）

于 2013-03-26T20:53:15.230 に答える