[Go] Map 원리와 활용(feat. hash)

소개

Go의 map은 매우 중요한 내장 자료구조로, key-value 형태의 해시 테이블(hash table) 기반 컨테이너입니다.

원리 (내부 구조)

Go의 map은 hash table을 기반으로 구현되어 있습니다.

핵심 개념

• Key → Hashing → Bucket → Value
• 해시 함수(hash(key))를 통해 버킷(bucket) 인덱스를 계산하고, 그 버킷에 key-value 쌍을 저장합니다.
• 해시 충돌이 발생하면 같은 버킷 안의 슬롯에 체이닝(chaining) 형태로 저장합니다.

내부 구조 개요

Go 런타임에서 map은 다음과 같은 구조로 관리됩니다 (runtime/map.go 참고):

type hmap struct {
    count     int           // 요소 개수
    flags     uint8
    B         uint8         // 버킷 수 = 2^B
    buckets   unsafe.Pointer // 실제 데이터 저장소
    oldbuckets unsafe.Pointer // 리사이징 중인 버킷
    ...
}

• 버킷 수(bucket count): 2^B
• 리사이징(resize): 요소가 많아지면 자동으로 버킷 크기가 2배가 됩니다.
• Load factor (평균 버킷당 원소 수)가 일정 기준 이상이면 재배열(rehashing) 수행.

---

사용법

기본 선언 및 초기화

// 빈 맵 선언
var m map[string]int  // nil 상태, 바로 사용 불가

// make를 사용한 초기화
m = make(map[string]int)

// 또는 한 줄 초기화
m := map[string]int{
    "apple":  3,
    "banana": 5,
}

삽입 (Insert / Update)

m["apple"] = 10  // 추가 또는 수정

조회 (Lookup)

val := m["apple"]     // 존재하지 않으면 0 (int의 zero value)
val, ok := m["apple"] // ok == true이면 존재

삭제 (Delete)

delete(m, "apple")

순회 (Iteration)

for key, value := range m {
    fmt.Println(key, value)
}

Go의 map은 iteration 순서가 매번 랜덤(randomized) 입니다. 보안성과 해시 공격 방지를 위해 설계상 순서가 보장되지 않습니다.

 

성능 및 동작 특성

장점

• 평균 접근 시간 O(1)
• 해시 기반이라 빠르고 효율적
• 키 타입으로 comparable한 타입 사용 가능 (== 비교 가능한 타입)

주의사항

1. Concurrent access 금지
   • 여러 고루틴이 동시에 읽기/쓰기 하면 fatal error: concurrent map read and map write
   • 해결 방법: sync.Mutex 또는 sync.RWMutex로 보호하거나, sync.Map 사용

   var mu sync.RWMutex
   mu.Lock()
   m["x"] = 1
   mu.Unlock()

2. Nil map 주의
3. var m map[string]int m["a"] = 1 // panic! (nil map에 할당 불가)
4. 순서 보장 X
   • 출력 순서가 매번 다름 → 순서를 원한다면 slice로 key를 정렬해야 함.

예제: 빈도 카운트

func main() {
    words := []string{"apple", "banana", "apple", "orange", "banana"}
    freq := make(map[string]int)

    for _, w := range words {
        freq[w]++ // 존재하지 않으면 0에서 시작
    }

    for k, v := range freq {
        fmt.Printf("%s: %d\\n", k, v)
    }
}

관련 개념 추천

• sync.Map: concurrent-safe map (lock-free, atomic 접근 지원)
• map[string]interface{}: JSON 파싱 시 자주 사용
• struct{}: value를 빈 구조체로 두어 set처럼 사용 가능

set := make(map[string]struct{}) 
set["A"] = struct{}{} 
if _, ok := set["A"]; ok { fmt.Println("exists") }

Go의 map은 해시 기반의 키-값 자료구조로, 평균 접근 시간은 O(1), 내부적으로 버킷 리사이징과 해시 분산을 통해 안정적인 성능을 제공합니다. 다만, 동시성 제어와 순서 비보장은 반드시 주의해야 합니다.