std:map — 順序付きマップ (SortedMap) と挿入順マップ (InsertionMap)

標準ライブラリモジュール (index.md)。本書中の裸の §N は本書の節を指す。言語の意味論は ../language-spec.md を参照。

import m := "std:map" は 3 つの不透明なマップ型のコンストラクターを持つ namespace object を m に束縛する。3 者は「値をキーにできる」点は共通だが、反復順・キー同一性の基準・可変性が異なる:

• SortedMap (m.sorted.*) — キーの compare 昇順で反復する。キーは Comparable (language-spec.md §9.4) でなければならない。不変で、変更系メソッドは新値を返す。
• InsertionMap (m.insertion.*) — 挿入順で反復する。キーは == (構造的値等価、language-spec.md §9.1) で同一性判定し、Comparable である必要はない (任意の値をキーにできる)。不変で、変更系メソッドは新値を返す。
• ScratchMap (m.insertion.scratch() / m.insertion.build) — InsertionMap と同じキー同一性 (==) を持つが、内部状態が可変な scratch ハンドル。set/remove/update はハンドル自身を前進させ、frozen() で InsertionMap に確定する (§2.3)。

SortedMap と InsertionMap はキー照合が「順序」で決まるか「等価」で決まるかが本質的な違いで、命名もそれを表す (Sorted = compare 昇順・Insertion = 挿入順)。ScratchMap は反復順で言えば InsertionMap 側に属する — 可変な間も挿入順を保ち、確定後も挿入順のまま InsertionMap になる。3 者とも String 識別子に限らず、Int・Tuple・object などをキーにできる。

std:fs / std:term と違い I/O を伴わず、純粋・同期 (Future を返さない)。すべてのコンストラクター・メソッドは即値を返す。

import m := "std:map"

# --- SortedMap: キー compare 昇順 ---
t := m.sorted.of([(1, "a"), (3, "c"), (2, "b")])
t.get(2)        #> Some("b")
t.get(9)        #> None
t.has(3)        #> true
t.keys()        #> [1, 2, 3]            (compare 昇順)
t.length()      #> 3

# 非破壊。t は変わらない
t2 := t.insert(2, "B").remove(1)
t2.entries()    #> [(2, "B"), (3, "c")]
t.entries()     #> [(1, "a"), (2, "b"), (3, "c")]

# --- InsertionMap: 挿入順・任意キー ---
h := m.insertion.of([("class", "card"), ("data-id", "42")])
h.keys()        #> ["class", "data-id"]  (挿入順)
h.insert("class", "card selected").keys()   #> ["class", "data-id"]  (既存キーは位置維持)
h.insert("id", "x").keys()                  #> ["class", "data-id", "id"]  (新規キーは末尾)

# --- ScratchMap: 可変 scratch ハンドル・frozen() で InsertionMap に確定 ---
sc := m.insertion.scratch()
sc.set("class", "card").set("data-id", "42")
sc.get("class")   #> Some("card")
tbl := sc.frozen()   # tbl は InsertionMap。sc は以降使うと Error
tbl.keys()        #> ["class", "data-id"]  (挿入順を保ったまま確定)

以下では import m := "std:map" で束縛したものとして m.sorted.of / m.insertion.of / m.insertion.scratch 等で記す。

1. record との違いと 3 型の使い分け

キーで値を引く辞書は言語の値ではなく、このモジュールが提供する (language-spec.md §7.5)。オブジェクトのスロットは書いた時点で名前が決まっている record のフィールドであり、実行時のキーで引く手段は無い (language-spec.md §3.10 の動的アクセスは Sequence の添字専用)。フィールド名が静的に決まっている構造体は record を、キーが実行時に決まる／識別子として不正な文字を含むものは std:map を使う。

3 型は次のように分かれる:

キー昇順で反復したいか (SortedMap)・挿入順を保ちたいか (InsertionMap)・in-place で辞書更新したいか (ScratchMap) で使い分ける。ScratchMap は frozen() で InsertionMap に確定する (§2.3) — std:array の Array が List に対して立つのと同じ二段構えである。

2. キーの制約 — 同一性の基準

SortedMap と InsertionMap はキー同一性の基準が異なる。1 つのマップの中でどちらの基準を使うかは型で決まり、混在しない。ScratchMap は独自の基準を持たず InsertionMap と同じ == に従う (§2.3)。

2.1 SortedMap — Comparable と compare

• キーは Comparable (language-spec.md §9.4: Int・Float・String・Bool・Unit、compare を持つ不透明値型 (std:decimal の Decimal・std:time の各型)、compare スロットを持つ object) でなければならない。Bytes は原始型だが順序を持たないのでキーにできない (bytes で作った値を sorted のキーに渡すと静的検査が type-mismatch で報告する)。非 Comparable をキーに渡すと、その操作の呼び出し位置で Error (バグ層、language-spec.md §16)。sort と同じ規律。
• キーの同一性は compare で定める: 2 つのキー a, b は a.compare(b) == Equal のとき同一とみなす (== ではない)。順序付き構造として一貫させるための単一基準であり、== のオーバーロード (language-spec.md §9.1) とは独立する。型定義側で compare と == が食い違う場合、マップは compare のみに従う。
• 1 つのマップのキーは相互に比較可能でなければならない。異型キーの混在 (例: Int キーと String キー) は compare が異型比較で panic する (language-spec.md §9.4) ため、その時点で Error。実用上、1 マップのキーは単一の Comparable 型に揃える。
• Float をキーにする場合の順序は全順序 (total_cmp 相当、language-spec.md §9.4)。NaN にも定位置があるため壊れない。

2.2 InsertionMap — == と任意キー

• キーは == (構造的値等価、language-spec.md §9.1) で同一性判定する。Comparable である必要は無く、compare を持たない object もキーにできる。
• その == は構造だけで見る。 キーが == スロットや compare スロットを宣言していても、キー同一性はそれを呼ばない — SortedMap が compare を呼ぶのと非対称である。索引 (§8) はキーの内容からハッシュを取るので、宣言された等価を呼ぶと「等しいのにハッシュが違う」組を作れてしまい、索引が引き当てられなくなる。宣言した等価でキーをまとめたいときは SortedMap を使う (そちらはキーに compare を要求する)。値の側は普通の == で、宣言があればそれを呼ぶ (§6)。
• 値には制約なし (String・Bool・任意値)。
• キー同士は == で比較できれば十分で、異型キーの混在も == が false を返すだけで panic しない (SortedMap と異なり全順序を要求しないため)。

2.3 ScratchMap — ハンドルと確定

ScratchMap のキー同一性は §2.2 の InsertionMap と同じ == で、専用の制約は増えない。SortedMap/InsertionMap が値そのものであるのに対し、ScratchMap は std:array の Array (array.md §2) と対称の可変 scratch ハンドルである点が異なる。ScratchMap は値型ではないため ==/compare/Comparable を持たず、std:map/std:set のキーや要素にできない (Array について array.md §2 が述べるのと同じ理由)。比較したい/持ち回りたい結果は frozen() で InsertionMap に確定する。

ScratchMap は非 Copyable、SortedMap / InsertionMap はCopyable である (../language-spec.md の複製の節)。分かれ目は可変性で、ScratchMap は内部状態が可変なので作り直しても同じものにならず、copy は panic し spawn / std:parallel の捕獲検査も弾く。確定先の InsertionMap は不変な値なので複製できる。

ScratchMap はAtMostOnce の多重度型である (../language-spec.md の多重度型の節)。frozen が Consuming メソッドで、set / get / remove / update / length は借用である。SortedMap / InsertionMap は不変な値なので多重度を持たない。

ハンドル h の束縛自体は immutable (h = other は再代入エラー)。可変なのは h が指す内部状態 (挿入順のエントリ列とキー索引、§8) だけで、set/remove/update がそれを前進させる。これは Array (array.md §2) や std:random のジェネレーター (random.md §1) と同じ規律で、新しい束縛セマンティクスを増やさない。

h.frozen() は内部状態を InsertionMap に確定して返す (§4)。確定と同時にハンドルは封印 (seal) される — 以降 h のどのメソッドを呼んでも Error。ハンドルの漏れを静的に禁ずるにはランク 2 の多相が要るが、Hikari は higher-rank 多相を持たない (language-spec.md §17.2) ためこれを再現できない。代わりに frozen で封印し、封印後の使用を実行時エラーにする (array.md §2.1 と同じ動的規律)。

h := m.insertion.scratch()
h.set("a", 1)
tbl := h.frozen()  # tbl は InsertionMap。h は封印される
h.get "a"  #> Error (use after frozen)
tbl.get("a")  #> Some(1)

3. namespace とコンストラクター

import m := "std:map" で得られる closed namespace は、sorted / insertion の 2 つのサブ namespace object をそれぞれ slot に持つ (2 型で of/empty が衝突するための分離):

of(pairs): pairs が非 List・要素が非 2-Tuple・(sorted のみ) キーが非 Comparable のとき Error。キー重複は後勝ち (last-wins)。insertion.of の後勝ちは位置維持 (§4 の insert と同じ規律: 先に現れたキーの位置はそのまま、値だけ最後に現れたもので上書き)。

scratch/build を sorted ではなく insertion に置くのは、sorted/insertion の分岐軸が反復順 (§1) であり、ScratchMap が frozen() で確定する先は挿入順の InsertionMap だからである。sorted 側に対応物を置かないのは、今のところ確定先が InsertionMap の 1 種類しか要らないためで (YAGNI)、compare 順を保ったまま可変更新する需要が出れば独立に追加できる。

scratch が値スロットではなく呼び出しなのは、呼ぶたびに独立した内部状態を持つ別のハンドルが要るためである (insertion.empty が値スロットで済むのは、InsertionMap が不変で使い回しても安全だから)。

insertion.build は「ハンドルを作りブロックへ渡して frozen() する」を 1 呼び出しにまとめた安全形で、ハンドルが外へ漏れず、凍結し忘れがない。次のコードはおおよそ同じ効果を持つ展開形である:

h := m.insertion.scratch()
({ h | body })(h)
h.frozen()

insertion.build のブロックパラメーター（h）の型は Borrowed(ScratchMap(k, v)) である（language-spec.md §17.8）。build 自身が最後に呼ぶ frozen() の対象を失わせないためである。

この借用の規律は注釈の有無を問わず静的検査に働く。build の宣言型が持つブロックパラメーターの型が、注釈の無いパラメーターへ流れるためである（static-analysis.md §2「注釈の無いブロックパラメーターへ型を流す」）。h を束縛・コンテナーへ格納・別フローへ捕獲すると cannot-bind-borrowed（static-analysis.md §2.14）になる。実行時の封印（§2.3）はこれとは独立に等しく効く。

m.insertion.build { h: Borrowed(m.ScratchMap(String, Int)) | keep := h }  # cannot-bind-borrowed
m.insertion.build { h | keep := h }                          # 同じく cannot-bind-borrowed

SortedMap / InsertionMap / ScratchMap 型は std:map の型メンバーとして export され、型注釈に書ける (language-spec.md §13 のモジュール型 export、time.md §1 と対称)。namespace 名 (sorted/insertion) とは独立にフラットに置かれる: x: m.SortedMap(Int, String) / y: m.InsertionMap(String, Int) / z: m.ScratchMap(String, Int) と修飾参照するか、import { SortedMap, InsertionMap, ScratchMap } := "std:map" で取り出して x: SortedMap(Int, String) と書く。3 者とも不透明型であり内部表現は露出しない (生成は本節のコンストラクター・insert/set 等の派生のみ)。

3.1 型引数 — キー型と値型

3 者はキー型 k と値型 v の 2 つの型引数を持つ型構築子である (language-spec.md §17.2 の List(T) / Option(T) と同じ形): SortedMap(k, v) / InsertionMap(k, v) / ScratchMap(k, v)。get の結果は Option(v)、keys() は List(k)、entries() は List((k, v)) になり、取り出した値に注釈を書き足す必要が無い (§4.2 のシグネチャ表)。

• 型引数は省略できない。 x: m.InsertionMap は List を裸で書いたときと同じく type-arity-mismatch (static-analysis.md §2)。要素型を問わない位置は InsertionMap(String, Any) と明示で Any を書く (static-analysis.md §2.5 の「暗黙 Any の禁止」と同じ規律で、書き手が Any を書いた位置だけが gradual 境界になる)。
• 要素型は of の引数から決まる。 m.insertion.of [("a", 1)] は InsertionMap(String, Int)。sorted.empty / insertion.empty は [] が List(Never) であるのと同じく要素型 Never の空の値で、注釈や最初の insert / merge で確定する。scratch() / build は要素型を引数から取れないので、束縛注釈などの期待型があればそれを要素型にし、無ければ Any になる (無注釈の束縛は implicit-any-binding が注釈を求める。array.md §3 の collect と同じ規律)。build では期待型がブロックパラメーター h: Borrowed(ScratchMap(k, v)) へ流れ、h.set の引数がその型で検査される。
• 変性: SortedMap / InsertionMap は不変な値で要素を差し替える経路が無いので、k / v とも共変 (List(T) の要素型と同じ。language-spec.md §17.2)。ScratchMap は set / update がキーと値を書き込むので k / v とも不変 (invariant) — ScratchMap(String, Int) の値は ScratchMap(String, Any) の位置に通らない (static-analysis.md §2.10「可変コンテナー位置の不変性」)。
• キーの Comparable 境界はシグネチャに置く。 型構築子 SortedMap(k, v) そのものの k は無境界である (境界付き型変数は関数型の中でだけ意味を持つ。language-spec.md §17.2)。境界は k を取るシグネチャが持つ — sorted.of の引数と、get / has / insert / remove / merge / compare の受け手 (§4.2)。確実に非 Comparable な型 (List・Tuple・enum のタグ・compare を持たない不透明型) をキーにすると、その位置で type-mismatch (static-analysis.md §3.2 の非充足)。record と関数は幅部分型ゆえ静的には「不明」で素通しし、§2.1 の実行時 Error が backstop になる。InsertionMap / ScratchMap の k は無境界。
• 実行時の照合は List(T) と同じで、注釈位置ではキーと値を走査して照合する。静的に確実な位置は型消去 (../language-spec.md §17) が照合を消す。

m.sorted.empty.length()              #> 0
m.sorted.of([])                      #> (空 SortedMap)
m.sorted.of([(1, "a"), (1, "b")])    # キー 1 は後勝ち → { 1: "b" }

m.insertion.empty.length()                     #> 0
m.insertion.of([("a", 1), ("b", 2), ("a", 9)])  # キー "a" は位置維持で値だけ後勝ち → 挿入順 [("a", 9), ("b", 2)]

m.insertion.scratch().length()                 #> 0
(m.insertion.build { h | h.set("x", 1) }).keys()  #> ["x"]

4. メソッド

SortedMap・InsertionMap は同じメソッド顔を持つ。両者の値 t に生えるメソッドはすべて非破壊で、変更系は同じ型の新しい値を返す (元の t は不変)。違いは反復順だけ (sorted = キー昇順 / insertion = 挿入順) だが、いくつかのメソッドは反復順が意味に絡むため注記する。

length / is_empty / keys / values / entries / first / last / to_list は zero-arg のため t.length! のように ! 形でも書ける (prelude.md の呼び出し糖衣)。

t := m.sorted.of([(1, "a"), (2, "b"), (3, "c")])
(t.map { k, v | v + "!" }).entries()     #> [(1, "a!"), (2, "b!"), (3, "c!")]
(t.filter { k, v | k > 1 }).keys()       #> [2, 3]
t.fold(0) { acc, k, v | acc + k }        #> 6        (キーの和)
t.each { k, v | print(k.inspect! + "=" + v) }     # 1=a / 2=b / 3=c

h := m.insertion.of([("b", 2), ("a", 1)])
h.keys()                                 #> ["b", "a"]         (挿入順)
(h.map { k, v | v * 10 }).entries()      #> [("b", 20), ("a", 10)]   (挿入順を保つ)
(h.filter { k, v | v > 1 }).keys()       #> ["b"]

# Option との合成 (不在の既定値)
t.get(9).or("?")                       #> "?"

4.1 ScratchMap のメソッド

ScratchMap は可変ハンドルであり、§4 冒頭の表 (SortedMap/InsertionMap 共通・すべて非破壊) とは別の表を持つ。ハンドル h に生えるメソッドのうち set/remove/update は内部状態を破壊的に更新する (新しいハンドルは作らない)。すべて封印後 (frozen() 済み、§2.3) は Error。

get が Option を返すのは、Array の範囲外添字が呼び出し側のバグとして Error になる (array.md §6) のと違い、ScratchMap ではキーの不在が正常な状態だからである。update が init を取るのは、キーの有無を問わず read-modify-write を 1 呼び出しで書けるようにするためで (不在なら init をブロックへ渡す)、これが無いと has で分岐してから set/update する 2 段構えが必要で、置き換え元の破壊的コードよりかえって冗長になる。

length / keys / frozen は zero-arg のため h.length! のように ! 形でも書ける (prelude.md の呼び出し糖衣)。ScratchMap は merge/map/filter/fold/values/entries/first/last/each/compare を持たない — これらの非破壊系メソッドが要るときは frozen() で InsertionMap に確定してから使う。

set / remove / update の戻りが所有ではなく借用 (Borrowed(ScratchMap)) なのは、これらが受け手を消費しないためである。所有を返すと、消費されていない受け手と合わせて同じ内部状態への経路が 2 本になる (../language-spec.md の多重度型の節)。連鎖 (h.set("a", 1).set("b", 2)) はそのまま書ける一方、戻りを別の名前に束縛したりコンテナーへ入れたり別フローへ捕獲したりすると cannot-bind-borrowed (static-analysis.md §2.14) になる。

h := m.insertion.scratch()
h.set("a", 1).set("b", 2).update("a", 0) { v | v + 10 }
h.get("a")     #> Some(11)
h.get("z")     #> None
h.has("b")     #> true
h.remove("a")
h.keys!        #> ["b"]
tbl := h.frozen()   # tbl は InsertionMap { "b": 2 }。h は以降 Error

4.2 静的なシグネチャ

受け手の型引数 k / v に対する各メソッドの静的型 (hover に出る形。static-analysis.md §2.2 のとおり実引数の照合はこの型に対して行う)。M は受け手と同じ型構築子 (SortedMap または InsertionMap)、w は map のブロックの結果型、acc は fold の初期値の型から確定する。

SortedMap の k を取る位置には Comparable 境界が付く — 表の k は SortedMap では (k: Comparable) と読む (sorted.of の引数、get / has / insert / remove の第 1 引数、merge / compare の引数の SortedMap(k, v)。hover にはこの形で出る)。受け手の k が確実に非 Comparable なら、これらの呼び出しは受け手の型引数で落ちる:

x: m.SortedMap(List(Int), String) := m.sorted.empty
x.insert([1], "a")   # type mismatch: receiver of insert expects SortedMap((k: Comparable), v), got SortedMap(List(Int), String)
x.length!           # 鳴らない — キーを比べないメソッドは境界を見ない

k を比べない length / is_empty / keys / values / entries / first / last / each / map / filter / fold は鳴らない (キーを渡さない限り、非 Comparable のキー型で注釈した空の map はエラーではない)。InsertionMap / ScratchMap の k は無境界。

ScratchMap の set / update は受け手を破壊的に書き換えるので、引数の値の型が受け手の v と確実に非整合なら静的検査が報告する (static-analysis.md §2.10「可変な器への書き込みの要素型照合」。List の push と同じ契約系の規則)。不変な insert / merge にこの規則は無く、引数の型が受け手の型引数と割れた呼び出しの結果型は単一化の規則 (static-analysis.md §3.1) に従って Any 側へ倒れる。

5. merge (マージ)

t.merge(other) は 2 つの同じ型の値をマージした新値を返す。同一キーは 右 (other) が勝つ。language-spec.md §7.4.1 の object マージ (スロットは右勝ち) と同じ意味論。

• 演算子 + はオーバーロードしない (time.md §1 と同方針 — 不透明値型は演算子を増やさず名前付きメソッドで操作する)。マージは merge で行う。
• other が同じ型 (SortedMap 同士・InsertionMap 同士) でなければ Error (型混在は不可)。
• SortedMap: 結果のキーは両者の和で、compare 昇順を保つ。
• InsertionMap: 結果の順序は左 (t) の並びを保ち、右 (other) にしかない新規キーを末尾に追記する。左右の両方にあるキーは左の位置を維持したまま値だけ右のもので上書きされる (insert の位置維持規律と同じ)。

a := m.sorted.of([(1, "a"), (2, "b")])
b := m.sorted.of([(2, "B"), (3, "c")])
a.merge(b).entries()   #> [(1, "a"), (2, "B"), (3, "c")]    (キー 2 は右勝ち)

ha := m.insertion.of([("a", 1), ("b", 2)])
hb := m.insertion.of([("b", 20), ("c", 3)])
ha.merge(hb).entries()   #> [("a", 1), ("b", 20), ("c", 3)]  (左の順を保ち、"b" は右の値・"c" は末尾追記)

6. 等価と順序 (== / compare)

SortedMap・InsertionMap はどちらも 値等価を持つ (time.md §1 の不透明値型と同じ方針)。core の object マップ (String 名キー) と違い、任意の値をキーにとれるのが特徴だが、順序 (compare) を持つのは SortedMap だけ。

• SortedMap:
• ==: t1 == t2 は、キー集合が一致 (compare 同一) し、かつ各キーの値が == (language-spec.md §9.1) で等しいとき true。別インスタンスでも内容が同じなら true (構築順に依らない)。
• compare: エントリをキー昇順に並べた列の辞書式順序で Ordering を返す。< <= > >= がこれを経由して効き、SortedMap を別の SortedMap/OrderedSet のキー/要素にネストできる (集合演算・マップのキーは内部でこの compare を使う)。値の比較は値が Comparable なときのみ意味を持ち、非 Comparable 値を含む compare は呼び出し位置で Error。
• InsertionMap:
• == は順序非感応: 同じ (key, value) 集合であれば、挿入順が異なっていても true。順序 (反復順) は同一性に一切関与しない。キーの突き合わせは §2.2 のキー同一性 (構造のみ) で、値の突き合わせは普通の == (宣言があればそれを呼ぶ) である。
• compare を持たない。InsertionMap は全順序を持つ必要が無く (v matches Comparable は false)、< <= > >= は使えない (呼び出せば universal method 不在として静的検査で弾かれる)。並び (挿入順) を検査したいときは == ではなく entries!/keys! (List・順序感応) を使う。

m.sorted.of([(1, "a"), (2, "b")]) == m.sorted.of([(2, "b"), (1, "a")])   #> true   (順不同で構築しても同値)
m.sorted.of([("a", 1)]) == { a := 1 |}                                   #> false  (object マップとは別物)

a := m.insertion.of([("class", "card"), ("id", "x")])
b := m.insertion.of([("id", "x"), ("class", "card")])
a == b            #> true                          （中身一致・並び無視）
a.entries!        #> [("class", "card"), ("id", "x")]  （並びは entries で見る）
b.entries!        #> [("id", "x"), ("class", "card")]

7. エラーモデル

std:map は 2 層を使い分ける (math.md §6・json.md §5 と同じ規律)。

1. Option を返す: get (SortedMap/InsertionMap/ScratchMap 共通) / first / last。不在は None (language-spec.md §9.2「不在は Option」)。
2. Error (バグ層、language-spec.md §16): プログラムのバグなので呼び出し位置で停止する。
• (SortedMap のみ) キーが 非 Comparable (compare を持たない object など)
• (SortedMap のみ) 1 つのマップ内で 異型キーを混在 (compare の異型比較が panic、language-spec.md §9.4)
• of に 非 List / 要素が 2-Tuple でないものを渡す
• merge の相手が 同じ型でない (SortedMap に InsertionMap を渡す等)
• (SortedMap のみ) compare を 非 Comparable な値を含むマップに適用
• (ScratchMap のみ) 封印後 (frozen() 済み、§2.3) のハンドルへの任意のメソッド呼び出し

回復可能な「キーが無い」(get/has) と、バグ層の「そもそもキーにできない型」(panic、SortedMap のみ) は層が異なる。InsertionMap はキーが Comparable である必要が無いため、キー型に起因する Error は起きない。ScratchMap の get も不在を None で表す (§4.1) 一方、封印後の使用は状態そのものが失われた呼び出し側のバグなので Error になる。

8. 計算量

• SortedMap: compare 昇順に保った不変 slice で実装する (コピーオンライト)。要素数 n に対し:
• get / has: O(log n) (二分探索)
• first / last: O(1) (先頭・末尾への直接添字アクセス)
• insert / remove: O(n) (不変ゆえ slice をコピー)
• keys / values / entries / each / map / filter / fold / to_list: O(n)
• merge: O(m log n + (n+m)) 程度 (m は相手の要素数)
• InsertionMap: 挿入順を保つ不変 slice で実装する (コピーオンライト)。要素数 n に対し:
• get / has: O(n) (線形探索。索引は持たない — 不変なので索引を持ち回れず、1 回引くために組めば組む側が O(n) かかって釣り合わない)
• first / last: O(1) (先頭・末尾への直接添字アクセス)
• insert / remove: O(n)
• keys / values / entries / each / map / filter / fold / to_list: O(n)
• of: O(n) (n は渡した対の数。後勝ちの畳み込みに使い捨ての索引を組む)
• merge: O(n+m) 程度 (m は相手の要素数。同じく使い捨ての索引で引く)
• ==: O(n) 程度 (§6 の順序非感応な値等価。同じく使い捨ての索引で引く)
• ScratchMap: 挿入順 slice ＋ キー索引で実装する (可変)。要素数 n に対し:
• get / set / has / update: O(1) (索引でスロットへ直接アクセス。ただし下記「索引に載るキー」の限定が付く)
• remove: O(n) (挿入順の列から詰めるので後続の位置がずれ、索引が持つ位置も直す)
• keys: O(n)
• frozen: O(n) (内部状態を InsertionMap へ確定。索引は引き継がない — 確定先は不変で、insert/remove のたびに作り直すことになるため)

SortedMap がハッシュではなく順序 (compare) を採るのは、Hikari が既に compare/Comparable を持ち Hashable を持たないこと、反復順を決定的にできることによる。insert/remove を O(log n) にする平衡木への置き換えは内部実装の最適化余地 (外部契約は変わらない)。

InsertionMap の get が O(n) のままなのに対し ScratchMap の get/set が O(1) になるのは、両者とも索引の要る == キーを持つ点は同じでも、InsertionMap は不変ゆえコピーオンライトで索引を都度作り直すコストを避けているのに対し、ScratchMap は可変ゆえ索引を持ち回ったまま更新できるという違いによる。of/merge/== だけが O(n) 系に乗るのは、これらが1 回の呼び出しの中で何度も引くからで、そこでは組む O(n) を引く回数で割れる。1 回しか引かない get/has では割れない。

索引に載るキー

索引はキーの内容から引く。一方 == の同一性も値の中身で決まるので、中身が後から変わりうる値は索引に載せられない — 載せた時点の内容と実態が食い違い、同じキーで引き直せなくなる。そこでキーを 2 つに分け、載せられるものだけを索引に載せる。

• 索引に載るキー — 中身の変わりえない値。原始型 (Unit・Bool・Int・Float・String・Bytes・Decimal・時刻の各型)・Tuple・variant・および それらだけを含む List がこれにあたる。同一性が箱の参照で決まる値 (Range ほか) も、参照は変わらないので載る。
• 索引に載らないキー — 可変スロットを持ちうる object と、内容の同一性が別の規則で決まる値 (InsertionMap・SortedMap・OrderedSet・型値)。これらは位置だけを別の短い列で持ち、線形に突き合わせる。

この 2 つは == で交わらない — 載るキーと載らないキーが等しくなることは無い。したがって探すキーがどちらに属するかで見る先が一意に決まり、索引が「外れて全件走査に落ちる」ことは無い。載らないキーをいくつ格納しても、載るキーの get/set/has/update は O(1) のままである。比例するのは載らないキーでの操作だけで、その本数 (要素数 n ではない) に比例する。

要素数が少ないうちは索引を持たず全件走査する。索引を引く費用 (キーの内容をたどる) が走査より高くつく範囲があるためで、境目の要素数は実装が決める。

この限定はすべて速度だけの話で、返す答えは常に InsertionMap と一致する。 どのキーを使っても同一性の判定結果は変わらない。