読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

unordered_map について

unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。

まとめ
  • 基本的にチェイン法っていうのでやってるっぽい
    • vector< list< T > > みたいのをイメージするとわかりやすい
詳細

まとめで書いたように, 基本的には vector< list< T > > というのが全部説明している気がします。

  • find() は平均計算量 O(1), 最悪計算量 O(n)
    • find() は, 基本的にはハッシュ値vector にランダムアクセスするだけで目的のものが見つかるので O(1) だが, ハッシュ値がかぶっているものがあると, vector の要素のリストを線形探索しないといけない。なので最悪 O(n)
  • insert(), delete() も平均計算量 O(1), 最悪計算量 O(n)
    • 結局消す, 入れる場所を探さないといけないので find() が必要になる(insert は後ろに追加すれば良くね, と思うかもですが既にキーが入っている可能性があるので調べる必要があります)。vector の各要素はリストなので, その中で insert や delete は O(1) で出来る

そんな感じで計算量についてはイメージできます。結局, 全部最悪計算量が O(n) なので, 競技プログラミングに限った話をすると, CodeForcesSRM のような, hack が出来るコンテスト, 最後まで AC かどうかがわからないコンテストでは使わないほうが無難です。逆に, AtCoder のように提出してすぐ AC かわかるコンテストでは, unordered_map がダメなら map に切り替える, とかできるので使っても良さそうです。
日常的には unordered_map のほうが map より高性能な気がするので unordered_map 一択なんですかね(適当)。

ただ, マジメに考えてみると, 「ホントに O(1) で出来るのか?」という疑問が湧いてきます。
それについては, このスライドがとてもわかりやすかったです。

www.slideshare.net
結局, 平均計算量が O(1) になるように, 裏でいろいろ頑張ってくれている, ということですね!ありがたい。

あ, あとここからは多分です。unordered_map は vector< list< T > > なので, vector のサイズを動的に変えているっぽい(それはスライドにも書いてある)んですが, 多分 vector の大きさは 2 倍ずつにしていけば全体的に見て insert() も O(1) で出来そうです。