map은 Go의 핵심적인 자료구조로, 그 내부 구현은 성능 향상을 위해 지속적으로 발전해왔다. 특히 Go 1.24 릴리스를 기점으로, map의 내부 아키텍처는 Go 1.24 전의 Hash Table (체이닝 방식)에서 Go 1.24 이후의 Swiss Table (오픈 어드레싱 방식)으로 변경되었다.
이 글에서는 이 두 방식을 비교하며, map의 동작 원리를 정리하고자 글을 작성한다.
핵심 구조: '체이닝' 방식과 '오픈 어드레싱' 방식
두 방식의 가장 근본적인 차이는 데이터를 저장하는 구조에 있다.
- Hash Table: 이 버전의 map은 bmap이라는 개별 버킷(bucket)들의 배열로 구성된다. 각 버킷은 최대 8개의 키-값 쌍을 저장할 수 있는 독립적인 공간이며, 해시 충돌이 발생하면 오버플로우 버킷이 '쇠사슬'처럼 포인터로 연결되는 구조다.
- Swiss Table: 이 버전은 오픈 어드레싱 방식을 사용한다. map의 가장 작은 단위인 '테이블(Table)'은 하나의 거대한 연속된 슬롯(Slot) 배열로 구성된다. '개별 버킷'이라는 개념 대신, 이 거대한 배열 안에서 빈자리를 찾아 나서는 방식이다. 이 구조는 CPU 캐시 효율을 극대화하기 위해 설계되었다.
충돌 처리: '오버플로우 체인'과 '2차 탐사'
해시 충돌을 해결하는 방식에서 두 버전의 철학적 차이가 드러난다.
- Hash Table: 한 버킷에 8개의 데이터가 모두 차면, 별도의 메모리 공간을 할당하여 오버플로우 버킷을 만들고 기존 버킷에 연결한다. 키를 찾으려면 이 연결 리스트를 따라 메모리 주소를 점프해야 하며, 이는 성능 저하의 주된 원인이 될 수 있다.
- Swiss Table: 특정 슬롯이 꽉 차 있으면, 오버플로우를 만드는 대신 '2차 탐사(Quadratic Probing)'를 사용해 다음 빈 슬롯을 찾아 나선다. 이는 하나의 거대한 배열 내에서 정해진 규칙에 따라 점프하며 빈 공간을 찾는 방식으로, 추가적인 메모리 할당이 없고 연속된 메모리에 접근하므로 훨씬 빠르다.
탐색 메커니즘: 순차 비교와 병렬 스캔
키를 찾는 과정은 두 버전의 성능 차이를 만드는 가장 극적인 부분이다.
- Hash Table: 키를 찾을 때, 해당하는 버킷을 찾아간 뒤 그 안의 tophash 배열(키 해시의 상위 비트들)을 하나씩 순차적으로 비교하여 후보를 찾는다. 최악의 경우 버킷 내 8개의 슬롯을 모두 확인해야 한다.
- Swiss Table: '제어 단어(Control Word)'라는 8바이트 메타데이터를 사용한다. 이 제어 단어는 8개 슬롯의 상태 정보와 해시 값 일부(H2)를 담고 있다. Go는 비트 연산을 통해 8개 슬롯의 상태를 한 번에(병렬로) 스캔할 수 있다. 이 방식은 8번의 탐색을 한 번의 작업으로 압축하여 조회 속도를 극적으로 향상시킨다.
동작 예시로 보는 두 방식의 차이
상황: map에 여러 키를 추가하는데, 운이 나쁘게도 a, b... i 까지 9개의 키가 모두 동일한 위치로 해시 충돌이 발생했다고 가정하자.
- Hash Table
- 입력: 처음 8개의 키(1~ 8)는 모두 같은 메인 버킷의 1번부터 8번 슬롯까지 차곡차곡 저장된다.
- 9번째 키 입력: 메인 버킷이 꽉 찼으므로, map은 새로운 메모리를 할당하여 '오버플로우 버킷'을 생성하고, 메인 버킷 끝에 이 새 버킷을 연결한다. 9번째 키는 이 오버플로우 버킷의 첫 번째 슬롯에 저장된다.
- i 조회:
- 해시 값으로 메인 버킷을 찾는다.
- 메인 버킷의 tophash 8개를 모두 확인하지만, i를 찾지 못한다.
- 버킷 끝의 오버플로우 포인터를 따라 메모리를 점프한다. (비싼 작업)
- 오버플로우 버킷의 첫 번째 슬롯에서 i를 찾는다.
- Swiss Table
- 입력: 처음 키 a은 해시된 시작 위치(예: 10번 슬롯)에 저장된다.
- 두 번째 키 b도 10번 슬롯으로 해시되었지만, 이미 차 있으므로 2차 탐사 규칙에 따라 근처의 다른 빈 슬롯(예: 11번)을 찾아 저장된다.
- 이 과정이 반복되어 8개의 키가 10번 슬롯 주변에 흩어져서 저장된다.
- 9번째 키 입력: 10번 슬롯 주변이 모두 꽉 찼더라도 새로운 메모리를 할당하지 않는다. 2차 탐사 규칙에 따라 계속해서 더 멀리 점프하며 거대한 단일 배열 내의 다른 빈 슬롯(예: 25번)을 찾아 i를 저장한다.
- i조회:
- 해시 값으로 탐색 시작 그룹(10번 슬롯이 포함된)을 찾는다.
- 제어 단어를 한 번에 스캔하여 후보가 없음을 확인한다.
- 2차 탐사 규칙에 따라 다음 탐색할 그룹으로 이동하여 다시 한 번에 스캔한다.
- 이 과정을 반복하다 25번 슬롯이 포함된 그룹을 스캔했을 때, 후보를 찾고 실제 키를 비교하여 i를 찾는다. 메모리 점프 없이 연속된 공간 내에서 탐색이 끝난다.
성장 방식: 점진적 이주와 확장 가능 해싱
map이 꽉 차서 확장해야 할 때도 두 버전은 다르게 동작한다.
- Hash Table: 로드 팩터(load factor)가 약 6.5 (13/2)를 초과하면, 2배 더 큰 새로운 버킷 배열을 할당한다. 그리고 기존의 모든 데이터를 새로운 배열로 점진적으로 이주(evacuate)시킨다.
- Swiss Table: map은 내부에 여러 개의 독립적인 테이블(Table)을 가질 수 있으며, 이 목록을 디렉토리(Directory)가 관리한다. 성장은 map 전체가 아닌 개별 테이블 단위로 일어난다. 특정 테이블이 꽉 차면, 그 테이블만 성장하거나 두 개로 분할(split)된다. 이 '확장 가능한 해싱(Extendible Hashing)' 구조 덕분에 재할당으로 인한 시스템 부하의 범위가 훨씬 작아져, map 크기와 상관없이 부드러운 성능을 유지할 수 있다.
결론
Go map의 진화는 하드웨어의 동작 방식을 더 깊이 이해하고, 그 이점을 최대한 활용하는 방향으로 이루어졌다. 전통적인 체이닝 방식에서 Swiss Table 기반의 오픈 어드레싱으로의 변화는, '메모리 점프'와 '새로운 할당'이라는 비싼 작업을 피하고 '연속된 메모리 접근'과 '병렬 처리'라는 CPU 친화적인 작업을 통해 성능을 극한까지 끌어올리려는 노력의 결과다. 블로그에 따르면, 이 변화로 마이크로벤치마크에서는 최대 60%, 실제 애플리케이션에서는 평균 1.5%의 CPU 시간 개선을 보였다.
출처
https://github.com/golang/go/blob/release-branch.go1.19/src/runtime/map.go
https://github.com/golang/go/blob/release-branch.go1.24/src/runtime/map_swiss.go
'Go' 카테고리의 다른 글
| Go의 Slice는 어떻게 동작하는가 (0) | 2025.06.14 |
|---|---|
| Go 프로젝트 라이브러리 받기 (0) | 2022.04.19 |
| 알고리즘 용 콘솔 입/출력 방법 (0) | 2022.04.15 |