맵

맵은 키를 대면 그 키에 묶어 둔 값을 찾아 줍니다. 회원 번호를 대고 그 회원의 정보를 꺼내는 일이 그런 예입니다. 한 키에는 값이 하나만 묶입니다. 목록의 원소마다 함수를 적용하는 map 함수와는 이름만 같은 다른 것입니다.

상세

이 절은 맵이 지키는 약속에서 시작합니다. 이어서 맵을 만드는 두 방법을 비교합니다. 끝에서는 백엔드 코드에서 맵이 맡는 일과 이름이 같은 다른 「맵」을 봅니다.

키와 값

맵이 담는 것은 키와 값의 짝입니다. 키는 찾을 때 대는 이름입니다. 값은 그 이름에 묶어 둔 데이터입니다. 아이디 "kim" 에 나이 31 을 묶어 두는 식입니다.

맵이 지키는 약속은 하나입니다. 한 키에는 값이 하나만 묶입니다. 같은 키로 다시 넣으면 값이 바뀝니다. 짝이 둘로 늘지 않습니다. 서로 다른 키가 같은 값을 가리키는 것은 괜찮습니다.

아래 그림은 세 키가 두 값을 가리키는 맵입니다.

flowchart TD
    subgraph 키
        K1["kim"]
        K2["lee"]
        K3["park"]
    end
    subgraph 값
        V1["31"]
        V2["27"]
    end
    K1 --> V1
    K2 --> V2
    K3 --> V2

lee 와 park 는 같은 값 27 을 가리킵니다. 어느 키에서도 화살표가 둘 나가지는 않습니다. 그래서 키를 대면 값이 하나로 정해집니다.

맵이 제공하는 연산

맵이 제공하는 연산은 넷입니다. 넣기, 꺼내기, 들어 있나 묻기, 빼기입니다. 파이썬은 맵을 딕셔너리라고 부르고 중괄호로 적습니다.

ages = {"kim": 31, "lee": 27}
ages["kim"]          # 31
ages["kim"] = 32
ages["kim"]          # 32
"park" in ages       # False
del ages["lee"]
len(ages)            # 1

ages["kim"] = 32 줄에서 kim 의 값이 31 에서 32 로 바뀌었습니다. 짝이 둘로 늘지 않았다는 것이 앞 소절의 약속입니다. 마지막 줄의 1 은 lee 를 빼고 남은 짝의 수입니다.

없는 키를 물을 때 어떻게 답할지는 맵마다 다릅니다. 파이썬은 두 가지 길을 줍니다.

ages.get("park")     # None
ages["park"]         # KeyError

get 은 값이 없다는 뜻으로 None 을 돌려줍니다. 대괄호로 물으면 예외를 던집니다. 없는 키가 흔한 일이면 앞쪽을 씁니다. 있어야 정상이면 뒤쪽을 씁니다.

값으로 키를 찾는 연산은 없습니다. 맵은 키에서 값으로 가는 길만 만들어 둡니다. 나이가 32 인 사람을 찾으려면 모든 짝을 하나씩 봐야 합니다.

목록 · 배열과의 차이

키와 값의 짝을 목록에 늘어놓아도 같은 정보는 담깁니다. 문제는 찾을 때입니다. 목록에서 kim 을 찾으려면 첫 짝부터 차례로 비교해야 합니다. 짝이 백만 개면 없는 키를 찾을 때 백만 번을 전부 비교합니다.

배열은 번호로 값을 곧바로 꺼냅니다. 하지만 배열의 번호는 0부터 이어지는 정수뿐입니다. 회원 번호 1 번과 1000000 번 둘만 담으려 해도 배열은 칸을 백만 개 잡아야 합니다. 맵은 짝 두 개만 담습니다.

아래 표는 셋을 나란히 놓은 것입니다.

맵은 목록처럼 아무 값이나 키로 받습니다. 그러면서도 찾을 때 모든 짝을 보지는 않습니다. 어떻게 그럴 수 있는지는 다음 소절의 두 방법이 답합니다.

짝이 몇 개 안 되거나 넣은 순서가 뜻을 가지는 일에는 목록이 더 단순합니다. 맵은 키로 찾는 일이 잦을 때 유리합니다.

약속과 구현

맵은 무엇을 해 주는지만 정한 이름입니다. 안에서 짝을 어떻게 늘어놓는지는 정하지 않습니다. 이렇게 연산만 정하고 만드는 법은 비워 둔 자료형을 추상 자료형이라고 부릅니다.

그래서 맵을 만드는 방법은 여럿입니다. 흔한 것은 둘입니다.

첫째는 해시테이블입니다. 해시테이블 안에는 칸을 늘어놓은 배열이 하나 있습니다. 짝은 이 칸 가운데 하나에 들어갑니다.

어느 칸에 넣을지는 키가 정합니다. 키를 해시 함수에 넣으면 수 하나가 나옵니다. 이 수를 해시값이라고 부릅니다. 해시값으로 칸을 정하므로, 찾을 때 그 칸 하나만 열어 보면 됩니다.

칸을 정하는 것이 해시값이라서 해시테이블에는 넣은 순서도 키의 크기 순서도 남지 않습니다. 짝을 꺼내 훑으면 뒤섞인 순서로 나옵니다.

둘째는 균형 이진 탐색 트리입니다. 키를 크기순으로 가지 모양에 담습니다. 어떤 키의 왼쪽 아래에는 더 작은 키가 놓입니다. 오른쪽 아래에는 더 큰 키가 놓입니다.

찾을 때는 맨 위 키부터 비교합니다. 찾는 키가 더 작으면 왼쪽 아래로, 더 크면 오른쪽 아래로 내려갑니다. 한 단계 내려갈 때마다 남은 후보가 절반쯤으로 줄어듭니다.

「균형」은 이 절반씩 줄어드는 이점을 지키려고 붙은 말입니다. 가지가 한쪽으로만 길어지면 트리가 목록처럼 한 줄로 늘어섭니다. 그러면 짝 수만큼 내려가야 합니다. 균형 트리는 짝을 넣고 뺄 때마다 모양을 고쳐 가지가 한쪽으로 쏠리지 않게 합니다.

두 방법이 걸리는 시간은 빅오 표기법으로 적습니다. 빅오 표기법은 짝이 늘 때 걸리는 시간이 얼마나 빨리 느는지를 적는 방법입니다. 식 안의 n 은 담긴 짝의 수입니다.

O(1) 은 짝이 몇 개든 걸리는 시간이 늘지 않는다는 뜻입니다. O(log n) 은 짝이 두 배가 될 때 한 단계씩만 는다는 뜻입니다. O(n) 은 짝 수에 비례해 는다는 뜻입니다. 짝이 두 배면 시간도 두 배입니다.

해시테이블로 만든 맵에는 「평균」과 「최악」을 따로 적습니다. 평균은 키가 칸에 고루 흩어지는 보통의 경우입니다. 최악은 여러 키가 한 칸에 몰린 경우입니다. 아래 표는 두 방법을 나란히 놓은 것입니다.

해시테이블의 최악이 O(n) 인 것은 한 칸에 몰린 짝을 하나씩 비교해야 하기 때문입니다. 서로 다른 키가 한 칸으로 오는 일을 해시 충돌이라고 부릅니다.

고르는 기준은 대개 하나입니다. 키 순서나 범위로 찾을 일이 있으면 트리로 만든 맵을 씁니다. 키 하나로 꺼내기만 하면 해시테이블로 만든 맵을 씁니다.

키가 지켜야 할 조건

맵은 두 키가 같은지를 판정할 수 있어야 동작합니다. 같은 키로 다시 넣었을 때 값을 바꾸려면 두 키가 같다는 것을 알아야 하기 때문입니다. 두 값이 같은지를 가리는 이 규칙을 동등성이라고 부릅니다.

해시테이블로 만든 맵에는 조건이 하나 더 붙습니다. 같은 키라면 해시값도 같아야 합니다. 두 키를 같다고 판정해 놓고 해시값을 다르게 내면 둘이 다른 칸으로 갑니다. 그러면 넣은 키를 다시 대도 못 찾습니다.

자바는 두 객체가 같은지를 equals 메서드로 묻습니다. 해시값은 hashCode 메서드로 묻습니다. equals 만 재정의한 클래스를 키로 쓰면 위의 일이 납니다. hashCode 도 함께 재정의해야 두 규칙이 맞습니다.

키를 넣은 뒤에 키의 내용을 바꾸는 것도 같은 문제를 냅니다. 맵은 넣을 때의 키를 기준으로 짝을 둘 칸이나 가지를 골랐습니다. 키가 바뀌면 그 기준이 어긋나 짝을 다시 못 찾습니다. 그래서 키로는 문자열이나 정수처럼 한번 만들면 안 바뀌는 값을 씁니다.

이렇게 만든 뒤에 내용이 안 바뀌는 값을 불변 객체라고 부릅니다. 불변 객체를 키로 쓰면 넣은 뒤에 기준이 어긋날 일이 없습니다.

레코드와의 차이

레코드는 이름이 정해진 필드 몇 개를 묶은 데이터입니다. 클래스 하나가 가진 필드 묶음을 떠올리면 됩니다. 레코드도 필드 이름으로 값을 꺼냅니다. 회원 레코드에서 name 을 꺼내는 식입니다.

겉보기는 맵과 닮았습니다. 갈리는 것은 이름을 언제 정하느냐입니다. 레코드의 필드 이름은 코드를 짤 때 정해져 있습니다. 맵의 키는 프로그램이 도는 동안 들어오고 나갑니다. 오늘 들어온 주문 번호를 이름으로 쓰는 일은 레코드로는 못 합니다.

JSON(JavaScript Object Notation, 자바스크립트 객체 표기) 객체는 둘 중 어느 쪽으로도 읽힙니다. 필드가 정해진 응답이면 클래스로 받아 레코드처럼 씁니다. 키가 그때그때 달라지는 응답이면 맵으로 받습니다.

맵이 맡는 일

백엔드 코드에서 맵은 대개 아래 넷 중 하나를 맡습니다. 넷 다 「무엇으로 찾나」가 키가 되고 「무엇을 얻나」가 값이 됩니다.

첫 줄처럼 한 번 계산한 결과를 담아 두고 다시 꺼내 쓰는 것이 캐시의 기본 모양입니다. 함수의 결과를 인자별로 담아 두는 기법은 메모이제이션이라고 부릅니다.

마지막 줄은 컴파일러가 이름마다 정보를 달아 두는 심볼 테이블입니다. 코드에 나온 변수 이름을 키로 대고 그 변수가 무엇인지를 꺼냅니다.

언어마다 부르는 이름

같은 맵을 언어마다 다른 이름으로 부릅니다. 연관 배열이라고도 부릅니다. 이름이 달라도 키로 값을 찾는 그릇이라는 점은 같습니다.

C++ 에서는 그냥 map 이라고 부르는 쪽이 트리입니다. 해시테이블로 만든 쪽에 「순서 없는」이라는 뜻의 unordered 가 붙습니다. 이름만 보고 해시테이블로 여기면 걸리는 시간을 잘못 어림합니다.

이름이 같은 다른 「맵」

「맵」이라는 말은 자료구조 밖에서도 흔히 씁니다. 문장에 따라 전혀 다른 것을 가리키므로 갈라 읽어야 합니다.

가장 자주 부딪히는 것은 map 함수입니다. 목록의 원소 하나하나에 함수를 적용해 새 목록을 만듭니다.

list(map(abs, [-1, 2]))  # [1, 2]

-1 과 2 가 저마다 abs 를 거쳐 [1, 2] 가 되었습니다. 키도 값도 없습니다. 함수를 인자로 받는 함수라서 고차 함수라고 부릅니다.

아래 표는 「맵」이 쓰는 곳마다 무엇을 가리키는지 모은 것입니다.

관련 항목

맵이 속하는 상위 분류

자료구조 · 추상 자료형 · 컬렉션 · 컨테이너 (자료구조)

맵을 가리키는 다른 이름

딕셔너리 · 연관 배열 · 해시맵 · 트리맵 · 키-값 쌍

맵을 실제로 담아내는 구현

해시테이블 · 이진 탐색 트리 · 균형 이진 탐색 트리 · 레드-블랙 트리 · AVL 트리 · B-tree · 트라이 · 스킵 리스트

맵과 비교해 고르는 다른 자료구조

배열 · 리스트 · 집합 · 레코드 · 튜플 · 멀티맵

맵을 만드는 데 쓰는 부품

해시 함수 · 해시 충돌 · 버킷 · 동등성 · 불변 객체 · 적재율

맵을 바탕으로 만드는 기법

캐싱 · 메모이제이션 · 심볼 테이블 · 인덱스 · 해시 인덱스

맵의 모양을 빌린 저장 시스템

키-값 저장소 · Redis · 문서 데이터베이스 · JSON

맵을 설명할 때 쓰는 개념

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 상각 분석

이름이 겹치는 다른 맵

map 함수 · 고차 함수 · 함수형 프로그래밍 · 맵리듀스