맵

맵은 키를 대면 그 키에 묶어 둔 값을 찾아 줍니다. 회원 번호를 대고 그 회원의 정보를 꺼내는 일이 그런 예입니다. 한 키에는 값이 하나만 묶입니다. 목록의 원소마다 함수를 적용하는 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 을 가리킵니다. 어느 키에서도 화살표가 둘 나가지는 않습니다. 그래서 키를 대면 값이 하나로 정해집니다.

이 약속을 지키려면 맵이 두 키가 같은지를 가릴 수 있어야 합니다. 같은 키로 다시 넣었는지를 알아야 값을 바꿀 수 있기 때문입니다. 두 키가 같은지를 가리는 규칙을 동등성이라고 부릅니다.

맵이 제공하는 연산

맵이 제공하는 연산은 넷입니다. 넣기, 꺼내기, 들어 있나 묻기, 빼기입니다. 넷 다 키를 받습니다.

kim → 31, lee → 27 두 짝이 든 맵에 연산을 차례로 걸어 보면 아래와 같습니다.

2번에서 kim 의 값이 31 에서 32 로 바뀌었습니다. 짝은 둘로 늘지 않았습니다. 앞 소절의 첫째 약속이 이것입니다.

없는 키를 꺼내려 할 때 답하는 방식은 둘입니다. 하나는 미리 정해 둔 기본값을 돌려주는 방식입니다. 「값이 없다」를 뜻하는 빈 값이 그 기본값일 수 있습니다. 다른 하나는 실패로 알리는 방식입니다. 맵마다 한쪽을 고르거나 둘 다 줍니다.

없는 키가 흔한 일이면 기본값을 받는 쪽이 편합니다. 있어야 정상인 키라면 실패로 알리는 쪽이 실수를 일찍 드러냅니다.

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

목록 · 배열과의 차이

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

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

목록 · 배열 · 맵 셋을 나란히 놓으면 아래와 같습니다.

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

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

약속과 구현

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

그래서 맵을 만드는 방법은 여럿입니다. 흔한 것은 해시테이블과 균형 이진 탐색 트리 둘입니다.

해시테이블 안에는 버킷이라는 칸을 늘어놓은 배열이 하나 있습니다. 짝은 이 칸 가운데 하나에 들어갑니다. 어느 칸에 넣을지는 키가 정합니다.

키를 해시 함수에 넣으면 수 하나가 나옵니다. 이 수를 해시값이라고 부릅니다. 해시값으로 칸을 고릅니다.

flowchart TD
    K["찾는 키 kim"] --> H["해시 함수"]
    H -->|"해시값이 칸 2 를 고른다"| S2
    subgraph 칸배열["칸 배열"]
        S0["칸 0"]
        S1["칸 1"]
        S2["칸 2"]
        S3["칸 3"]
    end
    S1 --> P2["lee → 27"] --> P3["park → 27"]
    S2 --> P1["kim → 31"]

kim 을 찾을 때는 해시값이 고른 칸 2 하나만 열어 봅니다. 칸 0 과 칸 3 은 비어 있습니다. 칸 1 에는 lee 와 park 두 짝이 매달려 있습니다. 서로 다른 키가 한 칸으로 오는 이 일을 해시 충돌이라고 부릅니다. 충돌한 칸에서는 매달린 짝을 하나씩 비교합니다.

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

flowchart TD
    R["lee"] -->|"kim 은 lee 보다 작다 · 왼쪽"| A["jung"]
    R --> B["seo"]
    A --> C["choi"]
    A -->|"kim 은 jung 보다 크다 · 오른쪽"| D["kim"]
    B --> E["park"]
    B --> F["yoon"]

kim 을 찾을 때는 맨 위 lee 부터 비교합니다. 더 작으니 왼쪽 아래 jung 으로, 거기서 더 크니 오른쪽 아래로 내려가 찾습니다. 세 번 비교했습니다. seo 쪽 가지는 보지 않았습니다. 한 단계 내려갈 때마다 남은 후보가 절반쯤으로 줄어듭니다.

「균형」은 이 절반씩 줄어드는 이점을 지키려고 붙은 말입니다. 아래 그림은 같은 일곱 키를 작은 것부터 차례로 넣었을 때의 모양입니다.

flowchart TD
    C2["choi"] --> J2["jung"] --> K2["kim"] --> L2["lee"] --> P4["park"] --> S4["seo"] --> Y2["yoon"]

어느 키의 왼쪽 아래에도 키가 놓이지 않아 트리가 목록처럼 한 줄로 늘어섰습니다. yoon 을 찾으려면 일곱 번을 다 비교해야 합니다. 앞 그림의 균형 잡힌 트리에서는 세 번이면 닿습니다. 균형 트리는 짝을 넣고 뺄 때마다 모양을 고쳐 가지가 한쪽으로 쏠리지 않게 합니다.

두 방법은 짝을 늘어놓는 순서가 다릅니다. 해시테이블은 해시값으로 칸을 고르므로 넣은 순서도 키의 크기 순서도 남지 않습니다. 트리는 키 크기순으로 놓입니다. 걸리는 시간은 아래 「복잡도」가 다룹니다. 순서가 어떻게 갈리는지는 「갈래」가 다룹니다.

레코드와의 차이

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

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

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

맵이 맡는 일

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

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

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

이름이 같은 다른 「맵」

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

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

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

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

쓰이는 분야마다 「맵」이 가리키는 것은 아래와 같습니다.

복잡도

해시테이블로 만든 맵은 보통 짝이 아무리 늘어도 꺼내는 시간이 거의 늘지 않습니다. 다만 여러 키가 한 칸에 몰리면 짝 수만큼 걸립니다. 트리로 만든 맵은 짝이 두 배가 될 때마다 한 단계씩만 늡니다. 최악에도 그보다 더 걸리지 않습니다. 키 순서로 꺼내는 일은 트리만 합니다.

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

표기와 세는 것

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

O(1) 은 짝이 몇 개든 걸리는 시간이 늘지 않는다는 뜻입니다. O(log n) 은 짝이 두 배가 될 때 한 단계씩만 는다는 뜻입니다. O(n) 은 짝 수에 비례해 는다는 뜻입니다. 짝이 두 배면 시간도 두 배입니다. 이렇게 비례해 느는 것을 선형이라고도 부릅니다.

복잡도 앞에 붙는 말이 셋입니다. 「평균」은 키가 칸에 고루 흩어지는 보통의 경우입니다. 「최악」은 키가 가장 불리하게 놓인 경우입니다. 「상각」은 가끔 오는 비싼 한 번을 여러 번의 연산에 나눠 계산한 것입니다.

연산마다의 복잡도

두 방법의 연산별 복잡도를 나란히 놓으면 아래와 같습니다. 마지막 두 줄에 나오는 k 는 범위에 걸린 짝의 수입니다.

트리는 범위의 시작을 O(log n) 에 찾습니다. 거기서부터 걸린 짝 k 개를 크기순으로 따라가며 꺼냅니다.

해시테이블의 평균이 O(1) 인 이유는 둘입니다. 해시값이 칸 하나를 바로 고릅니다. 칸마다 매달린 짝도 몇 개 안 됩니다.

트리의 O(log n) 은 균형이 트리의 단계 수를 log n 쯤으로 묶어 두기 때문입니다. 맨 위부터 맨 아래까지의 단계 수를 트리의 높이라고 부릅니다. 짝이 백만 개여도 완전히 고르게 놓인 트리라면 스무 단계쯤 내려가면 닿습니다.

최악이 오는 조건

해시테이블의 최악은 여러 키가 한 칸에 몰렸을 때 옵니다. 해시 함수가 키를 칸에 고루 흩지 못하는 경우입니다. 그 칸에 매달린 짝을 하나씩 비교해야 하므로 짝이 전부 한 칸에 몰리면 O(n) 이 됩니다.

넣기의 「상각」은 칸 배열을 늘리는 일에서 나옵니다. 칸이 어느 정도 차면 해시테이블은 더 큰 칸 배열을 새로 잡고 모든 짝을 다시 넣습니다. 이 일을 재해시라고 부릅니다. 재해시 한 번은 O(n) 이 걸립니다. 칸을 두 배씩 늘리면 재해시가 드물게 옵니다. 그래서 넣기 한 번에 나눠 계산하면 O(1) 이 됩니다.

트리는 최악도 O(log n) 입니다. 짝을 넣고 뺄 때 모양을 고치는 일이 높이를 묶어 두기 때문입니다. 이 균형이 없으면 키를 크기순으로 넣는 것만으로 트리가 한 줄로 늘어서 O(n) 이 됩니다. 앞 「약속과 구현」의 한 줄로 늘어선 트리가 그 모양입니다.

키 하나를 다루는 비용

위 복잡도는 키 하나를 비교하거나 해시값을 내는 일을 한 번의 일로 셉니다. 키가 정수면 그래도 됩니다. 키가 긴 문자열이면 해시값을 낼 때 글자를 전부 읽습니다. 비교도 다른 글자가 나올 때까지 읽습니다.

그래서 긴 문자열 키에서는 O(1) 안에 키 길이만큼의 일이 들어 있습니다. 트리는 이 비교를 log n 번 합니다.

공간

두 방법 다 공간은 짝 수에 비례합니다. 더 드는 것이 다릅니다.

해시테이블은 칸이 다 차기 전에 칸 배열을 늘리므로 늘 빈칸을 남겨 둡니다. 칸 가운데 짝이 든 비율을 적재율이라고 부릅니다. 앞 소절의 재해시는 이 적재율이 정해 둔 선을 넘을 때 옵니다.

트리는 짝마다 왼쪽·오른쪽 아래를 가리키는 포인터 둘을 더 둡니다. 균형을 지키는 데 쓰는 정보도 짝마다 조금 붙습니다.

예시

이 절은 언어와 런타임 안에 박힌 맵 넷을 봅니다. 인터프리터가 스스로 맵을 쓰는 경우, 없는 키에 답하는 두 방식, 구현을 비워 둔 맵, 트리로 만든 맵입니다.

파이썬 인터프리터의 이름 공간

파이썬에서 맵 노릇을 하는 표준 타입은 딕셔너리 하나입니다. 코드에서 쓰는 이름은 dict 입니다.

이름 공간은 이름에서 객체로 가는 대응입니다. 이름을 키로, 객체를 값으로 보면 맵입니다. 대부분의 이름 공간은 현재 파이썬 딕셔너리로 구현돼 있습니다. 성능 말고는 대개 이 사실이 드러나지 않습니다. 앞으로 바뀔 수도 있습니다.

이름 공간의 예는 셋입니다. abs() 같은 내장 함수와 내장 예외 이름의 모음, 모듈 하나의 전역 이름, 함수를 한 번 부를 때의 지역 이름입니다.

파이썬 dict 와 Go map

없는 키를 물었을 때 답하는 두 방식이 두 언어에 다 있습니다. 파이썬의 dict 는 실패로 알리는 쪽과 기본값을 돌려주는 쪽을 둘 다 줍니다.

ages = {"kim": 31, "lee": 27}
ages.get("park")     # None
ages["park"]         # KeyError

get 은 키가 없으면 기본값을 돌려줍니다. 기본값을 안 주면 None 을 돌려줍니다. 그래서 get 은 KeyError 를 던지지 않습니다. 대괄호로 물으면 없는 키에 KeyError 를 던집니다.

Go 의 map 은 기본값을 돌려주는 쪽입니다. 맵 a 에 키 x 가 있으면 a[x] 는 그 키의 값입니다. 맵이 nil 이거나 그 키가 없으면 a[x] 는 값 타입의 영값(zero value)입니다. 영값은 Go 가 타입마다 정해 둔 기본값입니다. 초기화하지 않은 맵은 그 자체가 nil 입니다.

ECMAScript 의 Map

ECMAScript 는 자바스크립트 언어의 표준 이름입니다. 여기의 Map 은 키와 값이 둘 다 아무 언어 값이나 될 수 있는 짝의 모음입니다. 한 키는 짝 하나에만 나옵니다. 두 키가 같은지는 SameValueZero 라는 같음 판정 규칙으로 가립니다.

Map 은 해시테이블로 만들어도 되고 다른 방법으로 만들어도 됩니다. 다만 평균 접근 시간이 짝 수에 대해 선형보다 낮아야 합니다. 앞 「복잡도」의 O(n) 보다 낮아야 한다는 뜻입니다. 어떤 방법을 쓸지는 정해 두지 않습니다. 표준 문서 안에 적힌 자료구조는 겉으로 보이는 동작을 설명하려는 것이지 그대로 구현하라는 모델이 아닙니다. 연산만 정하고 담는 법은 비워 둔 추상 자료형이 언어에 박힌 모습입니다.

자바의 TreeMap

TreeMap 은 레드-블랙 트리로 만든 맵입니다. 레드-블랙 트리는 균형 이진 탐색 트리의 한 종류입니다. 「자연 순서」는 그 키 타입에 미리 정해 둔 크기 순서입니다. 수라면 작은 수부터 큰 수 쪽입니다. TreeMap 의 키는 이 자연 순서로 정렬됩니다. 맵을 만들 때 Comparator 를 넘기면 그 순서로 정렬됩니다.

containsKey · get · put · remove 네 연산은 log(n) 시간이 보장됩니다. 앞 「복잡도」 표의 트리 쪽 복잡도가 이 네 연산에 걸린 것입니다.

갈래

맵의 갈래를 가르는 축은 하나입니다. 짝을 어떤 순서로 내주나입니다. 맵에 든 짝을 하나씩 모두 꺼내 보는 일을 순회라고 부릅니다. 갈래마다 순회 순서가 다릅니다. 키에 요구하는 것도 다릅니다.

언어 표준이 못박는 것은 대개 순회 순서까지입니다. 안에서 짝을 어떻게 늘어놓는지는 정하지 않는 쪽이 많습니다. 그래서 아래 소절은 순회 순서로 가릅니다. 담는 방법은 그것까지 밝힌 맵에만 적습니다.

순회 순서를 정하지 않는 맵

어느 짝이 먼저 나올지 약속하지 않습니다. 키에는 두 키가 같은지 가리는 판정을 요구합니다. 해시로 담는 맵이면 해시값도 요구합니다.

자바의 HashMap 은 해시테이블로 만든 맵입니다. 순서를 보장하지 않습니다. 그 순서가 시간이 지나도 같다는 것도 보장하지 않습니다. C++ 의 unordered_map 은 해시 함수를 받는 「순서 없는」 맵입니다. Go 의 map 도 순회 순서를 정하지 않습니다. 한 번 순회할 때와 다음 순회할 때 순서가 같다는 보장도 없습니다.

키 크기순으로 내주는 맵

순회하면 작은 키부터 나옵니다. 범위 찾기도 됩니다. 키에는 크기 비교를 요구합니다.

자바의 TreeMap 은 레드-블랙 트리로 만든 맵입니다. 키의 자연 순서나 넘긴 Comparator 로 정렬합니다. C++ 의 map 은 키 크기를 비교하는 규칙을 받습니다. 기본값은 「작다」 비교입니다. 순회하면 그 비교로 따져 작은 키부터 나옵니다. 담는 방법은 정해져 있지 않습니다.

넣은 순서로 내주는 맵

순회하면 짝을 넣은 순서로 나옵니다. 해시로 담은 맵에는 넣은 순서가 남지 않습니다. 순서를 따로 기억하는 사슬을 덧대는 것이 한 방법입니다.

자바의 LinkedHashMap 이 그 꼴입니다. 해시테이블에 연결 리스트를 더해 만듭니다. 모든 짝을 앞뒤 양쪽으로 잇는 연결 리스트를 둡니다. 이 리스트가 순회 순서를 정합니다. 그 순서는 대개 키를 넣은 순서입니다. 이미 있는 키를 put 으로 다시 넣어도 순서는 바뀌지 않습니다.

flowchart TD
    subgraph 칸배열["칸 배열"]
        S1["칸 1"]
        S2["칸 2"]
    end
    S1 --> P3["park → 27"]
    S1 --> P2["lee → 27"]
    S2 --> P1["kim → 31"]
    P3 -. "다음에 넣은 짝" .-> P1
    P1 -. "다음에 넣은 짝" .-> P2

park, kim, lee 순서로 넣었습니다. 알파벳 순서와는 다릅니다. 실선 화살표는 짝이 매달린 칸입니다. 칸은 해시값이 정합니다. 점선은 넣은 순서를 잇는 사슬입니다. 순회는 이 사슬을 따라가므로 park 부터 나옵니다. 키 크기순이라면 kim 부터 나왔을 것입니다.

파이썬의 dict 도 넣은 순서를 지킵니다. 3.7 판부터 보장으로 못박았습니다. 키의 값을 바꿔도 순서는 안 바뀝니다. 뺐다가 다시 넣은 키는 맨 뒤로 갑니다. ECMAScript 의 Map 도 짝마다 함수를 부르는 forEach 가 키를 넣은 순서로 돕니다. 이 둘은 순회 순서만 약속합니다. 담는 방법은 LinkedHashMap 과 달리 정해 두지 않습니다.

언어마다 부르는 이름

같은 맵을 언어마다 다른 이름으로 부릅니다. 연관 배열이라는 이름도 씁니다. 이 절의 셋으로 가르면 아래와 같습니다.

같은 map 이라는 이름이 C++ 에서는 키 크기순입니다. Go 에서는 순서를 정하지 않는 쪽입니다. C++ 에서는 순서를 정하지 않는 쪽에 「순서 없는」이라는 뜻의 unordered 가 붙습니다. 이름만 보고 갈래를 짐작하면 순회 순서와 걸리는 시간을 잘못 예상합니다.

보장과 가정

맵이 하는 약속은 「상세」에서 본 둘입니다. 한 키에는 값이 하나만 묶입니다. 넣어 둔 짝은 같은 키를 대면 다시 찾힙니다. 이 둘은 키가 몇 가지 가정을 지킬 때만 섭니다.

키가 지켜야 할 가정

가정은 넷입니다. 아래 표 셋째 줄의 「모순 없는 순서」란 a 가 b 보다 작고 b 가 c 보다 작으면 a 도 c 보다 작다는 식으로 비교끼리 어긋나지 않는 것입니다.

맨 아래 가정은 맵이 짝을 둘 곳을 고르는 방식에서 나옵니다. 맵은 넣을 때의 키를 기준으로 짝을 둘 칸이나 가지를 골랐습니다. 키가 바뀌면 그 기준이 어긋나 짝을 다시 못 찾습니다. 그래서 내용이 바뀌는 값을 키로 쓸 때는 크게 조심해야 합니다. 키로는 문자열이나 정수처럼 한번 만들면 안 바뀌는 값을 씁니다. 이렇게 만든 뒤에 내용이 안 바뀌는 값을 불변 객체라고 부릅니다.

자바의 equals 와 hashCode

자바는 두 객체가 같은지를 equals 메서드로 묻습니다. 해시값은 hashCode 메서드로 묻습니다. equals 로 같은 두 객체는 hashCode 도 같은 정수를 내야 합니다. equals 에 쓰는 정보가 안 바뀌었다면, 같은 객체에 hashCode 를 여러 번 불러도 같은 정수를 내야 합니다. 이 약속은 한 실행 안에서만 걸립니다.

그래서 hashCode 를 그대로 두고 equals 만 재정의한 클래스를 키로 쓰면 둘째 가정이 깨질 수 있습니다. hashCode 도 함께 재정의하는 쪽이 안전합니다.

가변 객체를 키로 쓸 때는 크게 조심해야 합니다. 키가 맵에 든 동안 equals 비교에 영향을 주게 바뀌면 맵의 동작은 정해지지 않습니다. 맵도 짝을 넣고 빼면 내용이 바뀝니다. 그래서 맵이 자기 자신을 키로 담는 것은 이 금지의 특별한 경우로 허용되지 않습니다.

키 크기순으로 정렬하는 맵은 같음 판정을 따로 쓰지 않습니다. 모든 키 비교를 크기 비교 메서드로 합니다. 그래서 크기 비교가 「같다」고 답한 두 키는 그 맵에서 한 키입니다. equals 로는 다른 두 키가 한 짝으로 합쳐집니다. 먼저 넣은 짝은 그 키로 다시 못 찾습니다. 위 약속 둘 가운데 둘째가 깨지는 것입니다. TreeMap 처럼 정렬하는 맵에서 이런 일이 나도 그 맵의 동작 자체는 잘 정해져 있습니다. 다만 그 맵은 맵이 하는 약속을 따르지 않습니다.

파이썬의 해시 가능

파이썬에서 키가 되려면 해시 가능해야 합니다. 해시 가능한 객체는 수명 동안 해시값이 안 바뀝니다. 다른 객체와 같은지 비교할 수도 있습니다. 같다고 비교되는 해시 가능한 객체들은 해시값이 같아야 합니다.

리스트와 딕셔너리처럼 내용이 바뀌는 컨테이너는 해시 가능하지 않아서 키로 못 씁니다. 튜플은 원소가 전부 해시 가능할 때만 해시 가능합니다. 같다고 비교되는 1, 1.0, True 는 같은 항목을 가리키는 키로 서로 바꿔 쓸 수 있습니다.

C++ 와 Go 의 키 조건

C++ 의 unordered_map 에서 같다고 판정된 두 키는 해시 함수가 같은 해시값을 내야 합니다. 같은 두 키에 대한 같음 판정과, 한 키에 대한 해시값은 언제 불러도 같은 결과여야 합니다. C++ 의 map 은 키 비교 규칙이 엄격한 약순서(strict weak ordering)를 이뤄야 합니다. 엄격한 약순서는 위 「모순 없는 순서」를 수학으로 적은 조건입니다.

Go 는 키 타입에 == 와 != 가 빠짐없이 정의돼 있어야 합니다. 그래서 함수·맵·슬라이스는 키 타입이 될 수 없습니다. 키 타입이 인터페이스면 실제로 들어온 키마다 비교가 정의돼 있어야 합니다. 정의돼 있지 않으면 실행 중에 패닉이 납니다.

관련 항목

맵이 속하는 상위 분류

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

맵을 가리키는 다른 이름

딕셔너리 · 연관 배열

맵을 담아내는 구현

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

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

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

맵을 만드는 데 쓰는 부품

키-값 쌍 · 해시 함수 · 해시 충돌 · 버킷 · 재해시 · 적재율 · 동등성 · 불변 객체 · 해시 가능

맵을 표준 라이브러리에 둔 언어

Java · Python · C++ · Go · JavaScript

맵을 바탕으로 만드는 기법

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

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

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

맵을 설명할 때 쓰는 개념

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

이름이 겹치는 다른 맵

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