paint-brush
Go로 지도 마스터하기: 알아야 할 모든 것~에 의해@smokfyz
6,236 판독값
6,236 판독값

Go로 지도 마스터하기: 알아야 할 모든 것

~에 의해 Ivan Sharapenkov21m2024/04/27
Read on Terminal Reader

너무 오래; 읽다

이 기사에서는 기본 연관 배열부터 충돌 처리 전략이 포함된 고급 해시 맵까지 Go 프로그래밍에서 맵을 사용하는 데 필요한 필수 사항을 다룹니다. Go에서 맵 구현, sync.Map을 사용하여 동시성을 관리하는 방법을 자세히 살펴보고 맵 작업과 그 복잡성을 설명하는 실제 예제를 제공합니다. 이 토론의 목표는 다양한 프로그래밍 시나리오에서 맵을 효과적으로 사용하여 효율성과 성능을 모두 향상시키는 지식을 갖추는 것입니다.
featured image - Go로 지도 마스터하기: 알아야 할 모든 것
Ivan Sharapenkov HackerNoon profile picture
0-item
1-item
2-item


맵(연관 배열, 해시 테이블, 해시 맵, 해시 세트, 딕셔너리라고도 함)은 일상적인 작업, 프로그래밍 콘테스트 또는 면접 중에 다양한 알고리즘 문제를 해결하는 데 필수적인 데이터 구조입니다. 따라서 개발자에게 맵이 제공하는 기능, 즉 지원되는 작업, 다양한 작업의 시간 및 공간 복잡성, 코드에서 이 구조를 사용하는 방법을 이해하는 것이 중요합니다. 이러한 지식과 실제 경험을 활용하면 문제 해결을 위해 지도를 적용해야 하는 경우를 감지할 수 있습니다. 현재 읽고 있는 기사는 지도 사용에 대한 포괄적인 가이드를 제공합니다. 일반적인 지도 데이터 구조에 대한 간략한 개요부터 시작한 다음 Go 프로그래밍 언어의 지도 구현에 대해 자세히 알아보고 동시 코드에서 지도를 사용하기 위한 전략을 논의합니다.

초보자를 위한 지도

연관 배열

다양한 프로그래밍 언어로 구현된 모든 데이터 구조 뒤에 있는 중요한 개념인 추상 데이터 유형에 대해 논의하는 것부터 시작해 보겠습니다. 이는 데이터 유형이 지원하는 작업, 이러한 작업의 동작, 전달되거나 수신될 수 있는 가능한 값 측면에서 데이터 유형을 설명하는 데 사용되는 수학적 모델입니다. 연관 배열이라고 알려진 지도의 추상 데이터 유형도 있습니다.


연관 배열은 각 키가 컬렉션에 한 번만 나타나는 방식, 즉 컬렉션의 각 키에 대해 하나의 값만 있는 방식으로 키와 값 쌍의 컬렉션을 저장하는 데 사용되는 추상 데이터 유형입니다. . get , setdelete 작업을 지원합니다.


Go 프로그래밍 언어에서 키와 값 쌍(키와 값이 모두 문자열인 경우)을 저장할 수 있는 연관 배열의 구현이 있다고 가정하고 작업이 어떻게 보이는지 살펴보겠습니다.


 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set the value for the key "Alice". associativeArray.Set("Alice", "apple") // Attempt to retrieve and print the value associated with "Alice". valueForAlice, found := associativeArray.Get("Alice") if found { fmt.Println(valueForAlice) // Output: "apple" } else { fmt.Println("No value found for Alice.") } // Delete the entry associated with "Alice". associativeArray.Delete("Alice") // Attempt to retrieve the value for "Alice" after deletion to check error handling. valueForAlice, found = associativeArray.Get("Alice") if !found { fmt.Println("No value found for Alice. (Deleted)") } // Attempt to retrieve the value for "Bob" which was never set. valueForBob, found := associativeArray.Get("Bob") if !found { fmt.Println("No value found for Bob. (Never set)") } }


이전에 설정된 키를 설정하는 것은 유효한 작업이지만, 이 경우 새 값이 이전 키와 연결되어 이전 값을 검색할 수 없습니다. 연관 배열의 구현에 따라 삭제되거나 숨겨질 수 있습니다.


 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set value associated with "Alice" key associativeArray.Set("Alice", "apple") // Get value associated with "Alice" key valueForAlice := associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "apple" // Set new value associated with "Alice" key associativeArray.Set("Alice", "orange") // Get new value associated with "Alice" key valueForAlice = associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "orange" }


훌륭하지만 실제 생활에서 연관 배열을 구현하는 방법이 궁금할 수도 있습니다. 실제로 구현에는 제한이 없습니다. 상상할 수 있는 어떤 방식으로든 구현할 수 있습니다. 이 추상 데이터 유형에 필요한 작업만 지원하면 됩니다. 그러나 가장 일반적인 몇 가지 접근 방식은 해시 맵과 이진 검색 트리입니다. 둘 사이의 차이점은 시간과 공간의 복잡성, 물론 키와 값을 저장하고 검색하는 알고리즘에 있습니다. 앞으로 우리는 해시 맵 구현에 집중할 것이지만 이진 검색 트리를 연관 배열 구현에 사용할 수도 있다는 점은 주목할 가치가 있습니다.

해시 맵

우리는 해시 맵이 연관 배열 작업(키 값 설정, 키별로 값 검색, 키와 연관된 값 삭제)을 구현하는 데이터 구조라는 것을 알았습니다. 하지만 해시 맵은 내부적으로 어떻게 작동할까요? 알아 보자.


여기서 핵심 아이디어는 "해시"라는 단어 뒤에 숨겨져 있습니다. 해시 맵은 해시 함수를 사용하여 키를 해시 함수에 전달하여 값이 저장될 배열의 위치 인덱스를 계산합니다. Go 프로그래밍 언어를 사용하여 간단한 해시 맵을 구현하여 해시 함수와 배열이 함께 작동하여 해시 맵을 구축하는 방법을 살펴보겠습니다.


 package main import "fmt" func main() { // Define an array to hold string data array := make([]string, 10) // Hash function that returns an integer based on the key and array length hash := func(key string, length int) int { calculatedHash := 0 for _, char := range key { calculatedHash += int(char) } return calculatedHash % length } // Set operation: store a value associated with a key index := hash("Alice", len(array)) array[index] = "apple" // Get operation: retrieve the value associated with a key index = hash("Alice", len(array)) fmt.Println(array[index]) // Should print "apple" // Delete operation: remove the value associated with a key index = hash("Alice", len(array)) array[index] = "" // Setting it to empty string, assuming nil is not an option // Check if the deletion was successful index = hash("Alice", len(array)) if array[index] == "" { fmt.Println("Value deleted successfully.") } else { fmt.Println("Value still exists:", array[index]) } }


이는 실제로 실제 해시 맵이 작동하는 방식을 단순화한 것입니다. 경우에 따라 구현이 중단될 수 있음을 알 수 있습니다. 눈치채지 못했다면 계속 읽기 전에 잠시 시간을 내어 잠재적인 문제에 대해 생각해 보십시오.

충돌

이전 구현에서 문제가 무엇인지 알아냈습니까? 두 개의 서로 다른 문자열이 동일한 해시를 생성할 수 있는 상황입니다. 정확하게 말하면, 우리는 len(array) 가능한 해시 값만 가지고 있지만 서로 다른 키는 무한히 많습니다. 비둘기집 원리 에 따라 동일한 해시를 생성하는 두 개의 서로 다른 키를 찾을 수 있으며 이는 두 키가 동일한 위치에 해당한다는 것을 의미합니다. 배열에서.


우리는 그걸로 무엇을 할 것인가? 우리는 이 상황을 처리할 방법을 찾아야 합니다. 다행스럽게도 똑똑한 사람들은 이미 이 문제를 해결하고 몇 가지 잘 알려진 솔루션을 구현했으므로 바퀴를 재발명하는 대신 그냥 사용하도록 합시다.


  • 별도의 체인.

    이 접근 방식에서는 값을 배열에 직접 저장하는 대신 각 인덱스의 배열에 연결된 목록을 저장합니다. 맵에 새 값을 추가하면 먼저 동일한 키를 가진 항목이 있는지 검색합니다. 있는 경우 값을 업데이트하면 됩니다. 그렇지 않으면 연결된 목록에 새 항목을 추가합니다.


  • 공개 주소 지정

    개방형 주소 지정은 충돌 해결에 대한 또 다른 접근 방식입니다. 이제 각 배열 위치에 키와 값 쌍을 저장하겠습니다. 새로운 값을 추가하려고 할 때 이 위치에 이미 값이 있는 상황이 발생하면 프로빙을 사용하기 시작합니다. 프로빙은 다른 해싱 함수를 사용하여 선형, 2차 또는 무작위로 수행될 수 있습니다. 선형 프로빙에서는 기본 배열에서 여유 공간을 찾을 때까지 인덱스를 1씩 증가시키기 시작합니다. 배열에서 값을 검색하려고 할 때 배열 위치의 키가 검색 키와 일치하지 않는 상황에 직면할 때에도 동일한 프로세스가 발생합니다.


Go에서 구현된 접근 방식과 매우 유사하므로 별도의 연결 접근 방식의 구현을 살펴보겠습니다. 하지만 스키마를 검사하기 전에 해시 맵이 어떻게 보이는지 살펴보겠습니다.


별도의 체인이 포함된 해시 맵


 package main import ( "fmt" "hash/fnv" ) // Entry represents a key-value pair in the linked list type Entry struct { Key string Value string Next *Entry } // HashMap represents the hash table structure type HashMap struct { Buckets []*Entry Size int } // NewHashMap creates a new hash map with a given size func NewHashMap(size int) *HashMap { return &HashMap{ Buckets: make([]*Entry, size), Size: size, } } // HashFunction computes the bucket index for a given key func (h *HashMap) HashFunction(key string) int { hasher := fnv.New32() hasher.Write([]byte(key)) return int(hasher.Sum32()) % h.Size } // Insert adds a new key-value pair to the hash map func (h *HashMap) Set(key, value string) { index := h.HashFunction(key) entry := &Entry{Key: key, Value: value} if h.Buckets[index] == nil { h.Buckets[index] = entry } else { current := h.Buckets[index] for current.Next != nil { current = current.Next } current.Next = entry } } // Search finds the value for a given key in the hash map func (h *HashMap) Get(key string) (string, bool) { index := h.HashFunction(key) current := h.Buckets[index] for current != nil { if current.Key == key { return current.Value, true } current = current.Next } return "", false } // Delete removes an entry from the hash map based on the key func (h *HashMap) Delete(key string) { index := h.HashFunction(key) if h.Buckets[index] != nil { if h.Buckets[index].Key == key { h.Buckets[index] = h.Buckets[index].Next } else { current := h.Buckets[index] for current.Next != nil { if current.Next.Key == key { current.Next = current.Next.Next break } current = current.Next } } } } func main() { hm := NewHashMap(10) hm.Set("name", "John") hm.Set("age", "30") value, exists := hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } hm.Delete("name") value, exists = hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } } // OUTPUT: // Found: John // Not found

복잡성

이는 알고리즘 복잡성의 개념에 익숙하지 않은 사람들에게는 고급 주제일 수 있습니다. 이 설명에서 자신을 인식했다면 이 링크를 따라 이 개념에 대해 알아보십시오.


알고리즘과 데이터 구조를 추론할 때 시간과 공간의 복잡성은 코드 성능에 직접적인 영향을 미치기 때문에 매우 중요합니다. 이전 장에서 제공된 구현의 복잡성을 파악해 보겠습니다.


해시 맵에 새로운 키-값 쌍을 추가하려면 해시를 계산하고 인덱스에 있는 연결 목록을 찾은 다음 연결 목록을 통과하여 키를 찾아야 합니다. 시간 복잡도에 영향을 미칠 수 있는 첫 번째 요소는 키 크기입니다. 평균 키 크기는 작고 해시 함수의 시간 복잡도는 키 크기에 선형적으로 의존한다고 가정합니다. 이 경우 키 해시를 계산하는 평균 시간 복잡도는 O(1) 이라고 가정할 수 있습니다. 다음으로 연결 목록의 모든 항목을 통과해야 합니다. 항목 수는 충돌이 몇 번 발생했는지에 따라 달라지며, 최악의 경우 모든 항목이 동일한 해시에 해당하면 O(n) 이 됩니다. 따라서 추가 작업의 총 시간 복잡도는 최악과 평균 모두 O(1) + O(n) = O(n) 입니다.


로드 팩터라는 경험적 방법을 기반으로 기본 배열의 크기 조정을 구현하여 평균 시간 복잡성을 줄일 수 있습니다. 이는 단순히 해시 맵의 키 수를 기본 배열의 슬롯 수로 나눈 것입니다. 이 값이 특정 임계값을 초과하면 기본 배열의 크기를 조정하고 모든 값을 새 배열에 복사할 수 있습니다. 그 후에는 모든 연결 목록의 평균 크기가 제한됩니다. 이 경우 대부분의 경우 평균 시간 복잡도가 O(1) 이 되는 방식으로 로드 팩터 값을 찾을 수 있습니다. 여기서는 계산에 들어가지 않겠지만 이를 이해하는 것이 중요합니다.


따라서 해시 맵은 다음과 같은 시간 및 공간 복잡성 제약 조건을 제공합니다.

시간 복잡도: 모든 작업에 대해 평균 O(1) 입니다.

공간 복잡도: O(n) 각 키에 대해 하나의 연결 목록 엔터티를 저장하기 때문입니다.

Go의 지도

해시 맵 구현 이론에 대한 지식을 바탕으로 Go 프로그래밍 언어가 제공하는 내장 맵 유형이 무엇인지 살펴보겠습니다. Go에서 지도를 만드는 방법에는 여러 가지가 있습니다.


 package main func main() { // Using the make Function: This is the most common way to create a map. // You specify the type of the keys and values. m1 := make(map[string]int) // Create a map with string keys and integer values. // You can also optionally set the size of the underlying array using a second argument if // you know how many items you will store in the map before creation. m2 := make(map[string]int, 10) // Using Map Literals: This method is similar to array or slice literals and is // useful for initializing a map with some values. m3 := map[string]int{"one": 1, "two": 2} // Creates and initializes a map. // Nil Map: A map can also be declared without initialization. Such a map // is nil and has no keys, nor can it be added to. var m4 map[string]int // m4 is nil and you cannot add keys to it without initializing it first. // To add keys to a nil map, it must first be initialized using the make function. // m3["hello"] = 1 // Would panic. Map m3 is not nil here and will not cause a panic, this comment should refer to m4 or another nil map. m4 = make(map[string]int) // Now m4 is initialized and ready for use. }


Go 내장 맵 유형은 연관 배열에 필요한 세 가지 작업과 맵 항목을 반복하기 위한 추가 기능도 구현합니다.


 package main import "fmt" func main() { m := make(map[string]int) // Adding or updating an element. m["one"] = 1 // Retrieving an element and checking if a key exists. value, ok := m["four"] if ok { fmt.Println("Value exists in map:", value) } else { fmt.Println("Value doesn't exist.") } // Deleting an element. delete(m, "one") // You can iterate over a map using a for loop along with the range keyword. // This gives you access to each key and value in the map. // You shouldn't rely on the order of items; even if you run the for loop several times // in sequence, you can get a different order of items. It's a property of hash tables // in general. Items in the hash table do not have a particular order. for key, value := range m { fmt.Println(key, value) } }


비교 가능한 모든 유형은 Go 맵의 키가 될 수 있습니다. 비교 가능한 유형에는 부울, 숫자, 문자열, 포인터, 채널 및 인터페이스 유형뿐만 아니라 비교 가능한 유형만 포함하는 구조체 또는 배열이 포함됩니다. 또한 맵에서 값으로 사용할 수 있는 유형에는 사실상 제한이 없습니다. 정수 및 문자열과 같은 간단한 유형부터 슬라이스, 기타 맵 또는 함수와 같은 복잡한 유형까지 무엇이든 될 수 있습니다.

Go 지도 자세히 알아보기

이제 지도 소스 코드를 탐색하여 지도 구현을 살펴보겠습니다. 이는 지도가 내부적으로 어떻게 구현되는지 더 잘 이해하는 데 도움이 됩니다. Go 지도의 소스 코드는 여기에서 찾을 수 있습니다.


Go의 맵은 앞서 설명한 해시 맵을 구현한 것입니다. 이전 예에서는 충돌 해결을 위해 연결 목록을 사용했습니다. Go는 다른 접근 방식을 사용합니다. 연결된 목록 대신 각 기본 배열 인덱스에 다른 하위 배열인 버킷이 있습니다. 따라서 본질적으로 기본 배열은 2차원 하위 배열입니다. 각 버킷에는 최대 8개의 키-값 쌍이 포함됩니다. 8개 이상의 키가 버킷에 해시되면 추가 버킷을 기존 오버플로 버킷에 연결합니다. 해시의 하위 비트는 버킷을 선택하는 데 사용됩니다. 각 버킷에는 단일 버킷 내의 항목을 구별하기 위해 각 해시의 몇 가지 상위 비트가 포함되어 있습니다. 맵이 커지면 두 배 크기의 새로운 버킷 배열을 할당합니다. 버킷은 이전 버킷 배열에서 새 버킷 배열로 증분 복사됩니다.


맵을 나타내는 주요 구조는 hmapbmap 이라고 합니다. 단순화를 위해 구조체의 일부 도우미 필드를 건너뜁니다. 알고리즘의 아이디어를 이해하는 데는 중요하지 않습니다.


 type hmap struct { count int // # of live cells == size of map. Must be first (used by len() builtin) buckets unsafe.Pointer // array of 2^B Buckets; may be nil if count==0. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing // some other fields... } // A bucket for a Go map. 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 [abi.MapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // Followed by an overflow pointer. }


count 현재 맵에 저장된 항목 수입니다. buckets 새 항목을 저장하는 기본 배열이고, oldbuckets 맵 크기가 조정되기 전에 항목을 저장한 배열입니다. Go에서는 크기 조정 시 지도 항목을 이동하는 대신 점진적으로 수행합니다. bucketsoldbuckets tophash (버킷에 저장된 각 키에 대한 해시의 첫 번째 바이트 배열)를 저장하는 bmap 구조체를 가리키는 포인터입니다. 그 뒤에는 MapBucketCount 키와 MapBucketCount 값이 있고 끝에는 오버플로 포인터가 있습니다. MapBucketCount 는 문서에 따르면 아키텍처별 값으로 8을 넘지 않습니다. 지도가 메모리에서 어떻게 보이는지 더 잘 이해하기 위해 다음 그림을 참조하세요.


메모리에 지도 표현


키와 관련된 값을 찾으려면 먼저 키가 있는 버킷을 결정하는 데 사용할 해시를 계산해야 합니다. 이를 위해 Go는 아키텍처와 해시해야 하는 유형에 따라 다양한 해시 함수를 사용합니다. 해시를 계산한 후 Go는 마지막 몇 비트를 사용하여 키가 위치할 수 있는 인덱스를 계산합니다. Go는 또한 해시의 첫 번째 바이트를 tophash 배열에 저장하고, 키의 해시를 사용하여 tophash 사용하여 버킷에서 가능한 키 인덱스를 쉽게 찾을 수 있습니다. 그 후에는 해시의 첫 번째 바이트 사이에도 충돌이 있을 수 있으므로 검색된 키와 버킷에 저장된 키를 비교해야 합니다. 이 과정이 그림에 표현되어 있습니다.


키를 이용하여 가치를 찾는 과정

동시성: 맵 대 sync.Map

동시 지도

맵의 내부 구현을 고려했지만 Go는 동시성이 높은 코드를 개발하도록 설계된 언어입니다. 두 개 이상의 고루틴이 동시에 맵에서 작업을 수행하는 경우 맵을 어떻게 사용합니까? 두 가지 경우를 고려해 보겠습니다. 동시에 실행 중인 두 개의 고루틴이 이전에 초기화된 맵에서 일부 값을 읽는 경우와 고루틴이 쓰기 작업을 수행하는 경우입니다.


공유 맵에서 일부 값을 읽기 위해 동시에 실행되는 두 개의 고루틴의 경우, 읽기 작업 중에 맵의 내부 상태가 변경되지 않기 때문에 문제가 발생하지 않습니다. 따라서 안전하게 동시에 읽을 수 있습니다.


 package main import ( "fmt" "sync" ) func main() { var wg sync.WaitGroup m := make(map[string]int) m["a"] = 1 m["b"] = 2 readMap := func(key string) { value, ok := m[key] if ok { fmt.Println("Read:", key, value) } else { fmt.Println("Key not found:", key) } wg.Done() } wg.Add(2) go readMap("a") go readMap("b") wg.Wait() }


반면, 동시 쓰기를 수행하면 쓰기 작업 중에 맵의 상태가 변경될 수 있습니다. 이전 섹션에서 이미 살펴본 것처럼 쓰기 작업은 원자적이지 않습니다. 즉, 맵 수정 단계 사이에 다른 작업이 있을 수 있으며, 다른 쓰기 프로세스 중에 읽거나 쓰려고 하면 잘못된 상태의 맵에 직면할 수 있습니다. Go는 맵에 동시 쓰기를 수행하려고 시도하면 fatal error: concurrent map writes 발생시키는지 감지할 만큼 똑똑합니다.


이 문제를 처리하려면 Mutex를 사용해야 합니다. Mutex는 여러 실행 스레드가 동시에 상태를 수정하거나 액세스하는 것을 방지하는 동기화 기본 요소입니다. 이는 원자적으로 실행되므로 안전한 잠금 및 잠금 해제라는 두 가지 작업을 지원합니다. 실제로 우리는 RWMutex를 사용할 수 있는데, 이는 여러 판독기의 읽기에 대해서는 잠금을 허용하지만 쓰기에 대해서는 하나만 잠글 수 있습니다. 이는 읽기가 많은 경우 성능을 최적화하는 데 도움이 될 수 있습니다. 동시 안전 맵 구현을 살펴보겠습니다.


 package main import ( "fmt" "sync" ) // ConcurrentMap wraps a Go map with a sync.RWMutex to manage concurrent access with optimized read performance type ConcurrentMap struct { sync.RWMutex items map[string]interface{} } // NewConcurrentMap creates a new concurrent map func NewConcurrentMap() *ConcurrentMap { return &ConcurrentMap{ items: make(map[string]interface{}), } } // Set adds or updates an element in the map func (m *ConcurrentMap) Set(key string, value interface{}) { m.Lock() defer m.Unlock() m.items[key] = value } // Get retrieves an element from the map func (m *ConcurrentMap) Get(key string) (interface{}, bool) { m.RLock() defer m.RUnlock() value, exists := m.items[key] return value, exists } // Delete removes an element from the map func (m *ConcurrentMap) Delete(key string) { m.Lock() defer m.Unlock() delete(m.items, key) } // Items returns a copy of all items in the map for safe iteration func (m *ConcurrentMap) Items() map[string]interface{} { m.RLock() defer m.RUnlock() itemsCopy := make(map[string]interface{}) for key, value := range m.items { itemsCopy[key] = value } return itemsCopy } func main() { cmap := NewConcurrentMap() cmap.Set("name", "John Doe") cmap.Set("age", 30) if name, ok := cmap.Get("name"); ok { fmt.Println("Name:", name) } if age, ok := cmap.Get("age"); ok { fmt.Println("Age:", age) } items := cmap.Items() fmt.Println("All items:", items) }


동기화.지도

표준 패키지에는 동시 안전 맵 구현이 하나 더 있습니다: sync.Map. 하지만 언제 sync.Map이나 Mutex가 있는 맵을 사용해야 할까요? 이제 그것을 알아낼 시간입니다. 문서에 따르면 지도 유형은 두 가지 일반적인 사용 사례에 최적화되어 있습니다.


  1. 특정 키에 대한 항목이 한 번만 기록되고 여러 번 읽히는 경우(예: 캐시의 크기가 커지는 경우)

  2. 여러 고루틴이 분리된 키 세트에 대한 항목을 읽고, 쓰고, 덮어쓸 때. 이 두 가지 경우에 Map을 사용하면 별도의 Mutex 또는 RWMutex와 쌍을 이루는 Go 맵에 비해 잠금 경합을 크게 줄일 수 있습니다.


이러한 경우 Mutex가 포함된 맵보다 sync.Map이 더 잘 작동하는 이유를 더 잘 이해하고 개발하려면 sync.Map의 소스 코드를 조사해야 합니다.


 type Map struct { mu Mutex read atomic.Pointer[readOnly] dirty map[any]*entry // some other fields... } // readOnly is an immutable struct stored atomically in the Map.read field. type readOnly struct { m map[any]*entry amended bool // true if the dirty map contains some key not in m. } // An entry is a slot in the map corresponding to a particular key. type entry struct { p atomic.Pointer[any] }


Map 지도 데이터의 두 가지 표현( readdirty 을 유지합니다. 읽기 맵( read ): 이는 Map 의 기본 데이터 저장소이며 동시 읽기 액세스를 위한 것입니다. 이는 readOnly 구조체에 대한 atomic.Pointer 로 표시되며 맵 스냅샷의 원자성 및 잠금 없는 읽기를 보장합니다. 키를 조회하면 먼저 read 맵을 확인합니다. 키를 찾을 수 없고 맵이 amended 것으로 표시되면(아직 read 맵에 없는 dirty 맵에 새 키가 있음을 나타냄) 뮤텍스 잠금( mu ) 하에서 dirty 맵을 확인하는 것으로 대체됩니다. 더티 맵( dirty ): 이 맵은 수정 중인 항목과 read 맵에 아직 표시되지 않은 새 항목을 저장합니다. 이 맵에 액세스하려면 단독 액세스를 보장하기 위해 뮤텍스 잠금을 유지해야 합니다. 쓰기 작업 시 키가 read 맵에 없거나 업데이트해야 하는 경우 dirty 맵에서 작업이 진행됩니다. dirty 맵이 nil 인 경우 더 이상 유효하지 않은 항목을 제외하고 read 맵의 얕은 복사본을 만들어 초기화됩니다. 특정 임계값의 "누락"( dirty 맵으로 대체해야 하는 실패한 조회) 후에 dirty 맵은 새 read 맵으로 승격되고 필요한 경우 새 dirty 맵이 준비됩니다.

Mutex가 포함된 내장 Go 맵과의 차이점

이제 Mutex가 포함된 내장 맵과 sync.Map의 차이점을 알아낼 수 있습니다.


  1. 잠금 경합 :
    • sync.Map : 잠금 경합을 최소화하도록 설계되었습니다. 대부분의 읽기 작업에서는 원자성 read 포인터로 인해 잠금이 필요하지 않습니다. 맵의 작은 부분에만 영향을 미치는 쓰기 및 삭제도 dirty 맵만 잠그기 때문에 잠금 기간을 최소화합니다.
    • 뮤텍스가 포함된 내장 맵 : 모든 액세스(읽기 또는 쓰기)에는 뮤텍스를 획득해야 하며, 이는 높은 동시성 시나리오에서 병목 현상이 될 수 있습니다.
  2. 메모리 오버헤드 및 복잡성 :
    • sync.Map : 지도의 두 가지 버전을 유지 관리하며 메모리를 더 많이 사용할 수 있습니다. 이러한 버전을 관리하는 논리는 복잡성을 더합니다.
    • Mutex가 포함된 내장 맵 : 맵의 한 버전만 유지하므로 sync.Map 에 비해 더 간단하고 메모리를 덜 사용합니다.
  3. 사용 사례 특이성 :
    • sync.Map : 키가 대부분 읽혀지고 자주 업데이트되지 않거나 분리된 키 집합에서 많은 작업이 발생하는 사용 사례에 최적화되었습니다.
    • Mutex가 포함된 내장 맵 : 범용적이고 사용하기 쉽지만 범용 잠금 경합으로 인해 특정 높은 동시성 시나리오에서는 제대로 작동하지 않을 수 있습니다.


요약하자면, sync.Map 동시성 최적화를 활용하여 잠금 경합을 줄이면서 복잡성과 메모리 사용량이 증가하는 시나리오에 특화되어 있습니다. 이와 대조적으로 뮤텍스가 있는 표준 Go 맵은 더 간단하고 일반적인 솔루션이지만 동시성이 높은 환경에서는 성능 문제가 발생할 수 있습니다.

마무리

이 기사 전체에서 우리는 특히 Go 프로그래밍 언어의 구현 및 사용법에 중점을 두고 지도 데이터 구조 사용의 복잡성을 탐구했습니다. 연관 배열의 기본 개념부터 시작하여 해시 맵의 메커니즘을 탐구하고 해시 맵의 작동 절차, 시간 및 공간 복잡성, 충돌을 처리하기 위한 별도의 연결 및 개방형 주소 지정과 같은 다양한 접근 방식을 논의했습니다.


Go 영역에서는 hmapbmap 과 같은 기본 구조를 조사하여 맵이 언어에 어떻게 활용되고 구축되는지 조사했습니다. 이 탐색에는 Go 애플리케이션에서 지도를 초기화, 조작 및 효과적으로 사용하는 방법을 보여주는 실용적인 코드 예제가 포함되었습니다. 또한 맵을 사용할 때 동시성의 잠재적 위험을 강조하고 동시 액세스가 필요한 시나리오를 위해 잠금 경합을 줄이고 성능을 최적화하는 sync.Map 도입했습니다.


지도 데이터 구조의 이러한 측면을 이해하면 코딩 툴킷이 향상될 뿐만 아니라 더 큰 효율성과 자신감을 갖고 일반적인 프로그래밍 문제를 해결할 수 있도록 준비됩니다. 동시 환경에서 최적의 성능이 필요한 간단한 애플리케이션을 개발하든, 복잡한 시스템을 개발하든 관계없이 다양한 유형의 맵을 사용하는 방법과 시기에 대한 지식은 매우 중요합니다. 계속해서 프로그래밍 전문 지식을 쌓으면서 이러한 구조와 다양한 구현을 계속 실험하여 프로젝트에서 잠재력을 최대한 활용하세요.