golangマップの実装説明

Golang は新興プログラミング言語であり、そのマップはハッシュ テーブルに基づいて実装されています。この記事では、Golang でマップがどのように実装されるかについて説明します。具体的には、ハッシュ テーブルの概念、Golang マップの構造とパフォーマンスの最適化について紹介します。

ハッシュ テーブルの概念

ハッシュ テーブルは、データをキーと値のペアで格納するデータ構造です。ハッシュ関数を通じてキーを配列インデックスにマップし、ハッシュ テーブル内のデータへのアクセスをより効率的にします。

ハッシュ関数は、キーを一意に識別する小さな固定長値に渡された値を計算します (これはハッシュ コードと呼ばれます)。このハッシュ コードは配列のインデックスとして使用されます。

ハッシュ関数にはいくつかの問題があります。 1 つはハッシュの衝突です。つまり、異なるキーが同じ配列インデックスにマップされており、これはハッシュの衝突を解決することで解決する必要があります。もう 1 つのタイプの問題は、ハッシュ関数が不適切であることです。値のハッシュ コードが正確に計算されず、ハッシュ テーブル内のデータが不均一に分散される可能性があります。

Golang マップの構造

Golang では、マップは構造であり、その基礎となるデータ構造はハッシュ テーブルです。具体的には、map は次の 3 つのフィールドで構成されます:

type hmap struct {
    count int                                 
    flags uint32                              
    B     uint8                               
    hash0 uint32                              
    buckets unsafe.Pointer // 指向一个桶数组
    oldbuckets unsafe.Pointer // 用于扩容时的桶数组
    nevacuate uintptr // 当前将要被载入到oldbuckets的指针位置
    extra *mapextra
}

このうち、count はマップ内の要素の数を表し、フラグは削除や反復などのマップの状態を記録するために使用されます。 ; B はバケット配列を表し、長さは 2 の B 乗です; hash0 は、ハッシュ関数の計算に使用されるハッシュ シードを記録します。

buckets は、バケットの配列を指すポインターです。バケット配列の形式は次のとおりです:

type bmap struct {
    tophash [bucketCnt]uint8
    data    [1]struct{ key, value interface{} }
}

このうち、tophash は、bucketCnt の長さの配列で、各要素は bmap 内の要素を表し、その値はキーを見つけるために使用される整数です。データ内の値のペア。 data は、キーと値のペアを含む長さ 1 の配列です。キーと値のペアの形式は次のとおりです:

type iface struct {
    tab  *itab
    data unsafe.Pointer
}

type itab struct {
    inter  *interfacetype
    _type  *_type
    link   *itab
    bad    int32
    inhash int32 // 是否在哈希表中
    funcbucket uintptr
    __hash uintptr // 哈希函数（方法）
    __eq   uintptr // 判断是否相等的函数（方法）
}

このうち、データ フィールドは iface 構造体へのポインタであり、iface 構造体には格納されたキーと値のペアへのポインタと、保存されたキーと値のペアへのポインタが含まれています。タイプ情報。

Golang マップのパフォーマンスの最適化

Golang マップによって実装されるパフォーマンスの最適化は、主に次の 2 つの側面に分かれています:

1. バケット配列の拡張

マップ内の要素の数がバケット配列の容量を超える場合、バケット配列を拡張する必要があります。拡張する方法は、新しいバケット配列を追加することです。次回マップにアクセスすると、すべてのキーと値のペアが再計算され、新しいバケット配列に 1 つずつ移動されます。このプロセスはリハッシュと呼ばれます。

バケット配列の拡張プロセスで、Golang はランダム化ハッシュと呼ばれるテクノロジーを使用します。このテクノロジーは、ハッシュ シードを調整して、再ハッシュ中にキーと値のペアが新しいバケット配列内でより均等に分散されるようにし、それによってハッシュの衝突を減らします。

2. 組み込みバイアス ロック

Golang は、マップ内でバイアス ロックと呼ばれるロック メカニズムを使用します。バイアス ロックは最適化手法の 1 つで、ロックに 1 つの go ルーチンのみがアクセスする場合、この go ルーチンのスレッド ID を使用してロックします。こうすることで、この go ルーチンがロックのロックを解除または再ロックする必要がある場合、他の go ルーチンがロックにアクセスしないため、スレッドを切り替える必要がなくなります。

概要

Golang のマップの基礎となるデータ構造はハッシュ テーブルであり、そのバケット配列はランダム化ハッシュ技術を使用してキーと値のペアを再ハッシュし、ロックとロックにはバイアスされたロック メカニズムを使用します。ロック解除されました。これらの実装の詳細により、Golang のマップはいくつかの一般的なデータ構造操作で非常に適切に実行できます。

以上がgolangマップの実装説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。