技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Go言語入門マップの詳しい解説

1.基本的な定義

マップは、kv 形式のキーと値のペアの順序付けされていないコレクションです。

(1) 特長

• 型の特性:マップは参照型であるため、関数内の値を更新すると永続的に変更されます。
• シーケンシャル特性: 最下層がハッシュ テーブルであり、ハッシュ テーブルが順序付けされていないため、マップの走査は順序付けされていません。
• 初期化の使用: 0 値または初期化されていない値は nil です。初期化されていない値を割り当てることはできません。そうでない場合は、直接パニックが発生します。
• キーと値のペア: キーと値は常にペアで表示されます。キーは一意であり、比較可能な任意のタイプにすることができます。
• 動的: 事前にサイズを宣言しなくても、キーと値のペアを実行時に動的に追加または削除できます。
• 高速検索: マップは、平均時間計算量 O(1) で、高速な検索、挿入、および削除の操作を提供します。
• 同時実行性: スレッドセーフではありません。安全性を確保するにはロックが必要です

(2) 定義文

var name map[key_type]value_type
1

• 名前: 変数名
• key_type: キーのタイプ
• value_type: 値のタイプ

// 方式一
var m map[int]string = map[int]string{}

// 方式二
m := map[int]string{
    1 : "老一",
    2 : "老二",
    3 : "老三",
}

// 方式三：5代表容量，也就是在内存中占用多大的空间，可以省略
m := make(map[int]string,5)
1
2
3
4
5
6
7
8
9
10
11
12

2.基本的な使い方

(1) 要素の追加

• 1. 最も一般的な方法は、上記の方法 2 で示したように、リテラルを介してマップを宣言するときに追加することです。
• 2. 2 番目のステップでは、指定されたキーに対応する値を直接設定します。

mapName[key] = value

// 假设map名为m，key为int，value为string
m[5] = "老五"
1
2
3
4

(2) 要素の削除

キーに基づいて要素を削除します。存在しないキーを削除してもエラーは報告されません。

delete(mapName, key)  

// 假设map名为m，key为int，value为string
delete(m, 5)
1
2
3
4

(3) 要素の変更

変更するには、指定したキーに対応する値を直接変更できます。

mapName[key] = newValue 

// 假设map名为m，key为int，value为string
m[5] = "五"
1
2
3
4

(4) 要素の取得

キーに従って値を取得します。ok は見つかったかどうかのフラグビットです。タイプはブールです。

値が見つからない場合、エラーは報告されず、対応する型の null 値が返されます。

value, ok := mapName[key]
if !ok {
		fmt.Println(ok)
	}
1
2
3
4

(5) すべての要素を横断する

注: マップの走査は順序付けされていません

for key, value := range myMap {
   // 处理每对键值
}

// 例子
for i, s := range m {
		fmt.Println(i, s)
	}
1
2
3
4
5
6
7
8

3. 基礎となる原則

Golang 言語のマップの根本的な本質は、次のとおりです。hashmap実装されているため、マップは基本的に哈希表。

哈希表用途です哈希函数データを、高速な挿入と検索をサポートするデータ構造に編成します。

哈希函数は、ハッシュ関数とも呼ばれ、特定のハッシュ アルゴリズムを通じて任意の長さの入力 (文字列など) を固定長の出力に変換する関数です。ハッシュ値は、通常、ハッシュ値のアクセスパフォーマンスを確保するために配列のような形式で格納されます。

入力の範囲がマップされた出力の範囲を超えると、異なる入力が同じ出力を取得する可能性があります。哈希冲突。

通常、この問題を解決するには次の 2 つの方法があります。开放地址法そして拉链法

(1) 地図実施計画

オープンアドレス方式:

データ構造は通常、配列を使用して実装されます

• 1. まず、配列はさまざまなハッシュ値で構成されており、これをハッシュ テーブルと呼びます。
• 2. 次に、多くのキーを実行し、ハッシュ関数を実行して、アドレスが対応する位置に配置されていることを確認します。ハッシュ テーブルのこのスロットがすでに占有されている場合は、検出シーケンス (線形検出、二次検出、二重ハッシュなど) を使用します。 、など)、使用可能な次のキーを見つけて、そこに競合するキーを保存します。

欠点:

このアプローチでは、データが保存されるだけでなく、衝突を解決するために追加のスペースが必要になるため、競合を解決するためにより多くのスペースが必要になります。

ジッパーメソッド (Go 言語マップはこのメソッドを使用します):

配列とリンク リストは通常​​、基礎となるデータ構造として使用されます。

• 1. まず、配列はハッシュ テーブルと呼ばれるさまざまなハッシュ値で構成され、ハッシュ テーブルの各スロットにはリンク リストが格納されます。
• 2. その後、多数のキーが入力されます。異なるキーをハッシュした後、ハッシュ値がモジュール的に計算され、同じハッシュ値の場合 (ハッシュ衝突)、新しいキーが既存のキー リストにハングされます。 。 後で
• 3. 特定のキーを見つける必要がある場合は、まずハッシュ関数を使用してその位置を特定し、次に、一致するキーが見つかるか、リンク リストの最後に到達するまで、その位置でリンク リストの線形検索を実行します。

配列の異なるインデックスでリンクされたリンク リストはバケットとも呼ばれます。

(2) マップの基本構造

hマップ

type hmap struct {
 count     int // 当前哈希表中的元素数量，即键值对数量，可用内置函数len()获取
 flags     uint8  // 标志位，标记map状态和属性的字段，如正在迭代等状态
 B         uint8  // 表示哈希表桶（buckets）的数量为2的B次方
 noverflow uint16 // 溢出桶的大致数量，扩容时会用到
 hash0     uint32 // 哈希种子，对key做哈希是加入种子计算哈希值，确保map安全性

 buckets    unsafe.Pointer // 存储桶数组的指针
 oldbuckets unsafe.Pointer // 扩容时用于保存旧桶数组的指针 , 大小为新桶数组的一半
 nevacuate  uintptr        // 扩容时的迁移进度器，迁移桶下标小于此值说明完成迁移

 extra *mapextra // 溢出桶的指针，指向mapextra结构体，用于存储一些额外的字段和信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// mapextra 处理桶溢出的结构体
type mapextra struct {
 overflow    *[]*bmap    // 溢出桶数组指针，仅当key和elem非指针时才使用
 oldoverflow *[]*bmap    // 旧的溢出桶数组指针，仅当key和elem非指针时才使用

 nextOverflow *bmap      // 下一个可用的溢出桶地址
}

1
2
3
4
5
6
7
8

bマップ

ソース コードでは、bmap タイプには tophash フィールドが 1 つだけあります。ただし、コンパイル中に、Go コンパイラーはユーザー コードに従って、対応するキー、値、その他の構造を自動的に挿入します。

サーフェス bmap

type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

1
2
3
4
5
6
7
8
9
10
11
12

実際のbmap

// 编译期间会动态地创建一个新的结构：
type bmap struct {
   topbits  [8]uint8   // 这里存储哈希值的高八位，用于在确定key的时候快速试错，加快增删改查寻址效率,有时候也叫tophash
   keys     [8]keytype   // 存储key的数组，这里bmap最多存储8个键值对
   elems   [8]valuetype    // 存储value的数组，这里bmap也最多存储8个键值对
   ...
   overflow uintptr     // 溢出桶指针
}

1
2
3
4
5
6
7
8
9

マップの基礎となる図

マップの拡張

Go 言語では、マップのパフォーマンスを維持するためにマップの拡張が自動的に実行されます。

まず、書き込み時にマップが渡されますruntime.mapassign拡張が必要かどうかを判断する

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 // If we hit the max load factor or we have too many overflow buckets,
 // and we're not already in the middle of growing, start growing.
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
 }
...
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 return noverflow >= uint16(1)<<(B&15)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上記のコードによれば、展開を判断するための条件は 2 つあります。

• 負荷率がしきい値 6.5 を超えています:overLoadFactor(h.count+1, h.B) 、負荷率 = 要素数 ÷ バケット数
• 使用されているオーバーフロー バケットが多すぎます (32768 を超えています):tooManyOverflowBuckets(h.noverflow, h.B))

拡張方法:

• 段階的な拡張:

負荷率が大きすぎる場合は、元の長さの 2 倍の新しいバケットが作成され、古いバケットのデータが新しいバケットに移動されます。

• 均等な容量拡張

データはそれほど多くありませんが、オーバーフロー バケットが多すぎます。拡張中、バケットの数は変更されず、増分拡張と同様の再配置操作が再度実行され、バケットの使用量を増やしてアクセスを高速化するために、緩いキーと値のペアが再配置されます。

拡張手順:

• 1. 新しいバケット配列:元のサイズで新規作成ダブル新しいバケット配列は拡張済みとしてマークされます。

func hashGrow(t *maptype, h *hmap) {
 ...
 // 原有桶设置给oldbuckets
 oldbuckets := h.buckets   
 // 创建新桶
 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

 flags := h.flags &^ (iterator | oldIterator)
 if h.flags&iterator != 0 {
  flags |= oldIterator
 }
 // commit the grow (atomic wrt gc)
 h.B += bigger
 h.flags = flags
 h.oldbuckets = oldbuckets
 h.buckets = newbuckets
 h.nevacuate = 0
 h.noverflow = 0

 ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 2. リハッシュ: oldbuckets を使用して元のバケット配列を指し、buckets を使用して新しいバケット配列を指し、古いバケット配列内のすべてのキーと値のペアを走査し、ハッシュ関数を使用して各キーの位置を再計算して新しいバケット配列に挿入します。バケット配列。

// 这个是mapdelete函数中的处理迁移的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 if h.growing() {
  // 
  growWork(t, h, bucket)
 }
...
}

1
2
3
4
5
6
7
8
9
10

• 3. 段階的な移行: 拡張中にプログラム全体が一時停止するのを避けるために、Go の Map 実装では次のオプションを選択できます。渐进式驱逐キーと値のペアを移行します。これは、拡張中、古いバケット配列と新しいバケット配列が同時に存在し、新しく挿入されたキーと値のペアが新しいバケットに直接配置され、古いバケットへのアクセスによって移行操作がトリガーされることを意味します。

// 进入后是一个简单的判断，之后的evacuate是核心逻辑处理，特别多，感兴趣自己看源码
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

• 4. 内部ステータスの更新: 古いバケット内のすべてのキーと値のペアが再配置されると、マップの内部状態が更新され、古いバケットが削除されます。

4.利用シーン

• 1.クイック検索: キーに基づいて値をすばやく検索する必要がある場合、Map は平均時間計算量 O(1) の検索パフォーマンスを提供します。
• 2.重複を削除する: 一意のキーを保存する必要がある場合、Map キーの重複は許可されず、重複排除機能が自然に実現されます。
• 3.動的コレクション: マップは、キーと値のペアを動的に追加または削除する必要がある場合に柔軟な操作を提供します。
• 4.リンクされたデータ: データがキーと値のペアの形式で存在し、頻繁に更新またはクエリする必要がある場合は、マップが適しています。

5. 使用方法の提案

1. 事前に割り当てられた処置: make 関数を使用して、既知のサイズのマップに容量を割り当ててみてください。
2. データ型の選択: より大きなデータ型を使用します。intまたはint64。
3. ポインタのストレージ: 大量のデータを含む構造体または変数の場合は、ポインタを使用して値を転送および保存するようにしてください。
4. 同時実行制御: 同時アクセスの場合は、次を使用します。sync.Mapまたは、独自の同時安全マップを実装します。

6.参考資料

• https://cloud.tencent.com/developer/article/2400014
• https://blog.csdn.net/qq_35289736/article/details/137480760/
• https://zhuanlan.zhihu.com/p/675715169/