딕셔너리

딕셔너리는 키를 대면 그 키에 묶어 둔 값을 꺼내 줍니다. 사용자 아이디로 그 사용자의 정보를 꺼내는 일이 그런 예입니다. 맵이라고 부르는 것과 같은 물건입니다. 검색 엔진이나 압축에서는 같은 이름이 다른 것을 가리킵니다.

상세

이 절은 딕셔너리라는 이름이 가리키는 것부터 보고, 백엔드 개발자가 가장 자주 만나는 파이썬 딕셔너리로 넘어갑니다.

이름이 가리키는 것

딕셔너리는 키와 값의 쌍을 담는 자료형입니다. 키는 찾을 때 대는 이름입니다. 값은 그 이름에 묶어 둔 데이터입니다. 한 키에는 값이 하나만 묶입니다.

이름은 종이 사전에서 왔습니다. 사전에서 낱말을 찾으면 그 뜻이 나옵니다. 딕셔너리에서 키를 찾으면 값이 나옵니다.

딕셔너리가 받는 연산은 셋입니다. 넣기, 찾기, 빼기입니다. 이 셋을 딕셔너리 연산이라고 부릅니다. 딕셔너리가 약속하는 것은 이 셋뿐입니다. 안에서 쌍을 어떻게 늘어놓는지는 정하지 않습니다.

이렇게 연산만 정하고 만드는 법은 비워 둔 자료형을 추상 자료형이라고 합니다. 만드는 법을 비워 두면 쓰는 쪽 코드를 안 고치고 속을 바꿀 수 있습니다.

같은 추상 자료형을 맵이나 연관 배열이라고도 부릅니다. 하는 일은 같습니다. 언어마다 고른 이름만 다릅니다. 아래 표는 흔한 언어 다섯이 이 자료형을 부르는 이름입니다.

위의 셋은 딕셔너리라는 이름을 씁니다. 아래의 둘은 맵이라는 이름을 씁니다. 이름이 달라도 키로 값을 찾는 자료형이라는 점은 같습니다.

파이썬 딕셔너리

파이썬은 딕셔너리를 중괄호로 적습니다. 키와 값은 콜론으로 잇습니다. 쌍끼리는 쉼표로 가릅니다.

아래 코드는 쌍 하나를 넣고 꺼냅니다. 그다음 같은 키로 다시 넣습니다.

ages = {"kim": 31}
ages["kim"]         # 31
ages["kim"] = 32
ages["kim"]         # 32
len(ages)           # 1

같은 키로 다시 넣자 값이 32 로 바뀌었습니다. 쌍의 수는 여전히 1 입니다. 한 키에 값이 하나만 묶인다는 규칙이 이렇게 드러납니다.

두 키가 같은 키인지는 값이 같은지로 가립니다. 겉으로 적은 모양은 따지지 않습니다. 파이썬에서 1 과 1.0 과 True 는 서로 같다고 판정되므로 셋은 한 키로 취급됩니다.

d = {1: "a"}
d[1.0]              # 'a'
d[True] = "b"
d                   # {1: 'b'}

1.0 으로 물어도 1 에 넣은 값이 나왔습니다. True 로 넣은 값은 새 쌍이 되지 않았습니다. 1 의 값을 바꿨습니다. 키는 처음 넣은 1 이 남았습니다.

키가 될 수 있는 값

파이썬 딕셔너리의 키는 아무 값이나 될 수 없습니다. 까닭은 딕셔너리를 만드는 방식에 있습니다. 이 소절은 그 방식을 먼저 보고 키의 조건으로 넘어갑니다.

파이썬 딕셔너리는 해시테이블로 만듭니다. 해시테이블은 칸을 늘어놓은 배열을 하나 품고 있습니다. 쌍은 이 칸 가운데 하나에 들어갑니다.

어느 칸에 넣을지는 키가 정합니다. 키를 해시 함수에 넣으면 수 하나가 나옵니다. 이 수를 해시값이라고 합니다.

해시값에서 칸 번호를 계산해 그 칸에 쌍을 넣습니다. 찾을 때도 같은 계산을 하므로 그 칸 하나만 열면 됩니다. 아래 그림은 키 kim 이 칸에 이르는 길입니다.

flowchart TD
    K["키 · kim"] --> H["해시 함수"]
    H --> V["해시값"]
    V --> N["칸 번호 · 2"]
    subgraph 칸배열["칸 배열"]
        C0["칸 0 · 비어 있음"]
        C1["칸 1 · 비어 있음"]
        C2["칸 2 · kim · 31"]
        C3["칸 3 · 비어 있음"]
    end
    N --> C2

키 kim 은 해시값을 거쳐 칸 2 로 갑니다. 나머지 칸은 비어 있습니다. kim 을 찾을 때도 같은 길을 거쳐 칸 2 하나만 엽니다.

그래서 키는 해시값을 낼 수 있어야 합니다. 이런 값을 해시 가능하다고 합니다. 문자열, 정수, 튜플처럼 만든 뒤에 내용이 안 바뀌는 값이 여기에 듭니다.

리스트나 딕셔너리처럼 내용이 바뀌는 값은 키로 못 씁니다. 키의 내용이 바뀌면 해시값도 바뀝니다. 그러면 넣을 때 고른 칸과 찾을 때 여는 칸이 달라져 쌍을 다시 못 찾습니다.

아래 코드는 내용이 같은 튜플과 리스트를 키로 넣어 봅니다.

d = {}
d[(1, 2)] = "ok"
d[[1, 2]] = "no"    # TypeError

튜플 (1, 2) 는 키가 되었습니다. 리스트 [1, 2] 는 예외를 냈습니다. 둘의 차이는 만든 뒤에 내용을 바꿀 수 있느냐 하나입니다.

이 조건은 딕셔너리를 안에 품은 기능에도 옮겨 갑니다. 함수 결과를 인자별로 담아 두는 메모이제이션 캐시가 그런 예입니다. 인자를 키로 삼으므로 리스트를 인자로 넘기면 결과를 담아 둘 수 없습니다.

넣은 순서

보통의 해시테이블은 넣은 순서를 남기지 않습니다. 칸을 해시값이 정하기 때문입니다. 쌍을 꺼내 훑으면 뒤섞인 순서로 나옵니다.

파이썬 딕셔너리는 다릅니다. 쌍을 훑으면 넣은 순서대로 나옵니다. 칸 배열과 따로 넣은 순서를 적어 두기 때문입니다. 훑을 때는 칸이 아니라 이 순서를 따라갑니다.

이 순서는 파이썬 3.7부터 언어가 약속합니다. 파이썬 공식 배포판에 든 인터프리터 CPython 은 3.6 에서도 그렇게 돌았습니다. 그때는 CPython 이 그렇게 만들어졌을 뿐 언어가 정한 것은 아니었습니다.

순서에는 규칙이 둘 더 붙습니다. 있는 키의 값을 바꿔도 그 키의 순서는 안 바뀝니다. 키를 뺐다가 다시 넣으면 맨 끝으로 갑니다. 아래 코드의 주석은 그 줄을 지난 뒤의 키 순서입니다.

d = {"a": 1, "b": 2, "c": 3}
d["a"] = 9          # a b c
del d["b"]          # a c
d["b"] = 0          # a c b

a 는 값이 바뀌었어도 맨 앞에 남았습니다. 뺐다가 다시 넣은 b 는 맨 끝으로 갔습니다.

넣은 순서와 키의 크기 순서는 다릅니다. 파이썬 딕셔너리가 지키는 것은 넣은 순서뿐입니다. 키를 크기순으로 훑으려면 따로 정렬해야 합니다.

언어 안쪽의 딕셔너리

파이썬은 딕셔너리를 언어 안쪽에서도 씁니다. 대표가 네임스페이스입니다. 네임스페이스는 이름을 대면 그 이름이 가리키는 객체를 돌려주는 표입니다.

코드에 x 라는 이름이 나오면 파이썬은 이 표에서 x 를 찾습니다. 거기 묶인 객체가 x 의 값이 됩니다. 변수 이름도 함수 이름도 이 표에 등록됩니다.

파이썬의 네임스페이스는 대부분 딕셔너리로 만들어져 있습니다. 모듈 하나의 전역 이름들이 딕셔너리 하나에 담기는 식입니다. 키는 이름 문자열입니다. 값은 그 이름이 가리키는 객체입니다.

모듈의 전역 네임스페이스는 코드에서 딕셔너리로 꺼내 볼 수 있습니다. globals() 가 그 딕셔너리를 돌려줍니다.

x = 10
globals()["x"]      # 10
globals()["y"] = 5
y                   # 5

딕셔너리에서 "x" 를 꺼내자 변수 x 의 값이 나왔습니다. 딕셔너리에 "y" 를 넣자 변수 y 가 생겼습니다. 이름을 찾는 일이 딕셔너리에서 키를 찾는 일이라는 것이 이렇게 드러납니다.

걸리는 시간

해시테이블로 만든 딕셔너리는 쌍이 많아져도 빨리 찾습니다. 걸리는 시간은 빅오 표기법으로 적습니다. n 은 담긴 쌍의 수입니다.

O(1) 은 쌍이 몇 개든 걸리는 시간이 늘지 않는다는 뜻입니다. O(n) 은 쌍 수에 비례해 늘어난다는 뜻입니다.

쌍을 리스트에 늘어놓기만 하면 키 하나를 찾을 때 첫 쌍부터 차례로 견주어야 합니다. 이것이 O(n) 입니다. 딕셔너리는 키가 정한 칸 하나만 열어 보므로 평균 O(1) 에 찾습니다. 아래 표가 딕셔너리 연산의 시간입니다.

최악은 여러 키가 같은 칸으로 몰릴 때 나옵니다. 서로 다른 키가 같은 칸으로 오는 일을 해시 충돌이라고 합니다. 같은 칸으로 온 키끼리는 하나씩 견주어 가려야 하므로 몰린 만큼 느려집니다.

공간도 치릅니다. 해시테이블은 충돌을 줄이려고 빈 칸을 넉넉히 남겨 둡니다. 쌍이 차오르면 더 큰 배열을 잡아 쌍을 모두 옮겨 담습니다. 그래서 같은 수의 값을 리스트에 담을 때보다 메모리를 더 씁니다.

키의 크기 순서로 훑거나 「a 부터 c 까지」처럼 범위로 찾는 일은 해시테이블이 못 합니다. 그런 일에는 키를 크기순으로 담는 균형 이진 탐색 트리로 만든 맵을 씁니다. 파이썬 표준 라이브러리에는 그런 딕셔너리가 없습니다.

이름이 같은 다른 딕셔너리

딕셔너리라는 말은 자료구조 밖에서도 씁니다. 분야마다 가리키는 것이 다릅니다. 아래 표는 자주 만나는 넷을 나란히 놓은 것입니다.

검색 엔진은 문서를 역색인으로 찾습니다. 역색인은 낱말마다 그 낱말이 든 문서의 목록을 붙여 둔 색인입니다.

역색인에 나오는 낱말 전부를 모은 목록을 검색 쪽에서는 딕셔너리라고 부릅니다. 낱말마다 붙은 문서 목록은 포스팅 리스트라고 합니다. 아래 그림에서 cat 은 문서 1 과 4 에 나옵니다. dog 는 문서 2 · 4 · 7 에 나옵니다.

flowchart TD
    subgraph 딕셔너리
        T1["cat"]
        T2["dog"]
    end
    T1 --> P1["포스팅 리스트 · 문서 1 · 문서 4"]
    T2 --> P2["포스팅 리스트 · 문서 2 · 문서 4 · 문서 7"]

검색어 dog 가 들어오면 딕셔너리에서 dog 를 찾습니다. 거기 붙은 포스팅 리스트가 답이 되는 문서 번호입니다. 구조로 보면 낱말을 키로, 포스팅 리스트를 값으로 삼은 딕셔너리입니다.

사전식 압축은 앞서 나온 문자열을 목록에 모아 둡니다. 같은 문자열이 다시 나오면 문자열 대신 목록에서 몇 번째인지만 적습니다. 이 목록을 압축 쪽에서는 딕셔너리라고 부릅니다.

데이터베이스는 자기가 담은 테이블 · 열 · 인덱스가 무엇인지도 따로 적어 둡니다. 이렇게 데이터를 설명하는 데이터를 메타데이터라고 합니다. 데이터베이스가 품은 이 메타데이터 모음을 데이터 딕셔너리라고 부릅니다.

관련 항목

딕셔너리를 가리키는 다른 이름

맵 · 연관 배열 · 해시맵 · 심볼 테이블

딕셔너리가 속하는 상위 분류

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

딕셔너리를 만드는 구현

해시테이블 · 균형 이진 탐색 트리 · 이진 탐색 트리 · 트리맵 · 개방 주소법 · 체이닝

딕셔너리 키에 걸리는 조건

해시 함수 · 해시 가능 · 해시 충돌 · 동등성 · 불변 객체 · 튜플

파이썬에서 딕셔너리를 안에서 쓰는 기능

네임스페이스 · 메모이제이션 · 키워드 인자 · 딕셔너리 컴프리헨션 · Python

딕셔너리와 견주어 고르는 자료구조

리스트 · 배열 · 집합 · 레코드 · 데이터 클래스

딕셔너리의 비용을 적는 개념

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

딕셔너리와 이름이 겹치는 다른 개념

역색인 · 포스팅 리스트 · 사전식 압축 · 데이터 딕셔너리 · 시스템 카탈로그 · 메타데이터