文字列内部表現（イミュータブル・インターン・SSO）

文字列は「ただのバイト列」ではない

ソースコード上では "hello" は素朴な文字の並びに見えますが、処理系の内部では、文字データ本体に加えて長さ・容量・参照カウントやハッシュ値・エンコーディング情報などを束ねた構造体として表現されます。同じ「文字列型」でも、言語によってこの構造体の中身と方針はまるで違います。可変か不変か、コピーをいつ作るか、短い文字列をどこに置くか——この設計選択が、== の速さ、連結の計算量、メモリ使用量を決めます。

文字列の中身がコードポイントとバイト列の二段の写像であること自体は「文字コードとUnicodeの内部」で扱った通りで、本稿はその「容れ物」側、つまり処理系がメモリ上にどう置くかを掘り下げます。

イミュータブル文字列とコピーオンライト

Java・C#・Python・JavaScript・Go など多くの言語で、文字列は**イミュータブル（不変）**です。一度作った文字列の中身は書き換えられず、変更したい場合は新しい文字列を作ります。不変にする理由は、不変性一般の利点（「イミュータビリティ」参照）に文字列特有の事情が加わるからです。

• 安全な共有 — 中身が変わらないので、同じ実体を複数の変数・スレッドが参照しても破壊されない。防御的コピーが不要になる。
• ハッシュ値のキャッシュ — 内容が固定なのでハッシュ値を一度計算して構造体に保持できる。文字列キーの辞書（ハッシュテーブル）で再ハッシュを避けられる。
• 部分文字列の共有（実装次第） — 元の文字データを共有し、オフセットと長さだけ持つ「ビュー」を返せる。

**コピーオンライト（COW）**は、不変の見た目を保ちつつコピーを遅らせる手法です。代入時はデータ本体を共有（参照カウントを増やすだけ）し、いずれかが書き換えようとした瞬間に初めて実体を複製します。読み取りだけなら一度もコピーが起きません。

連結の罠——不変ゆえの二乗コスト

不変文字列の最大の落とし穴が繰り返し連結です。s = s + x は毎回「長さ len(s)+len(x) の新文字列を確保し、両方をコピーする」ため、ループでn回連結すると総コストは 1+2+...+n、すなわち O(n²) に膨らみます。

# アンチパターン：n回の連結で O(n^2)
s = ""
for x in parts:
    s = s + x            # 毎回全体をコピーして作り直す

# 正攻法：可変バッファに溜めて最後に一度だけ確定
buf = []
for x in parts:
    buf.append(x)        # 追記は償却 O(1)
s = "".join(buf)         # 連結は一度きり O(n)

このため各言語は可変文字列バッファを別に用意します。Javaの StringBuilder、C#の StringBuilder、Goの strings.Builder がそれで、内部に伸長可能な配列（容量を倍々に増やす動的配列）を持ち、追記を**償却O(1)**で行います。償却コストの考え方自体は「償却計算量」と同じく、たまの再確保コストを多数の安価な追記でならす発想です。

文字列インターン

インターン（interning）は、同一内容の文字列をプログラム全体でただ1個のインスタンスに正規化する仕組みです。インターン済みプール（ハッシュテーブル）に同じ内容があればそれを返し、なければ登録します。狙いは二つです。

• 等値比較の高速化 — 同じ内容が必ず同じアドレスになるので、equals（中身の逐文字比較、最悪O(n)）の代わりに**ポインタ比較（O(1)）**で判定できる。
• メモリ削減 — 重複する文字列を1個に畳み込む。識別子・キー・列挙値のように同じ語が大量に現れる場面で効く。

String a = "tech";              // リテラルは自動でインターンされる
String b = new String("tech");  // newは別インスタンス（プール外）
String c = b.intern();          // 明示的にプールの代表を取得

a == b      // false（参照が違う）
a == c      // true （cはインターン済み代表＝aと同一参照）
a.equals(b) // true （内容比較なら当然一致）

多くの言語がコンパイル時の文字列リテラルを自動インターンします（Java・C#・Pythonの一部リテラル）。一方で実行時に生成した文字列まで無条件にインターンすると問題が生じます。

== がポインタ比較になる前提は、ハッシュテーブルのキー設計とも噛み合います。等値が速いキーは探索の定数項を縮めるからで、この発想は「ハッシュテーブルの内部実装」のキー比較コストと地続きです。

小文字列最適化（SSO）

文字列を素直にヒープ上の配列で持つと、"id" のような数文字の文字列でもヒープ確保（malloc）とポインタ間接参照が発生します。短い文字列が大量に飛び交うプログラムでは、この確保コストとキャッシュミスが効いてきます。

小文字列最適化（SSO, Small String Optimization）は、短い文字列をヒープに置かず、文字列オブジェクト本体の領域に直接埋め込む手法です。std::string は典型的に「ポインタ＋長さ＋容量」で24バイト程度を占めますが、SSOではこの領域そのものを文字バッファとして流用し、しきい値（libstdc++で15バイト、MSVCで15バイト程度）以下ならヒープ確保ゼロで済ませます。

通常（ヒープ）の string レイアウト          SSO で短い文字列を埋め込んだ場合
+----------+----------+----------+          +------------------------------+
| ptr ─────┼─→ heap   | len | cap |          | "id\0..." を本体に直接格納  |
+----------+----------+----------+          +------------------------------+
  間接参照あり・malloc あり                    間接参照なし・malloc なし

SSOがメモリ局所性を改善するのは、文字データがオブジェクトと同じキャッシュラインに乗り、ポインタ追跡（pointer chasing）が消えるからです。この効きどころは「メモリレイアウトとキャッシュ局所性」のキャッシュラインの議論そのものです。判定は文字列ごとに「埋め込みかヒープか」を分岐するため、わずかな分岐コストと引き換えに確保コストを消す設計といえます。

ロープ——長文字列を木で持つ

ふつうの連続配列表現は、先頭付近への挿入・削除・連結が苦手です。長さnの配列の途中に文字を挿入すると、後続を全部ずらすO(n)が発生します。テキストエディタのバッファのように巨大な文字列へ頻繁に編集を加える場面では、これが致命的になります。

ロープ（rope）は、文字列を二分木の葉に短い断片として分割保持するデータ構造です。内部ノードは左部分木の長さ（重み）を持ち、これを使って「i番目の文字」を**O(log n)で辿れます。連結は2本のロープを新しい根の下にぶら下げるだけ、挿入・分割も木の組み替えで済むため、いずれもO(log n)**になります。

代償は、ランダムアクセスがO(1)でなくなること、ノードがメモリ上に散在してキャッシュ局所性が落ちること、実装が複雑になることです。木構造で重みを持ちlog nで辿る発想は「平衡木」と共通で、ロープは「重み付き平衡木の文字列版」と捉えると見通しが良くなります。

まとめ

文字列は内部的に、文字データ本体にメタ情報を束ねた構造体で、設計の核心は四つです。イミュータブルは安全な共有・ハッシュキャッシュ・スレッド安全を生む一方、繰り返し連結のO(n²)を招くため可変バッファで回避します。インターンは同一内容を1個に畳み込み等値比較をポインタ比較（O(1)）にしますが、無制限なインターンはリーク源です。SSOは短い文字列をオブジェクト本体に埋め込んでヒープ確保とキャッシュミスを消し、ロープは長文字列を木で持って連結・挿入をO(log n)に変えます。どれも万能ではなく、「不変で安全に共有」か「可変で速く編集」か、「重複を畳む」か「確保を消す」か——扱う負荷に応じて処理系が選んだトレードオフの結果なのです。