競技プログラミング

JavaのTreeMapについて

ドキュメントを読んでもスッと理解できなかったので軽くまとめておきます。お気持ちが伝われば。

TreeMapとは

ナビゲーションメソッドが使えるマップ(連想配列)です…といって理解できたら苦労しないですね。もう少し説明しましょう。

連想配列というのはキーと値を紐づけるものです。”satake”は22みたいな感じですね。

この連想配列はハッシュを用いて実装するとだいたい挿入や削除、検索などがO(1)で動いて嬉しい!となります。ただハッシュには順列がありません。1より2が大きいみたいなことはハッシュマップには関係ありません。

それが嫌なのでソートされたマップというのを考えたくなります。それがSortedMapです。これはインターフェイスとして定義されています。

その実装としてナビゲーションメソッドを追加したものがTreeMapです。ナビゲーションメソッドというのは「vと一致するキー」「v以下で一番大きいキー」とかを探せる方法のことらしいです。関数ですね。

実装

赤黒木で実装されています。つまり挿入や削除や検索はもちろん、ナビゲーションメソッドも全てO(log n)かかります。順序のために検索などの性能は落ちていることに注意です。

参考