golang 맵 구현 원리

Golang을 학습하는 과정에서 맵은 우리가 자주 사용하는 데이터 구조로, 키-값 쌍을 저장하는 데 사용할 수 있습니다. 그런데 지도가 어떻게 구현되는지 생각해 본 적이 있나요? 이번 글에서는 Golang에서 map이 어떻게 구현되는지 살펴보겠습니다.

map 구현 원리 소개

map은 실제로는 해시 테이블이고 구현 원리는 해시 알고리즘입니다. 해시 테이블은 키를 기반으로 메모리 저장 위치에 직접 액세스하는 데이터 구조입니다. 즉, 키를 메모리 주소에 매핑하는 방법을 제공합니다. 해시 테이블에서는 키워드를 "키"라고 하며, 해시 함수에 의해 계산된 메모리 주소를 "버킷"이라고 합니다. 버킷은 키-값 쌍을 저장합니다.

Golang에서는 버킷 메모리 영역에 키-값 쌍을 저장하여 맵을 구현합니다. 각 버킷에는 버킷의 상태를 설명하는 데 사용되는 헤더 구조가 있습니다.

버킷 데이터 구조

버킷 데이터 구조를 먼저 살펴보겠습니다.

type bmap struct {
    tophash [bucketCnt]uint8
    // data 的类型在 map 被分配空间的时候由 map 的 key 和 value 类型决定
    // 如果 key 类型和 value 类型都是未知类型，那么 data 的类型是 byte
    // 因为 byte 可以用于存储任何类型，也就是说 data 可以存储任何类型的 key 和 value
    // 在存储 key 和 value 的时候，需要将 key 和 value 转换成 uintptr，然后再转换成 byte 存储到 data 中
    // 读取 key 和 value 的时候反向操作即可
    // 因此，map 中的 key 和 value 一般都是需要转换成 uintptr 类型的
    // 这里我们可以简单地理解为 data 存储了键值对的二进制数据
    // 第一个 bucket 中如果存不下某个 key-value，还需要在第二个 bucket 中存储
    // 所以，data 的长度可以为 1 或 2
    // 当 data 的长度为 1 或 2 时，存储的键值对的个数分别为 1 或 2
    // 因此，bucket 中最多只能存储 8 个键值对
    // 否则，就需要将键值对存储在 overflow 中
    // overflow 是一个指向单链表头部的指针数组
    // 如果某个桶存储的键值对数量超过了 8，那么就将多余的键值对存储到 overflow 中
    // overflow 中的第一个 bucket 中也是能够存储 8 个键值对的，如果第一个 bucket 中存不下的话
    // 那么还需要在第二个 bucket 中继续存储
    // 所以，overflow 数组的长度也可以为 1 或 2
    // 当 overflow 数组长度为 1 或 2 时，最多存储 8 个键值对的 overflow
    // 当 overflow 数组长度为 3 时，最多存储 24 个键值对的 overflow
    // 也就是说，如果 map 中存储的键值对数量很多的话，那么可能会有很多个 overflow 桶
    // 而 overflow 数组是动态分配的，因此它的长度是不定的，只有在运行时才能确定
    data unsafe.Pointer
    // overflow 是一个指针数组，用于存储除当前桶以外的其它桶
    // 如果某个桶的键值对数量超过了 8，那么它会将多余的键值对存储到 overflow 中
    // overflow 数组中的每个元素都是一个 bucket 指针
    // 这些 bucket 指针构成了一个链表，也就是所谓的 overflow 链表
    overflow *[]*bmap
    // 这里存储的是这个 bucket 当前存储的键值对的个数
    count int16
    // flags 存储了 bucket 的标志
    // 一个 bucket 可能会有如下三种状态：
    // 1. empty，表示这个 bucket 没有存储任何键值对
    // 2. iterator，表示这个 bucket 正在被访问，不能再被其它操作使用
    // 3. deleted，表示这个 bucket 存储的键值对已经被删除了
    // 注意，该标志位只有在 GC 达到一定阈值后才会被置为 true，而且并不是立即删除键值对，而是在下一次 GC 的时候才会内存回收
    flags uint8
    // Bmap 的类型标记
    // Bmap 用来标识存储于上文中 data 指针中的数据类型
    // 如果 data 中存储的是 int，那么 Bmap 的值为 hmap.BmapInt
    // 如果 data 中存储的是 string，那么 Bmap 的值为 hmap.BmapString
    // 如果 data 中存储的是 interface{}，那么 Bmap 的值为 hmap.BmapInterface
    // 如果 data 中存储其他类型，那么 Bmap 的值为 hmap.BmapOther
    BmapType uint16
    // 与该 bucket 相关联的 key 的类型
    tophash0 uint8
}

위 정의에서 버킷에 다음 정보가 저장되어 있음을 알 수 있습니다.

• tophash: 일치하지 않는 키를 빠르게 필터링하는 데 사용됩니다. ;
• data: 키-값 쌍의 데이터를 저장합니다.
• overflow: 오버플로 연결 목록의 포인터 배열을 저장합니다.
• count: 현재 버킷에 저장된 키-값 쌍의 수를 최대 8개까지 저장합니다. : 저장 버킷의 일부 상태 정보
• BmapType: 데이터에 저장된 데이터 유형을 저장합니다.
• tophash0: 버킷과 연결된 키 유형.
• 구현 원칙

맵에 저장된 데이터는 키-값 쌍이고, 키-값 쌍의 키값은 반복 불가능하고 비교가 가능하므로 해시 함수를 사용하여 키값을 변환할 수 있습니다. 고유한 해시 해시 값으로 변환한 다음 해시 값을 키 값에 해당하는 인덱스로 사용하고 값 값을 인덱스에 저장합니다.

Golang에서는 각 맵에 해시 테이블이 있습니다. 이 해시 테이블은 실제로 여러 개의 버킷을 저장할 수 있는 연속적인 저장 공간입니다.

그렇다면 해시 테이블의 크기는 어떻게 결정되나요? 맵 생성 시 동적으로 메모리가 할당되며, 처음 공간을 할당할 때 사용되는 기본 크기는 8버킷이다. 처음으로 요소를 추가할 때 버킷 수가 충분하지 않으면 해시 테이블의 크기가 확장되고 해시 테이블에 있는 각 요소의 인덱스 위치가 다시 계산됩니다.

Golang에서 해시 함수의 주요 기능은 키 값을 해시 테이블의 버킷에 보다 편리하게 위치할 수 있도록 해싱하여 키 값에 해당하는 값 값을 빠르게 검색하는 것입니다. Golang에서는 MurmurHash3 알고리즘을 사용하여 해시 함수를 구현합니다.

해시 함수는 키를 정수로 매핑하므로 서로 다른 키 값이 동일한 인덱스에 매핑될 수 있습니다. 이러한 상황을 해시 충돌이라고 합니다. 해시 충돌이 발생하면 Golang은 연결된 목록 방법을 사용하여 이를 해결하며, 이러한 키-값 쌍을 인덱스의 연결된 목록에 있는 동일한 인덱스에 저장합니다.

요약

Golang의 지도 구현 원리는 주로 해시 테이블과 해시 함수에 의존합니다. 해시 함수를 사용하여 키 값을 해시하여 해시 테이블의 버킷에 매핑함으로써 값 조회 작업 속도를 높입니다. 해시 테이블은 여러 개의 버킷으로 구성되며, 각 버킷은 키-값 쌍 정보를 저장하는 버킷 유형 구조로 표시됩니다. 해시 테이블의 동일한 인덱스 위치에 여러 개의 키-값 쌍이 있는 경우 연결 목록 방법을 사용하여 오버플로를 저장합니다. Golang의 맵은 실제로 해시 테이블의 크기를 동적으로 조정할 수 있는 동적 해시 테이블입니다. 맵을 사용할 때 해시 충돌을 방지하고 비교할 수 없는 크기의 유형을 키로 포함하도록 주의를 기울여야 합니다.

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