第29章へようこそ。
これまでに扱ったHashMapとHashSetには、共通する性質がありました。
内部はハッシュテーブルで、要素はハッシュ関数によって決まる位置に置かれる。
そのため、要素は挿入順にも整列順にも並ばず、イテレーションの順序は保証されない。
個々の操作はほぼ一定時間で動くが、順序にまつわる操作は構造的に難しい。
順序が必要な場面があります。
キーが範囲で問い合わされる場合。たとえば「ある日付以降のすべてのエントリ」「キーが10から20の間にあるもの」。
イテレーション順序が一定であることが望ましい場合。出力順を整えたい、結果を予測可能にしたい。
最小のキーや最大のキーを高速に取り出したい場合。
これらの場面のために用意されているのがBTreeMapとBTreeSetです。
役割はHashMapとHashSetと同じく、ペアの対応表と要素の集合。違うのは内部構造で、ハッシュテーブルではなくBツリーと呼ばれる木構造を使う。
今日扱うのは、Bツリーがどう順序を保つか、その代償は何か、求められるトレイトはなぜ変わるか、そして範囲クエリという固有の操作です。
感想
まだ感想はありません。最初の1件を書きましょう!
スクロール