golang 맵 구현 설명

Golang은 신흥 프로그래밍 언어이며 해당 지도는 해시 테이블을 기반으로 구현됩니다. 이번 글에서는 Golang에서 map을 구현하는 방법에 대해 설명하겠습니다. 구체적으로 해시 테이블의 개념, Golang 맵의 구조 및 성능 최적화에 대해 소개합니다.

해시 테이블의 개념

해시 테이블은 키-값 쌍으로 데이터를 저장하는 데이터 구조입니다. 해시 함수를 통해 키를 배열 인덱스에 매핑하므로 해시 테이블의 데이터에 더 효율적으로 액세스할 수 있습니다.

해시 함수는 전달된 값을 키를 고유하게 식별하는 작은 고정 길이 값(해시 코드라고 함)으로 계산합니다. 이 해시 코드는 배열 인덱스로 사용됩니다.

해시 함수에 몇 가지 문제가 있습니다. 하나는 해시 충돌입니다. 즉, 서로 다른 키가 동일한 배열 인덱스에 매핑되는데, 이는 해시 충돌을 해결하여 해결해야 합니다. 또 다른 유형의 문제는 해시 함수가 부적절하여 해당 값의 해시 코드를 정확하게 계산하지 못하여 해시 테이블의 데이터 분포가 고르지 않게 되는 것입니다.

Golang 맵의 구조

Golang에서 맵은 구조이고 기본 데이터 구조는 해시 테이블입니다. 구체적으로 맵은 다음 세 가지 필드로 구성됩니다.

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

그중 count는 맵의 요소 수를 나타내며, 플래그는 삭제 여부, 반복 여부 등을 포함하여 맵의 상태를 기록하는 데 사용됩니다. 2의 B승인 버킷 배열의 길이, hash0은 해시 함수 계산에 사용되는 해시 시드를 기록합니다.

buckets는 버킷 배열을 가리키는 포인터입니다. 버킷 배열의 형식은 다음과 같습니다.

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

그 중 tophash는 bucketCnt 길이의 배열입니다. 각 요소는 bmap의 요소를 나타내며 해당 값은 bmap에서 키-값 쌍을 찾는 데 사용되는 정수입니다. 데이터. 데이터는 키-값 쌍을 포함하는 길이 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 맵에서 구현되는 성능 최적화는 크게 다음 두 가지 측면으로 나뉩니다.

1. 버킷 배열 확장

맵의 요소 수가 버킷 배열의 용량을 초과하는 경우, 버킷 배열을 확장해야 합니다. 확장 방법은 새 버킷 배열을 추가하는 것입니다. 다음에 맵에 액세스하면 모든 키-값 쌍이 다시 계산되어 하나씩 새 버킷 배열로 이동됩니다. 이 프로세스를 재해시라고 합니다.

버킷 배열 확장 과정에서 Golang은 Randomized-Hashing이라는 기술을 사용합니다. 이 기술은 해시 시드를 조정하여 재해시 중에 키-값 쌍이 새 버킷 배열에 보다 균등하게 분산될 수 있도록 하여 해시 충돌을 줄입니다.

2. 내장 바이어스 잠금

Golang은 맵에서 바이어스 잠금이라는 잠금 메커니즘을 사용합니다. 편향된 잠금은 하나의 go 루틴에서만 잠금에 액세스하는 경우 이 goroutine의 스레드 ID를 사용하여 잠급니다. 이렇게 하면 이 go 루틴이 잠금을 잠금 해제하거나 다시 잠그야 할 때 다른 go 루틴이 잠금에 액세스하지 않으므로 스레드를 전환할 필요가 없습니다.

요약

Golang의 맵의 기본 데이터 구조는 해시 테이블입니다. 해당 버킷 배열은 무작위 해싱 기술을 사용하여 키-값 쌍을 다시 해시하고 잠금 및 잠금 해제를 위해 편향된 잠금 메커니즘을 사용합니다. 이러한 구현 세부 사항을 통해 Golang의 맵은 일부 일반적인 데이터 구조 작업에서 매우 잘 수행됩니다.

위 내용은 golang 맵 구현 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!