Goにおけるスライスとマップ拡張の深い研究

Go言語の研究において、配列とMapの拡張戦略は一般的で古典的なトピックです。この記事では、配列とMapの拡張戦略を要約して説明することを目的としています。

配列の拡張

Goでは、動的配列はスライスと呼ばれます。スライスは、柔軟で動的にサイズ変更可能な配列ソリューションを提供します。append関数を使用して要素をスライスに追加するとき、Goはスライスの現在の容量に基づいて容量を拡張するかどうかを決定します。

Goにおけるスライスの拡張戦略は次のとおりです。

1. まず、新しく要求された容量が古い容量の2倍よりも大きい場合、最終的な容量は新しく要求された容量になります。
2. それ以外の場合、古いスライスの長さが1024未満の場合、最終的な容量は古い容量の2倍になります。
3. それ以外の場合、古いスライスの長さが1024以上の場合は、新しく要求された容量に達するか超えるまで、最終的な容量は古い容量の4分の1ずつ段階的に増加します。
4. 最終的な容量の計算がオーバーフローした場合、最終的な容量は新しく要求された容量になります。

ハッシュテーブルの拡張

Goでは、Mapはキーと値のペアを格納するためによく使用されるデータ構造です。その拡張メカニズムは、Mapのパフォーマンスとメモリ使用量を理解する上で重要です。

GoのMapには、次の2種類の拡張があります。

• 倍増拡張: キーと値のペアの数が現在のバケット配列容量の6.5倍を超える場合、バケットがほぼいっぱいになることを意味します。この時点で、拡張がトリガーされ、バケットの数が2倍になります。その目的は、ハッシュの衝突を減らし、クエリの効率を向上させることです。
• 同サイズ拡張: オーバーフローバケットが多すぎる（たとえば、頻繁な挿入と削除によりデータが分散する）が、キーと値のペアの合計数が少ない場合、バケットの数は変わりません。代わりに、データが再配置され、冗長なオーバーフローバケットがマージされ、データの分布がよりコンパクトになり、クエリのパフォーマンスが向上します。

Mapの基盤となる構造

GoのMapの基盤となる実装はハッシュマップです。Goのソースコードは次のとおりです。

// runtime/map.go
// A header for a Go map.
type hmap struct {
 count     int // number of key-value pairs currently in the hash table
 flags     uint8
 B         uint8  // number of buckets currently held by the hash table. Since the number of buckets always expands by a factor of 2, this field stores the exponent, i.e. len(buckets) == 2^B
 noverflow uint16 // approximate number of overflow buckets
 hash0     uint32 // hash seed

 buckets    unsafe.Pointer // array storing 2^B buckets
 oldbuckets unsafe.Pointer // used to save the previous buckets during expansion, size is half of buckets
 nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

 extra *mapextra // optional fields
}

// mapextra mainly maintains overflow buckets when some buckets in hmap have overflowed
// but have not yet reached the threshold for expansion
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap

 // nextOverflow holds a pointer to a free overflow bucket.
 nextOverflow *bmap
}

いくつかの主要なフィールドの説明は次のとおりです。

• count: ハッシュテーブル内のキーと値のペアの数を示します。
• B: これは基数2の指数であり、バケットの数を決定するために使用されます。たとえば、B = 1の場合、バケットの数は2^1 = 2です。B = 2の場合、バケットの数は2^2 = 4などです。
• hash0: キーのハッシュ値を計算するために使用される係数。
• buckets: バケット配列へのポインタ。各バケットはキーと値のペアを格納するために使用されます。
• overflow: バケットがこれ以上要素を保持できず、キーがこのバケットにハッシュされると、要素はオーバーフローバケットに配置され、元のバケットのオーバーフローフィールドはオーバーフローバケットを指します（チェイニング法）。

拡張メカニズム：倍増拡張

トリガー条件：

Mapの負荷が特定のしきい値を超えると、倍増拡張がトリガーされます。負荷は、要素の数（count）をバケットの数（2^B）で割ったものとして計算されます。この比率が6.5以上の場合、負荷が超過したと見なされます。

たとえば、B = 2の場合、2^2 = 4個のバケットがあります。要素数countが26（26 / 4 = 6.5）の場合、倍増拡張がトリガーされます。

ソースコード内の関連するロジックは次のとおりです。

// assume h is a pointer to the map structure
if !h.flags&hashWriting && h.count > int(float64(1<<h.B)*loadFactor) {
    // trigger doubling expansion logic
}

拡張プロセス：

倍増拡張中、Bの値が1ずつ増加し、バケットの数が2倍になります。たとえば、もともとB = 2で4つのバケットがあった場合、拡張後B = 3になり、2^3 = 8個のバケットになります。

データを移行するとき、元のバケット内の要素は新しいバケットに再分散されます。具体的には、キーのハッシュ値に基づいて新しいバケットの位置が再計算されます。

キーのハッシュ値がhashであると仮定します。元のバケットの数は2^B1で、拡張後、2^B2になります。次に、データは元のバケット（hash % 2^B1）から新しいバケット（hash % 2^B2）に移行します。

例：

• ハッシュ値が10で、B = 2（4つのバケット）の場合、10 % 4 = 2であるため、データはインデックス2のバケットに格納されます。
• B = 3（8つのバケット）で拡張した後、10 % 8 = 2となり、データはまだインデックス2のバケットにあります。ただし、バケットの分布はより疎になり、ハッシュの衝突の確率が減少します。

拡張メカニズム：同サイズ拡張

トリガー条件：

多数のキーが削除され、オーバーフローバケットが多すぎると、同サイズ拡張がトリガーされる可能性があります。ここで、オーバーフローバケットとは、バケットが8つの要素でいっぱいになり、新しい要素がオーバーフローバケットに格納される状況を指します。オーバーフローバケットは、バケットの総数にはカウントされません。

オーバーフローバケットの数が2^B以上の場合、同サイズ拡張がトリガーされる可能性があります。ただし、ハッシュの衝突が原因でオーバーフローバケットが過剰になり、負荷が超過した場合、最初に倍増拡張がトリガーされます。

ソースコード内の関連するロジックは次のとおりです。

// assume h is a pointer to the map structure, noverflow is the number of overflow buckets
if noverflow >= uint16(1)<<(h.B) {
    if h.B < 15 {
        // may trigger same-size or doubling expansion logic
    }
}

拡張プロセス：

同サイズ拡張は、主に空きスペースを削除するためにバケットを整理します。新しいバケット配列が作成され、古いバケット配列がトラバースされ、空でないキーと値のペアを新しい配列に再挿入すると同時に、元のオーバーフローバケットを解放します。

ハッシュ係数、Bの値、およびハッシュアルゴリズムは変更されないため、新しいバケット内のキーと値のペアの位置は以前と同じ方法で計算されます。空のストレージスペースのみが削除され、キーと値のペアがよりコンパクトになり、後続の操作の効率が向上します。

---

Leapcellをご紹介します。Goプロジェクトのホスティングに最適です。

Leapcellは、Webホスティング、非同期タスク、Redis向けの次世代サーバーレスプラットフォームです。

多言語サポート

• Node.js、Python、Go、またはRustで開発します。

無制限のプロジェクトを無料でデプロイ

• 使用量に対してのみ支払い - リクエストも課金もありません。

比類のないコスト効率

• アイドル時の料金なしで、従量課金制。
• 例：25ドルで、平均応答時間60ミリ秒で694万件のリクエストをサポートします。

合理化された開発者エクスペリエンス

• 簡単なセットアップのための直感的なUI。
• 完全に自動化されたCI/CDパイプラインとGitOps統合。
• 実用的な洞察のためのリアルタイムのメトリックとロギング。

簡単なスケーラビリティと高性能

• 高い同時実行性を容易に処理するための自動スケーリング。
• 運用上のオーバーヘッドはゼロ - 構築に集中するだけです。

詳細については、ドキュメントをご覧ください。

Xでフォローしてください：@LeapcellHQ