golang-data-structures

ペルソナ： データ構造の内部実装を理解している Go エンジニアです。メモリレイアウト、割り当てコスト、アクセスパターンを考慮し、最もなじみのある構造ではなく、用途に適した構造を選びます。

Go のデータ構造

組み込みおよび標準ライブラリのデータ構造：内部実装、適切な使い方、選択の指針。

• 安全性に関する落とし穴（nil マップ、append によるエイリアシング、防御的コピー）については、samber/cc-skills-golang@golang-safety スキルを参照してください。
• チャネルと同期プリミティブについては、samber/cc-skills-golang@golang-concurrency スキルを参照してください。
• string/byte/rune の選択については、samber/cc-skills-golang@golang-design-patterns スキルを参照してください。

ベストプラクティスの概要

1. サイズが既知、または推定できる場合は、make(T, 0, n) / make(map[K]V, n) でスライスとマップを事前割り当てします。これにより、繰り返し発生する拡張時のコピーと再ハッシュを回避できます。
2. 配列は、サイズがコンパイル時に固定されている場合（ハッシュダイジェスト、IPv4 アドレス、行列の次元）に限り、スライスより優先すべきです。
3. **スライスの容量が拡張されるタイミングには決して依存しないでください。**拡張アルゴリズムは Go のバージョン間で変更されており、今後も変更される可能性があります。新しいバッキング配列がいつ割り当てられるかにコードが依存しないようにしてください。
4. 優先度付きキューには container/heap を使い、container/list は中央への挿入が頻繁に必要な場合に限って使い、固定サイズの循環バッファには container/ring を使います。
5. 文字列の構築には strings.Builder を優先しなければなりません。双方向 I/O（io.Reader と io.Writer の両方を実装）には bytes.Buffer を優先しなければなりません。
6. ジェネリックデータ構造では、可能な限り制約を絞るべきです。キーには comparable、順序付けにはカスタムインターフェースを使います。
7. unsafe.Pointer は Go 仕様で有効とされる 6 つの変換パターンに限って使わなければなりません。文をまたいで uintptr 変数に格納することは決してしないでください。
8. weak.Pointer[T]（Go 1.24 以降）は、GC によるエントリの回収を可能にするため、キャッシュや正規化マップで使うべきです。

スライスの内部実装

スライスは、ポインター、長さ、容量からなる 3 ワードのヘッダーです。複数のスライスで同じバッキング配列を共有できます（エイリアシングの落とし穴とヘッダーの図については、samber/cc-skills-golang@golang-safety を参照してください）。

容量の拡張

• 要素数が 256 未満：容量は 2 倍になります
• 要素数が 256 以上：およそ 25％ずつ増加します（newcap += (newcap + 3*256) / 4）
• 拡張のたびにバッキング配列全体がコピーされます（O(n)）

事前割り当て

// Exact size known
users := make([]User, 0, len(ids))

// Approximate size known
results := make([]Result, 0, estimatedCount)

// Pre-grow before bulk append (Go 1.21+)
s = slices.Grow(s, additionalNeeded)

slices パッケージ（Go 1.21 以降）

主な関数：Sort/SortFunc、BinarySearch、Contains、Compact、Grow。Clone、Equal、DeleteFunc については、samber/cc-skills-golang@golang-safety スキルを参照してください。

スライスの内部実装の詳細 — slices パッケージの完全なリファレンス、拡張の仕組み、len と cap の違い、ヘッダーのコピー、バッキング配列のエイリアシング。

マップの内部実装

マップは、8 エントリのバケットとオーバーフローチェーンを持つハッシュテーブルです。参照型であり、マップを代入するとデータではなくポインターがコピーされます。

事前割り当て

m := make(map[string]*User, len(users)) // avoids rehashing during population

maps パッケージのクイックリファレンス（Go 1.21 以降）

関数	用途
Collect (1.23+)	イテレーターからマップを構築する
Insert (1.23+)	イテレーターからエントリを挿入する
All (1.23+)	すべてのエントリを対象とするイテレーター
Keys, Values	キー／値を対象とするイテレーター

Clone、Equal、ソート順のイテレーションについては、samber/cc-skills-golang@golang-safety スキルを参照してください。

マップの内部実装の詳細 — Go のマップがデータを保存・ハッシュする仕組み、バケットのオーバーフローチェーン、マップが縮小しない理由（および対処方法）、代替手段とのマップ性能の比較。

配列

固定サイズの値型です。代入時に全体がコピーされます。サイズがコンパイル時に決まる場合に使います。

type Digest [32]byte           // fixed-size, value type
var grid [3][3]int             // multi-dimensional
cache := map[[2]int]Result{}   // arrays are comparable — usable as map keys

それ以外の場合はスライスを優先してください。配列は拡張できず、値渡しされるため、大きなサイズではコストが高くなります。

container/ 標準ライブラリ

パッケージ	データ構造	最適な用途
container/list	双方向連結リスト	LRU キャッシュ、頻繁な中間要素の挿入・削除
container/heap	最小ヒープ（優先度付きキュー）	Top-K、スケジューリング、ダイクストラ法
container/ring	循環バッファー	ローリングウィンドウ、ラウンドロビン
bufio	バッファー付きリーダー／ライター／スキャナー	小さな単位で読み書きする場合の効率的な I/O

コンテナー型は any を使うため、型安全ではありません。ジェネリックなラッパーの利用を検討してください。コンテナーパターン、bufio、使用例 — 各コンテナー型を使う場面、型安全性を加えるジェネリックなラッパー、効率的な I/O のための bufio パターンを説明します。

strings.Builder と bytes.Buffer

文字列の連結だけを行う場合は strings.Builder を使います（String() でのコピーを回避できます）。io.Reader やバイト操作が必要な場合は bytes.Buffer を使います。どちらも Grow(n) に対応しています。詳細と比較

ジェネリックなコレクション（Go 1.18+）

制約は必要最小限のものを使います。マップのキーには comparable、ソートには cmp.Ordered、ドメイン固有の順序付けにはカスタムインターフェースを使います。

type Set[T comparable] map[T]struct{}

func (s Set[T]) Add(v T)          { s[v] = struct{}{} }
func (s Set[T]) Contains(v T) bool { _, ok := s[v]; return ok }

ジェネリックなデータ構造の作成 — Go 1.18+ のジェネリクスを使った型安全なコンテナーの作成、制約の充足条件の理解、ドメイン固有のジェネリック型の構築について説明します。

ポインター型

型	用途	ゼロ値
*T	通常の間接参照、変更、オプショナルな値	nil
unsafe.Pointer	FFI、低レベルのメモリレイアウト（仕様で定められた 6 つのパターンのみ）	nil
weak.Pointer[T]（1.24+）	キャッシュ、正規化、弱参照	該当なし

ポインター型の詳細 — 通常のポインター、unsafe.Pointer（仕様で有効な 6 つのパターン）、クリーンアップを妨げない GC 安全なキャッシュのための weak.Pointer[T] について説明します。

コピーの意味に関するクイックリファレンス

型	コピーの動作	独立性
int、float、bool、string	値（ディープコピー）	完全に独立
array、struct	値（ディープコピー）	完全に独立
slice	ヘッダーをコピーし、バッキング配列を共有	slices.Clone を使用
map	参照をコピー	maps.Clone を使用
channel	参照をコピー	同じチャネル
*T（ポインター）	アドレスをコピー	同じ基になる値
interface	値をコピー（型と値のペア）	保持する型によって異なる

サードパーティーライブラリ

標準ライブラリにはない高度なデータ構造（ツリー、セット、キュー、スタック）を使う場合：

• emirpasic/gods — 包括的なコレクションライブラリ（ツリー、セット、リスト、スタック、マップ、キュー）
• deckarep/golang-set — スレッドセーフおよびスレッドセーフではないセットの実装
• gammazero/deque — 高速な両端キュー

サードパーティーライブラリを使う場合は、最新の API シグネチャを公式ドキュメントとコード例で確認してください。

• Go パッケージのドキュメント、シンボル、バージョン、インポーター、既知の脆弱性については、→ samber/cc-skills-golang@golang-pkg-go-dev スキル（godig）を参照してください。Go パッケージに関する情報は Context7 よりもこちらを優先してください。
• 自分のコード内でこのライブラリの使われ方（定義、呼び出し箇所、診断情報）を調べるには、→ samber/cc-skills-golang@golang-gopls スキル（gopls）を参照してください。
• Context7 は、pkg.go.dev にインデックスされていないドキュメントの代替手段として利用できます。

相互参照

• → 構造体フィールドのアラインメント、メモリレイアウトの最適化、キャッシュ局所性については、samber/cc-skills-golang@golang-performance スキルを参照してください
• → nil のマップ／スライスに関する注意点、append によるエイリアス、ディフェンシブコピー、slices.Clone／Equal については、samber/cc-skills-golang@golang-safety スキルを参照してください
• → チャネル、sync.Map、sync.Pool、すべての sync プリミティブについては、samber/cc-skills-golang@golang-concurrency スキルを参照してください
• → string と []byte と []rune の使い分け、イテレーター、ストリーミングについては、samber/cc-skills-golang@golang-design-patterns スキルを参照してください
• → 構造体の合成、埋め込み、ジェネリクスと any の使い分けについては、samber/cc-skills-golang@golang-structs-interfaces スキルを参照してください
• → スライス／マップの初期化スタイルについては、samber/cc-skills-golang@golang-code-style スキルを参照してください

よくある間違い

間違い	修正方法
事前確保せずにループ内でスライスを拡張する	拡張のたびに、バッキング配列全体がコピーされます（拡張ごとに O(n)）。make([]T, 0, n) または slices.Grow を使用してください
スライスで十分な場面で container/list を使う	リンクリストはキャッシュ局所性に優れません（各ノードが個別のヒープ割り当てです）。まずベンチマークを行ってください
文字列の組み立てだけに bytes.Buffer を使う	Buffer の String() は基になるバイト列をコピーします。strings.Builder ならこのコピーを避けられます
unsafe.Pointer を文をまたいで uintptr として保持する	文の実行間に GC がオブジェクトを移動させる可能性があり、uintptr が無効な参照になります
マップに大きな構造体の値を格納する（コピーのオーバーヘッド）	マップへのアクセス時に値全体がコピーされます。大きな値型では map[K]*V を使ってコピーを避けてください

参考資料

• Go のデータ構造（Russ Cox）
• Go メモリモデル
• Effective Go