golangのmap実装(一)

概要
ハッシュ・テーブルは、エンジニアリングでよく使用されるデータ型であり、迅速な検索と更新を提供します.複雑度は一般にO(1)である
本編の博文は2つの部分に分けて書いて、第1部分はソースコードの学習で、第2部分はいくつかの内部の実現で、および面白いいくつかの地方を感じて、および個人の思考
理論
ハッシュ・テーブルで解決すべき問題は2つあります.

位置インデックス

データ衝突

インデックスはhash functionハッシュアルゴリズムに渡され、よく使われるのはモード演算である.
衝突を解決するには主に以下の3つの方法があります.

はリンクを分離する、すなわちチェーンテーブルの性質を利用して競合するkeyを記憶し、その後、従来の区別(個別の記憶レベル)

を通過する.

オープン・アドレス

リニアプローブ(ストレージレベルおよびアルゴリズムレベルが調整されている)

平方プローブ(同上、アルゴリズムレベルの小さな変更にすぎない)

二重ハッシュ

再ハッシュ(拡張およびデータ移行)

拡張可能なカラムは、データが大きすぎてメモリに入れられないシーンを解決するために使用されます.ここでは説明しません.
ハッシュテーブルの効率はload factor充填因子に関係し,その平均複雑さを推定するために用いられた.一般に、格納されたデータ量/インデックス可能なアドレスの数を用いて計算されることを意味する.あるいは、単一インデックスアドレスの平均長さ
衝突の解決
理想的には,衝突がない場合,1つの配列を用いてハッシュアルゴリズムとハッシュ構造を実現できる.しかし衝突は完全に避けられず、以下のような方法で解決される.
リンクの分離
リンクを分離するコアは、チェーンテーブルを使用して衝突問題を処理することです.配列はインデックスとして使用され、内部にはチェーンテーブルが格納され、チェーンテーブルにはハッシュ衝突のkeyとvalueが格納され、格納keyは衝突時に比較によって位置決めを実現するために使用される.
オープンアドレス
チェーンテーブルの問題はノード申請で、メモリの頻繁な操作をもたらします.データ量が特に大きくない場合は,オープンアドレス方式を考慮することができる.比較的大きな配列を使用します.ただし、衝突が発生した場合には、固定方向にオフセットして記憶することで、衝突問題を解決することができます.線形プローブと二乗プローブはオフセット量選択にある.にじゅうハッシュ
再ハッシュ
衝突はある程度記憶空間が小さいことによるものといえる.ではrehashの考え方は、より大きな空間を申請し、データを再計算し、再配置することです.
Golangのmap実装
golangのmapはハッシュテーブルであり、チェーンテーブルおよびrehashを実装するために使用される.
チェーンテーブルは、より小さなレベルで衝突するために使用され、rehashはload factorが大きい場合に使用される.
注意:本編の記録はgo 1.9.2バージョンに基づいて記録されています.
データ構造
golangのmapには、伝達されたkeyおよびvalueが直接格納されず、その参照、およびkeyのhash値の上位が使用される(後述).
次はmapデータ構造の部分で、主にストレージに関連するドメインを選択します.

type hmap struct {
    B          uint8
    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    extra      *mapextra
}

bucketsとoldbucketsは、連続アドレスを指すポインタアドレスである.主にkeyとvalueの参照アドレスを格納するために用いられ,一時的にデータ部分として理解される.このうちoldbucketsは拡張時にのみ使用されます.両者は、前の「分離リンク」実装の配列機能と同様に、初歩的なインデックスとして使用されます.

type mapextra struct {
    overflow [2]*[]*bmap
    nextOverflow *bmap
}

一時的にnextoverflowだけに注目すればよいが、bucketsに似た連続アドレス(最後のbucketの最後にメンテナンスされたのはアドレスである.bucketsとoldbucketsにはこれがない)を指し、名前から空間が足りない場合(ただしrehashロジックをトリガするのに十分ではない)システムからメモリの一時的な使用を申請する空間をバッファリングしていることがわかる.

type bmap struct {
    tophash [bucketCnt]uint8
}

bmapはbucketデータ構造の一部構造である.このチェーンテーブルのアドレスを大まかに確認する機能です.空間が8の配列です.その値はkeyのhash値の高位である.1つのkeyが渡されると、比較して、この配列の下付きを決定します.この下付きは、このkeyが格納しているチェーンテーブルのヘッダに関係しています.
メモリ構造
以下の構造はすべてソースコードの個人的な理解によって描かれており、ずれがある可能性があります.実はmapの操作の後に置くべきです.しかし、後の操作を理解するのに役立つように、前に置きました.
拡張シーンを考慮しないで、mapストレージデータはbucketsを先に使用し、スペースが足りない場合(先にそう言えば)overflow領域を使用します.だから下にはこの2つの構造が置いてあります.
bucket

bmap
|        
|    |
|    |  |    key field  |  value field  |       bucket    
|____|__|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|

bmapは8つのuint 8の連続空間であり、tophashを格納するために使用される.後続のデータの位置合わせはメモリレベルの操作です.key fieldとvalue fieldは、key参照およびvalue参照を格納するために使用され、両方とも8つの空間であり、tophashのオフセット量によって各参照自体の記憶位置を計算し、keyおよびvalueを取得することができる.
nextOverFlow

|_|_|_|_|_|_|_-|

            bucket

nextoverflowはbucketサイズの連続空間を指し、機能は上のbucketと同じである.しかしnextoverflowの最後のbucket、すなわち上の|----|は、データを格納するために使用されるのではなく、末尾文字として特別に使用されています.バッファが終了したことを知らせるために使用されます.実装は、hmap構造におけるbucketsのヘッダアドレスを格納する最後の参照サイズの空間である.
注意:作成するbucketが8つを超える場合、golangはnextoverflowのスペースを事前に申請し、メモリ操作を減らします(詳細はいいですが)、bucketsとnextoverflowはメモリ上で連続しています.構造は次の図になります.

                                          |     | ---->      bucketSize      
buckets                    nextOverFlow  |       buckets     
|                           |             |  |  |
|                           |             |  |  |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|-|    '-'   sys.PtrSize，    ptrSeize   bucketSize

        ，    

インタフェース実装
mapのインタフェース実装には、上のメモリ構造のほかに、データ競合、ロードファクタサイズ、拡張時に使用されるデータ構造など、描かれていないドメインがあります.
作成
作成とは、メモリの申請を完了し、初期値の設定です.ここでは,作成された空間が大きいと仮定し,すなわちoverflow領域の初期化も併せてここに記録する.makemapはmap構造を完了する関数である.以下は原生コードを抽出し、いくつかの『偽コード』を簡単に読むことができます.

// hint     capacity
func makemap(t *maptype, hint int64) *hmap  {
    //     
    t.keysize = sys.PtrSize = t.key.size
    t.valuesize = sys.PtrSize = t.elem.size

    //    hint    hmap      B      。
    // B           ，            。B      。
    // overLoadFactor        。golang         0.65
    B := uint8(0)
    for ; overLoadFactor(hint, B); B++ {}

    // golang   lazy       
        if B != 0 {
        var nextOverflow *bmap
        buckets, nextOverflow = makeBucketArray(t, B)
        if nextOverflow != nil {
            extra = new(mapextra)
            extra.nextOverflow = nextOverflow
        }
    }

    //              hmap   ，     
    h.count = 0  //       k/v pari   。       
    h.B = B  //     
    h.flags = 0 //      。      ，    。

    ...
}

// makeBucketArray              nextOverflow 。
func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := uintptr(1 << b)
    nbuckets := base
    if b >= 4 {
        //      nbuckets
    }

    //   ，    nbuckets      
    buckets = newarray(t.bucket, int(nbuckets))

    //    overflow   ，
    if base != nbuckets {
        //            
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))

        //       ，         nextoverflow         。       
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    return buckets, nextOverflow
}

メモリマップの3つ目を合わせると、より効果的です.全体的な印象を持ちやすいです.
読み取り
読み取りはmapaccess1とmapaccess2の2つで、前者はポインタを返し、後者はポインタを返し、keyが存在するか否かを判断するためにboolである.ここではmapaccess1としか言いません.ポインタはvalue fieldに格納されているアドレスです

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//           0，        0  

//        ，      

//    key   hash  

//     key     bucket    （     buckets       oldbuckets  ）
//      ，        buckets  ，      bucket
//    oldbucket     ，     ，             oldbuckets    
//      bucket       evacuate ，      evacuate     buckets，      oldbuckets     
    m := uintptr(1)< 1
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))  // buckets   
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {  //              ，     
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }

//    bucket   ，   tophash      ，      ，     bucket   overflow  ，    。
//          。
// 1      ，         tophash ，         。
// 2    tophash     key   ，         val   ，      overflow     ，        

書き込み
ここで『書き込み』を使うのはそれほど厳しくありません.最後に返されるのはvalueを格納するためのポインタアドレスです.すなわち、入力したkeyによりvalue参照を書き込むアドレスを確認する(bucket構造のvalue fieldを考慮)
書き込みの操作をさらに説明する前に、拡張についてお話しします.書き込み量の増加に伴い、拡張は避けられない.拡張すると、新しい空間の申請に関連し、古い空間データの移行、および最後の古い空間の回収に関連します.データ移行部分は一度に完了できますが、ある操作が特に遅くなる可能性があります.golangは移行時にlazy方式を使用し、oldbucket内の要素を変更する場合にのみ、oldbucketを静かに再hashしてbucketsに書き込み、oldbucketを参照を削除してgcに渡して空間回収します.
より多くのgrow関連操作は『内部』で詳しく言えば、ここでは全体の流れが多い.mapassignは、この動作を完了するためのマスター関数である.(ここまで書いて、急に書きたくなくなった…心が疲れた)

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    //     
    //    hash  
    //         

    //             。     
    //           bucket  ，      key    
        //     （    ），         val    ，       
        //     ，          
    //           bucket   overflow   ，      bucket  
        //   ，        
        //   （   overflow    ，     ）      
    //                  （       ，  h.count++，   map   key    ）
        //    hashGrow (   )，           ，    
        //    overflow,           
        //     

    //      val   
}

削除mapdeleteは削除を担当する主体関数です

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    //   access      ，         
    //      ，     value      ，    gc         
    //   tophash          empty (         )
    // h.count--
}

参考資料https://www.gitbook.com/book/tiancaiamao/go-internals/details
記事は初めて個人ブログに投稿されましたhttps://blog.i19.me