기술나눔

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

Go 언어를 시작하기 위한 Map에 대한 자세한 설명

1.기본 정의

map은 kv 형식의 키-값 쌍을 정렬하지 않은 모음입니다.

(1) 특징

• 유형 특성: map은 참조 유형이므로 함수의 값을 업데이트하면 영구적으로 변경됩니다.
• 순차적 특성: 지도 순회는 맨 아래 레이어가 해시 테이블이고 해시 테이블이 순서가 없기 때문에 순서가 없습니다.
• 초기화 사용: 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. 두 번째 단계는 지정된 키에 해당하는 값을 직접 설정하는 것입니다.

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 언어에서 map의 기본 본질은 다음을 사용하는 것입니다.hashmap구현되었으므로 지도는 기본적으로哈希表。

哈希表용도이다哈希函数빠른 삽입과 검색을 지원하는 데이터 구조로 데이터를 구성합니다.

哈希函数 해시 함수라고도 알려진 은 특정 해시 알고리즘을 통해 임의 길이의 입력(예: 문자열)을 고정 길이 출력으로 변환하는 함수입니다. 해시 값은 일반적으로 해시 값의 액세스 성능을 보장하기 위해 배열과 같은 형태로 저장됩니다.

입력 범위가 매핑된 출력 범위를 초과하면 서로 다른 입력이 동일한 출력을 얻을 수 있습니다.哈希冲突。

이 문제를 해결하는 방법에는 일반적으로 두 가지가 있습니다.开放地址法그리고拉链法

(1) 지도 실시 계획

공개 주소 방법:

데이터 구조는 일반적으로 배열을 사용하여 구현됩니다.

• 1. 첫째, 배열은 해시 테이블이라고 하는 다양한 해시 값으로 구성됩니다.
• 2. 그런 다음 많은 키를 수행하고 해시 기능을 수행하여 주소가 해당 위치에 있는지 확인합니다. 해시 테이블의 이 슬롯이 이미 점유된 경우 감지 시퀀스(예: 선형 감지, 2차 감지 또는 이중 해싱)를 사용합니다. 등) 사용 가능한 다음 키를 찾고 거기에 충돌하는 키를 저장합니다.

결점:

이 접근 방식을 사용하면 데이터가 저장될 뿐만 아니라 충돌을 해결하려면 추가 공간이 필요하므로 충돌을 해결하려면 더 많은 공간이 필요합니다.

지퍼 방식(Go 언어 맵에서는 이 방식을 사용함):

배열과 연결리스트는 일반적으로 기본 데이터 구조로 사용됩니다.

• 1. 우선 배열은 해시 테이블이라고 하는 서로 다른 해시 값으로 구성됩니다. 해시 테이블의 각 슬롯은 연결 목록을 저장합니다.
• 2. 그러면 많은 키가 들어오게 됩니다. 서로 다른 키를 해싱한 후 해시 값이 모듈식으로 계산되어 배열에 연결됩니다. 동일한 해시 값(해시 충돌)이 발생하면 새 키가 기존 키 목록에 고정됩니다. . 나중에
• 3. 특정 키를 찾아야 하는 경우 먼저 해시 함수를 사용하여 위치를 확인한 다음 일치하는 키를 찾거나 연결 목록의 끝에 도달할 때까지 해당 위치에서 연결 목록에 대해 선형 검색을 수행합니다.

배열의 서로 다른 인덱스에 연결된 연결 리스트를 버킷이라고도 합니다.

(2) 지도의 기본 구조

에이치맵

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

비맵

소스 코드에서 bmap 유형에는 tophash 필드가 하나만 있습니다.그러나 컴파일하는 동안 Go 컴파일러는 사용자 코드에 따라 해당 키, 값 및 기타 구조를 자동으로 삽입합니다.

표면 B맵

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

실제 비맵

// 编译期间会动态地创建一个新的结构：
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

위의 코드에 따르면 확장을 판단하는 데는 두 가지 조건이 있습니다.

• 부하율이 임계값 6.5를 초과합니다.overLoadFactor(h.count+1, h.B) , 부하율 = 요소 수 ¼ 버킷 수
• 오버플로 버킷이 너무 많이 사용되었습니다(32768 초과).tooManyOverflowBuckets(h.noverflow, h.B))

확장 방법:

• 증분 확장:

부하율이 너무 크면 새 버킷이 생성되고, 새 버킷 길이는 원래 길이의 두 배가 되며, 이전 버킷 데이터는 새 버킷으로 이동됩니다.

• 동일한 용량 확장

데이터가 많지 않은데 오버플로 버킷이 너무 많습니다.확장 중에 버킷 수는 변경되지 않습니다. 증분 확장과 유사한 재배치 작업이 다시 수행되고 느슨한 키-값 쌍이 재배열되어 버킷 사용량이 늘어나고 더 빠른 액세스가 보장됩니다.

확장 단계:

• 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. 재해시: oldbucket을 사용하여 원래 버킷 배열을 가리키고, 버킷을 사용하여 새 버킷 배열을 가리키고, 이전 버킷 배열의 모든 키-값 쌍을 순회하고, 해시 함수를 사용하여 각 키의 위치를 ​​다시 계산하여 새 버킷 배열에 삽입합니다. 버킷 어레이.

// 这个是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의 지도 구현은 다음을 선택할 수 있습니다.渐进式驱逐 키-값 쌍을 마이그레이션합니다. 즉, 확장 중에 이전 버킷 배열과 새 버킷 배열이 동시에 존재하고 새로 삽입된 키-값 쌍이 새 버킷에 직접 배치되며 이전 버킷에 액세스하면 마이그레이션 작업이 트리거됩니다.

// 进入后是一个简单的判断，之后的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. 내부 상태 업데이트: oldbucket의 모든 키-값 쌍이 재배치되면 Map의 내부 상태가 업데이트되고 oldbucket이 삭제됩니다.

4.사용 시나리오

• 1.빠른 탐색: 키를 기준으로 값을 빠르게 조회해야 할 때 Map은 평균 시간 복잡도 O(1)의 조회 성능을 제공합니다.
• 2.중복 제거: 고유 키를 저장해야 하는 경우 맵 키의 중복을 허용하지 않아 자연스럽게 중복 제거 기능을 구현할 수 있습니다.
• 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/