19장. 맵 깊이 이해하기

12장에서 맵의 기본 사용법을 익혔다. 선언하고, 값을 넣고, 키로 꺼내고, 삭제하는 정도였다.

이번엔 한 층 더 내려간다.

• 맵 안쪽은 어떻게 생겼는가
• 왜 그렇게 빠른가
• 왜 가끔은 느려지는가
• 왜 순회 순서가 매번 다른가
• 왜 동시 접근에 안전하지 않은가

내부 구조를 알면 함정을 피할 수 있고, “맵을 써야 할지 슬라이스를 써야 할지” 같은 결정도 근거를 갖고 내릴 수 있게 된다.

이 장의 목표는 세 가지다.

• 해시 테이블이 어떻게 동작하는지 큰 그림으로 이해하기
• Go 맵의 특이한 성질들을 그 이유까지 알기
• 맵을 잘 쓰는 패턴 몇 가지를 손에 익히기

Big-O 표기는 도구로만 쓴다. 표기 자체가 낯설면 다른 자료를 한 번 훑어 두고 오자.

19.1 해시 테이블이란

맵은 내부적으로 해시 테이블(hash table)이다. 이름은 거창하지만 발상은 단순하다.

“키를 숫자로 바꿔서 그 숫자를 배열 인덱스로 쓰자.”

배열의 인덱스 접근이 O(1) 이라는 점에 기댄 아이디어다.

단계별로 따라가기

m["apple"] = 100 을 저장하는 과정을 그려 보자.

1단계. 해시 함수가 키를 큰 정수로 바꾼다.

"apple" ──[해시 함수]──→ 0x9F4A...8B2D (큰 정수)

2단계. 그 정수를 버킷 개수로 나눈 나머지를 구한다.

0x9F4A...8B2D % 8 = 3

3단계. 3번 버킷에 (“apple”, 100) 을 저장한다.

버킷 0: [          ]
버킷 1: [          ]
버킷 2: [          ]
버킷 3: [ apple=100 ]  ← 여기
버킷 4: [          ]
버킷 5: [          ]
버킷 6: [          ]
버킷 7: [          ]

조회할 때는 같은 과정이다.

"apple" → 해시 → 0x9F4A...8B2D → % 8 → 3번 버킷에서 "apple" 찾기

키만 알면 어디로 가야 할지 즉시 안다. 이게 평균 O(1) 의 비밀이다.

해시 함수의 역할

좋은 해시 함수의 조건은 두 가지다.

• 빠르게 계산된다
• 결과가 골고루 흩어진다 (편중되지 않음)

값이 골고루 흩어져야 모든 버킷에 비슷한 수의 키가 들어간다. 한 버킷에만 몰리면 그 안에서 다시 찾아야 하니 O(1) 의 환상이 깨진다.

Go 의 해시 함수는 런타임이 알아서 골라 준다. 사용자가 신경 쓸 필요는 없다.

충돌(collision)

해시 함수가 아무리 잘 만들어져도, 서로 다른 키가 같은 버킷으로 가는 일은 반드시 생긴다.

"apple"  → 3번 버킷
"orange" → 3번 버킷  ← 충돌!

이걸 어떻게 처리하느냐가 해시 테이블 설계의 핵심 주제다.

19.2 Go 맵의 내부 구조

Go 맵은 표준적인 해시 테이블 구현이다. 실제 구조를 단순화해서 그리면 이렇다.

버킷 배열

맵은 내부적으로 버킷의 배열을 갖고 있다.

hmap (맵 헤더)
 │
 ├─ count: 5         (원소 개수)
 ├─ B: 3             (버킷 개수의 로그 — 2^3 = 8개)
 └─ buckets:
      ┌──────────────────────┐
      │ bucket 0             │
      ├──────────────────────┤
      │ bucket 1             │
      ├──────────────────────┤
      │ ...                  │
      ├──────────────────────┤
      │ bucket 7             │
      └──────────────────────┘

각 버킷은 보통 한 자리짜리가 아니라 여러 키-값 쌍을 담을 수 있는 작은 슬롯 모음이다.

bucket 3
 ┌────────────────────────────┐
 │ slot 0: "apple"   → 100    │
 │ slot 1: "grape"   → 50     │
 │ slot 2: (비어 있음)         │
 │ ...                         │
 │ overflow → 다른 버킷 포인터  │
 └────────────────────────────┘

충돌 해결: chaining

Go 맵은 같은 버킷에 들어온 키들을 그 안에 묶어 둔다. 이 방식을 chaining (체이닝) 이라 부른다.

같은 버킷에 자리가 부족하면 “오버플로우 버킷” 을 매달아 사슬처럼 잇는다.

bucket 3                  overflow bucket
 ┌──────────────┐          ┌──────────────┐
 │ apple → 100  │          │ peach → 75   │
 │ grape → 50   │   ──→    │ lemon → 30   │
 │ kiwi  → 90   │          │              │
 │ overflow →   │          └──────────────┘
 └──────────────┘

조회 시에는 같은 버킷의 슬롯을 차례로 비교하면서 정확한 키를 찾는다. 한 버킷의 슬롯 수는 작은 상수라 이 안에서의 선형 탐색은 무시할 만하다.

로드 팩터

해시 테이블의 핵심 지표가 로드 팩터(load factor) 다.

로드 팩터 = 원소 수 / 버킷 수

• 너무 작으면 (= 버킷이 텅 빔): 메모리 낭비
• 너무 크면 (= 버킷마다 많이 몰림): 충돌 잦아져 느려짐

Go 는 로드 팩터가 일정 임계치 (대략 6.5) 를 넘으면 버킷 개수를 두 배로 늘려 충돌을 줄인다.

19.3 동적 확장 (resize / rehash)

맵에 키가 점점 쌓이면 로드 팩터가 커진다. 임계치를 넘는 순간 맵은 스스로를 확장한다.

무슨 일이 일어나는가

1. 새 버킷 배열을 만든다 (보통 2배 크기)
2. 기존 버킷에 있던 키-값을 새 자리로 옮긴다
3. 옮기는 과정에서 해시 값을 새 버킷 수로 다시 나눈다 (rehash)

확장 전 (버킷 8개)         확장 후 (버킷 16개)
┌────────────────┐         ┌────────────────┐
│ bucket 0       │         │ bucket  0      │
│ bucket 1       │         │ bucket  1      │
│ ...            │         │ ...            │
│ bucket 7       │         │ bucket 15      │
└────────────────┘         └────────────────┘
                              ↑
                       이 안에 새 자리에서
                       키들이 다시 흩어져 들어감

점진적 이주 (incremental rehashing)

키가 백만 개라면 한 번에 옮기다가 멈춤이 발생할 수 있다. Go 는 이걸 한 번에 다 하지 않는다. 대신 이후 맵 연산 (get, set, delete) 때마다 조금씩 옮긴다.

• 새 버킷이 만들어지면 일단 이주 시작 상태로 표시
• 매 연산 때 관련 버킷 한두 개씩 옮김
• 다 옮겨지면 옛 버킷 배열을 버림

덕분에 큰 맵도 한 번에 멎지 않는다. 대신 트레이드오프가 있다.

왜 가끔 맵 연산이 느려질 수 있나

이주 중인 맵은 모든 연산이 평소보다 살짝 비싸다. 원인은 다음과 같다.

• 키를 찾을 때 옛 버킷과 새 버킷 양쪽을 봐야 함
• 매 연산이 이주를 조금씩 수행함

벤치마크에서 가끔 튀는 지점이 생기는 이유다. “맵은 평균 O(1)” 이라는 말이 “항상 O(1)” 이 아닌 까닭이기도 하다.

그래서 큰 맵을 만들 게 예상되면 make(map[K]V, sizeHint) 으로 미리 용량을 지정하는 게 좋다. 초반에 일어날 여러 번의 확장을 피할 수 있다.

// 100만 개를 넣을 예정이라면
m := make(map[string]int, 1_000_000)

19.4 흥미로운 특성들

Go 맵에는 처음 만나면 갸우뚱하는 특성들이 있다. 각각의 이유를 짚어 보자.

순회 순서가 매번 다르다

같은 맵을 두 번 순회해도 순서가 다를 수 있다.

package main

import "fmt"

func main() {
	m := map[string]int{
		"a": 1, "b": 2, "c": 3, "d": 4, "e": 5,
	}

	fmt.Println("첫 번째 순회:")
	for k, v := range m {
		fmt.Println(k, v)
	}

	fmt.Println("두 번째 순회:")
	for k, v := range m {
		fmt.Println(k, v)
	}
}

실행할 때마다, 그리고 같은 실행 안에서도 두 번째 순회는 첫 번째와 다른 순서일 수 있다.

이건 버그가 아니라 의도된 설계다.

왜 일부러 무작위로 만들었나

Go 팀은 다음 시나리오를 막고 싶었다.

• 개발자가 우연히 한 순서에 맞춰 코드를 짠다
• Go 버전 업데이트로 내부 알고리즘이 바뀌면 순서도 바뀐다
• 멀쩡하던 코드가 갑자기 망가진다

그래서 처음부터 “순서에 의존할 수 없다” 는 사실을 강제로 드러내 놓았다. 순회 시작점을 매번 살짝 흔드는 식이다.

정렬된 순서가 필요하면 키들을 슬라이스로 뽑은 뒤 sort.Strings 등으로 정렬해서 순회한다.

import "sort"

keys := make([]string, 0, len(m))
for k := range m {
	keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
	fmt.Println(k, m[k])
}

동시 접근에 안전하지 않다

여러 고루틴이 같은 맵을 동시에 읽고 쓰면 프로그램이 죽거나 데이터가 깨진다.

package main

func main() {
	m := map[int]int{}

	for i := 0; i < 1000; i++ {
		go func(i int) { m[i] = i }(i)  // 위험
	}

	select {}
}

go run -race main.go 로 실행하면 경고와 함께 패닉이 난다.

fatal error: concurrent map writes

이유는 단순하다. 앞서 본 확장 / 이주 과정에서 한 고루틴이 버킷 구조를 바꾸는 중에 다른 고루틴이 그 버킷을 읽으면 일관되지 않은 상태를 보게 된다.

해결책은 두 가지다.

• sync.Mutex 로 직접 보호
• 표준 라이브러리의 sync.Map 사용

둘 다 동시성 챕터 (24장 / 25장) 에서 본격적으로 다룬다. 지금은 “그냥 맵은 동시 접근에 안전하지 않다” 정도만 머리에 새겨 두자.

19.5 nil 맵의 함정

맵 선언 방식에 따라 동작이 미묘하게 달라진다. 한 번쯤 호되게 당하고 기억하게 되는 함정이다.

두 가지 선언

var m1 map[string]int          // nil 맵
m2 := make(map[string]int)     // 빈 맵 (사용 가능)

겉으로 둘 다 비어 있지만 내부 상태가 다르다.

핵심은 굵게 표시한 한 줄이다. nil 맵에 쓰려고 하면 다음과 같이 죽는다.

panic: assignment to entry in nil map

왜 그렇게 동작하나

• nil 맵은 “맵을 가리키는 포인터가 비어 있는 상태”
• 읽기는 “어떤 키도 없는 셈” 으로 처리해서 제로값 반환
• 쓰기는 “어디에 쓸지가 없는 상태” 라 어쩔 수 없이 패닉

읽기와 쓰기의 안전성이 비대칭이라 함수에서 맵을 반환받았을 때 무심코 쓰다가 사고가 난다.

안전한 패턴

type Config struct {
	flags map[string]bool
}

// 생성 시 반드시 초기화
func NewConfig() *Config {
	return &Config{
		flags: make(map[string]bool),
	}
}

구조체 안의 맵 필드는 생성자에서 초기화하는 습관을 들이자.

map[K]V 타입 반환값이 nil 일 수 있는 함수는 호출 측에서 if m == nil 체크를 하든지 명시적으로 빈 맵을 반환하도록 정해 두자.

19.6 맵 vs 슬라이스 검색 속도 실험

머리로만 “맵이 빠르다” 라고 외우는 건 약하다. 숫자로 직접 보자.

다음은 같은 값을 슬라이스 선형 탐색과 맵 조회로 찾는 벤치마크다.

package bench

import "testing"

const N = 100000

var (
	slice []int
	m     map[int]struct{}
)

func init() {
	slice = make([]int, N)
	m = make(map[int]struct{}, N)
	for i := 0; i < N; i++ {
		slice[i] = i
		m[i] = struct{}{}
	}
}

func BenchmarkSliceLookup(b *testing.B) {
	target := N - 1  // 최악 케이스: 맨 끝
	for i := 0; i < b.N; i++ {
		for _, v := range slice {
			if v == target {
				break
			}
		}
	}
}

func BenchmarkMapLookup(b *testing.B) {
	target := N - 1
	for i := 0; i < b.N; i++ {
		_, _ = m[target]
	}
}

실행:

go test -bench=.

대략적인 결과는 다음과 같다 (장비마다 다름).

원소 수가 100배가 되어도 맵은 거의 같은 시간이 걸린다 — O(1) 의 위력이다. 슬라이스는 정직하게 100배 느려진다 — O(n).

그래도 슬라이스가 나은 경우

• 원소가 매우 적다 (대략 10개 이하)
  • 캐시에 통째로 올라와 선형 탐색이 더 빠를 때가 있다
• 검색은 거의 안 하고 순회만 한다
  • 슬라이스 순회가 보통 더 빠르다
• 입력 순서를 유지해야 한다

“맵 vs 슬라이스” 를 정할 때는 단순히 “맵이 빠르니까” 가 아니라 실제로 어떤 연산이 자주 일어나는지를 봐야 한다.

19.7 맵을 잘 쓰는 패턴

맵의 진짜 효용은 단순한 키-값 저장을 넘어선다. 실전에서 자주 쓰이는 패턴 몇 가지를 보자.

집합 (Set) 흉내 내기

Go 에는 별도의 Set 자료형이 없다. 대신 맵의 키만 쓰는 식으로 집합을 표현한다.

set := map[string]struct{}{}

set["apple"] = struct{}{}
set["banana"] = struct{}{}

if _, ok := set["apple"]; ok {
	fmt.Println("apple 있음")
}

delete(set, "apple")

값 자리에 왜 struct{}{} 인가? 빈 구조체는 메모리를 차지하지 않기 때문이다.

수백만 개의 집합을 만들 때 차이가 체감된다.

헬퍼로 깔끔하게

매번 struct{}{} 를 적기 번거롭다면 17장의 제네릭으로 작은 Set 타입을 만들 수 있다.

type Set[T comparable] map[T]struct{}

func (s Set[T]) Add(v T)         { s[v] = struct{}{} }
func (s Set[T]) Remove(v T)      { delete(s, v) }
func (s Set[T]) Has(v T) bool    { _, ok := s[v]; return ok }
func (s Set[T]) Len() int        { return len(s) }

func main() {
	s := Set[string]{}
	s.Add("a")
	s.Add("b")
	fmt.Println(s.Has("a"))  // true
	fmt.Println(s.Len())     // 2
}

카운터: 빈도 세기

map[K]int 는 카운터로 안성맞춤이다. 단어 빈도를 세는 예제를 보자.

package main

import (
	"fmt"
	"strings"
)

func main() {
	text := "the quick brown fox jumps over the lazy dog the fox"

	count := map[string]int{}
	for _, word := range strings.Fields(text) {
		count[word]++
	}

	for w, c := range count {
		fmt.Printf("%-6s %d\n", w, c)
	}
}

출력 (순서는 매번 다름):

the    3
fox    2
quick  1
brown  1
jumps  1
over   1
lazy   1
dog    1

핵심은 count[word]++ 한 줄이다. 처음 보는 키여도 count[word] 는 제로값 0 을 반환하므로 거기에 1 을 더해 다시 저장한다.

다른 언어처럼 “키가 있는지 먼저 확인” 할 필요가 없다.

그룹핑

비슷한 발상으로 데이터를 그룹별로 묶을 수 있다.

type Person struct {
	Name string
	City string
}

people := []Person{
	{"Alice", "Seoul"},
	{"Bob", "Busan"},
	{"Carol", "Seoul"},
	{"Dave", "Busan"},
}

byCity := map[string][]string{}
for _, p := range people {
	byCity[p.City] = append(byCity[p.City], p.Name)
}

for city, names := range byCity {
	fmt.Println(city, "→", names)
}

여기서도 append(byCity[p.City], p.Name) 한 줄이 “키가 없으면 nil 슬라이스에 추가” 라는 동작을 자연스럽게 처리한다. nil 슬라이스에 append 하면 새 슬라이스가 만들어지기 때문이다.

캐시 흉내

가장 단순한 형태의 캐시는 그냥 맵이다.

var cache = map[string]string{}

func get(key string) string {
	if v, ok := cache[key]; ok {
		return v
	}
	v := fetchFromDisk(key)  // 비싼 작업
	cache[key] = v
	return v
}

이 코드에는 두 가지 약점이 있다.

• 동시 접근 시 안전하지 않다 (앞에서 봤다)
• 무한히 자라서 메모리를 잡아먹는다

본격적인 캐시는 만료 정책, 크기 제한, 동시성 보호가 필요하다. 이런 주제들은 동시성 / 메모리 챕터에서 다시 만난다.

19.8 정리

이 장에서 본 내용:

• 맵은 해시 테이블이다 — 키를 해시로 바꿔 버킷 인덱스로 쓴다
• 충돌은 chaining 으로 해결 — 같은 버킷에 여러 키를 묶음
• 로드 팩터가 임계치를 넘으면 버킷이 2배로 확장된다
• Go 는 점진적 이주로 한 번에 멎는 일을 피한다
• 그래서 맵은 “평균 O(1)” 이지만 “항상 O(1)” 은 아니다
• 순회 순서는 의도적으로 무작위 — 코드의 견고함을 강제하기 위함
• 동시 접근은 안전하지 않다 — 락 또는 sync.Map 필요
• nil 맵은 읽기는 OK 지만 쓰기는 패닉 — make 로 초기화하자
• 큰 검색 데이터셋은 슬라이스 선형 탐색보다 맵이 압도적으로 빠르다
• 집합은 map[T]struct{}, 카운터는 map[K]int, 그룹핑은 map[K][]V

여기까지가 자료구조 깊이 보기의 마무리다. 다음 부에서는 코드를 잘 정리하고 안전하게 만드는 방법으로 넘어간다. 20장에서는 패키지와 모듈, 21장에서는 에러 처리를 다룬다.