체이닝

체이닝은 해시테이블에서 같은 칸으로 간 키들을 그 칸에 줄지어 매달아 두는 방법입니다. 겹친 항목은 그 칸의 목록에 이어 붙입니다. 찾을 때는 키가 가리키는 칸의 목록만 훑습니다. 메서드 호출을 점으로 잇는 메서드 체이닝과는 다른 말입니다.

상세

이 절은 칸 다섯 개짜리 표에 키를 넣고 찾고 지우는 과정을 따라갑니다. 그다음 목록 길이를 정하는 적재율과 복잡도를 봅니다. 마지막으로 같은 문제를 다르게 푸는 개방 주소법과 견줍니다.

키가 겹치는 까닭

해시테이블은 키로 값을 찾는 표입니다. 회원 번호로 회원 정보를 찾는 식입니다. 키를 받으면 어느 칸을 볼지 곧바로 계산하므로 표를 처음부터 훑지 않습니다.

칸 번호를 계산하는 함수가 해시 함수입니다. 해시 함수는 키를 숫자 하나로 바꿉니다. 그 숫자를 칸 수로 나눈 나머지가 칸 번호입니다.

칸은 버킷이라고도 부릅니다. 이 글에서는 계속 「칸」이라고 쓰겠습니다.

키로 올 수 있는 값은 끝없이 많습니다. 칸 수는 정해져 있습니다. 그래서 서로 다른 키가 같은 칸 번호를 받는 일을 피할 수 없습니다. 이 겹침이 해시 충돌입니다.

충돌한 항목을 어디에 둘지 정하는 일을 충돌 해소라고 부릅니다. 큰 갈래는 둘입니다. 하나는 표 안의 다른 빈 칸을 찾아가는 개방 주소법입니다. 다른 하나가 칸에 목록을 매다는 체이닝입니다.

칸에 매단 목록

체이닝에서 칸은 항목을 직접 담지 않습니다. 칸은 목록 하나의 첫머리를 가리킬 뿐입니다. 같은 칸 번호를 받은 항목은 전부 그 목록에 들어갑니다.

키가 정수이고 칸 번호를 「키를 5로 나눈 나머지」로 정한다고 해 보겠습니다. 12 와 7 은 나머지가 2 라서 둘 다 2번 칸으로 갑니다. 3 은 3번 칸, 10 은 0번 칸으로 갑니다.

flowchart TD
    subgraph T["칸 다섯 개짜리 표"]
        C0["0번 칸"]
        C1["1번 칸 · 비었다"]
        C2["2번 칸"]
        C3["3번 칸"]
        C4["4번 칸 · 비었다"]
    end
    C0 --> N10["10"]
    C2 --> N12["12"] --> N7["7"]
    C3 --> N3["3"]

그림에서 2번 칸 아래로 12 와 7 이 줄지어 이어졌습니다. 항목이 사슬처럼 꿰인 이 모양에서 체이닝이라는 이름이 왔습니다. 우리말로는 분리 연쇄법이라고도 부릅니다.

목록은 흔히 연결 리스트로 만듭니다. 연결 리스트는 항목마다 다음 항목이 어디 있는지를 적어 두는 목록입니다. 그 「어디」를 적은 값이 포인터입니다.

연결 리스트를 쓰는 까닭은 길이를 미리 몰라도 되기 때문입니다. 항목이 몇 개 올지 몰라도 하나씩 이어 붙이면 됩니다. 칸마다 크기를 정해 둘 필요가 없습니다.

넣기

넣기는 두 단계입니다. 키로 칸 번호를 계산합니다. 그 칸의 목록에 항목을 붙입니다.

같은 키가 이미 목록에 있으면 새로 붙이지 않고 값만 바꿉니다. 해시테이블은 한 키에 값 하나만 두기 때문입니다. 그래서 넣기도 목록을 한 번 훑어 같은 키가 있는지 봅니다.

아래 코드는 칸 다섯 개짜리 표의 넣기를 짧게 옮긴 것입니다. 목록은 연결 리스트 대신 파이썬 리스트로 씁니다. 주석이 달린 줄은 그 줄이 내는 값을 오른쪽에 적었습니다.

table = [[] for _ in range(5)]

def put(key, value):
    bucket = table[key % 5]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value
            return
    bucket.append([key, value])

12 % 5    # 2
7 % 5     # 2
put(12, "a")
put(7, "b")
put(12, "c")
table[2]  # [[12, 'c'], [7, 'b']]

12 와 7 은 나머지가 같아서 둘 다 2번 칸의 목록에 들어갔습니다. 세 번째 호출은 12 가 이미 있으므로 새 항목을 붙이지 않았습니다. 값만 "c" 로 바뀌었습니다.

찾기

찾기도 같은 칸에서 시작합니다. 칸 번호를 계산한 뒤 그 칸의 목록만 앞에서부터 훑습니다.

키가 같은 항목을 만나면 그것이 답입니다. 목록 끝까지 못 만나면 표에 없는 키입니다.

다른 칸의 목록은 보지 않습니다. 7 을 찾을 때는 2번 칸에 달린 두 항목만 봅니다. 표에 항목이 백만 개 있어도 한 칸에 달린 몇 개만 보면 끝납니다.

지우기

지우기는 찾기처럼 칸의 목록을 훑습니다. 지울 항목을 만나면 목록에서 뺍니다. 연결 리스트에서는 앞 항목이 가리키는 곳을 빠지는 항목의 다음 항목으로 바꿔 주면 됩니다.

개방 주소법에서는 지우기가 까다롭습니다. 개방 주소법은 겹친 항목을 정해진 순서에 따라 다른 칸에 하나씩 찾아가 넣습니다. 찾을 때도 같은 순서로 칸을 넘어가다 빈 칸을 만나면 멈춥니다.

칸을 그냥 비우면 그 순서에서 뒤쪽 칸으로 밀려 있던 항목을 못 찾게 됩니다. 이를 막으려고 지운 칸에 묘비라는 표시를 남깁니다.

체이닝에는 이런 표시가 필요 없습니다. 항목은 자기 칸의 목록에만 있습니다. 한 항목을 빼도 다른 칸의 찾기에는 아무 영향이 없습니다.

적재율과 목록 길이

표에 담긴 항목 수를 칸 수로 나눈 값이 적재율입니다. 항목 10개를 칸 5개에 담았다면 적재율은 2 입니다.

키가 칸마다 고르게 흩어진다고 보면 목록 하나의 평균 길이가 곧 적재율입니다. 적재율이 2 면 한 칸에 평균 두 항목이 달립니다. 찾기가 훑는 항목 수도 이 길이를 따라 늡니다.

체이닝은 항목을 표 밖의 목록에 두므로 적재율이 1을 넘어도 굴러갑니다. 칸보다 항목이 많아지면 목록이 길어질 뿐입니다. 넣기가 막히지는 않습니다.

그래도 목록이 길어지면 찾기가 느려집니다. 그래서 구현은 적재율이 정해 둔 선을 넘으면 칸 수를 늘립니다. 그리고 모든 항목의 칸 번호를 새로 계산해 다시 담습니다. 이 일이 리해싱입니다.

앞의 표에 17 과 22 를 더 넣어 보겠습니다. 둘 다 5로 나눈 나머지가 2 라서 2번 칸의 목록이 넷으로 늘어납니다.

flowchart TD
    subgraph T["칸 다섯 개 · 리해싱 전"]
        C0["0번 칸"]
        C1["1번 칸 · 비었다"]
        C2["2번 칸"]
        C3["3번 칸"]
        C4["4번 칸 · 비었다"]
    end
    C0 --> N10["10"]
    C2 --> N12["12"] --> N7["7"] --> N17["17"] --> N22["22"]
    C3 --> N3["3"]

칸을 열 개로 늘리면 칸 번호를 「키를 10으로 나눈 나머지」로 다시 계산합니다. 같은 여섯 항목이 이렇게 흩어집니다.

flowchart TD
    subgraph T["칸 열 개 · 리해싱 후"]
        D0["0번 칸"]
        D2["2번 칸"]
        D3["3번 칸"]
        D7["7번 칸"]
        DX["1·4·5·6·8·9번 칸 · 비었다"]
    end
    D0 --> M10["10"]
    D2 --> M12["12"] --> M22["22"]
    D3 --> M3["3"]
    D7 --> M7["7"] --> M17["17"]

가장 긴 목록이 넷에서 둘로 줄었습니다. 리해싱은 모든 항목을 한 번씩 옮기므로 그 순간에는 비쌉니다. 칸 수를 두 배씩 늘리면 리해싱이 점점 드물어집니다.

드물게 오는 큰 비용은 여러 번의 넣기에 나눠 셈할 수 있습니다. 넣기 전체의 비용을 넣은 횟수로 나누면 넣기 한 번의 몫은 항목이 늘어도 일정하게 남습니다. 이렇게 셈하는 법이 분할 상환 분석입니다. 아래 복잡도 표에서 넣기의 평균도 이 셈을 따릅니다.

복잡도

이 소절은 넣기·찾기·지우기에 드는 시간을 평균과 최악으로 나눠 봅니다. 공간은 따로 봅니다.

시간은 빅오 표기법으로 적습니다. O(1) 은 항목이 늘어도 드는 시간이 일정하다는 뜻입니다. O(n) 은 드는 시간이 항목 수 n 에 비례해 늘어난다는 뜻입니다.

아래 표의 평균은 두 조건을 둔 값입니다. 키가 칸마다 고르게 흩어집니다. 적재율을 정해 둔 선 아래로 유지합니다. 넣기는 같은 키가 있는지 목록을 훑어 확인하는 넣기입니다.

평균이 O(1) 인 까닭은 목록 길이가 적재율을 따르기 때문입니다. 적재율을 일정하게 묶어 두면 항목이 백만 개든 천 개든 한 칸의 목록은 몇 개로 남습니다.

같은 키 확인을 건너뛰고 목록 맨 앞에 붙이기만 하면 넣기는 최악도 O(1) 입니다. 칸이 목록의 첫머리를 가리키므로 맨 앞에는 훑지 않고 바로 붙습니다. 같은 키가 목록에 두 번 들어가지 않는다는 것은 호출하는 쪽이 보장해야 합니다.

최악은 모든 키가 한 칸으로 몰릴 때입니다. 그러면 표 전체가 목록 하나가 되어 찾기가 모든 항목을 훑습니다.

이런 몰림은 해시 함수가 키를 고르게 흩지 못할 때 생깁니다. 누군가 같은 칸으로 가는 키만 골라 보내도 생깁니다. 이 공격을 해시 플러딩이라고 부릅니다.

이 몰림에 대비해 목록이 일정 길이를 넘으면 균형 이진 탐색 트리로 바꿔 담는 구현도 있습니다. 이 트리는 항목을 크기 순으로 나눠 담습니다. 찾을 때마다 비교 한 번으로 후보가 절반씩 줄어듭니다.

트리로 바꾸면 최악이 O(n) 에서 O(log n) 으로 내려갑니다. O(log n) 은 항목이 두 배로 늘 때 비교가 한 번씩만 느는 정도입니다.

공간은 칸 배열과 항목 전부입니다. 칸이 m 개, 항목이 n 개면 O(n + m) 입니다. 여기에 항목마다 포인터가 하나씩 더 붙습니다. 개방 주소법은 항목을 표 안에 담으므로 이 포인터가 없습니다.

개방 주소법과의 차이

두 방식 모두 겹친 항목을 버리지 않습니다. 겹친 항목을 표 밖에 두느냐 표 안에 두느냐가 갈림입니다. 그 하나의 차이가 아래 다섯 줄을 만듭니다.

CPU(중앙 처리 장치)는 메모리를 한 바이트씩 읽지 않습니다. 이웃한 바이트를 한 묶음으로 캐시에 가져옵니다. 캐시는 CPU 곁에 붙은 작고 빠른 저장소입니다. 이미 캐시에 있는 데이터는 메모리까지 가지 않고 읽습니다.

개방 주소법의 칸은 배열 하나에 이어 붙어 있습니다. 한 칸을 읽으면 옆 칸도 대개 같은 묶음에 실려 캐시에 올라옵니다. 가까이 놓인 데이터를 함께 읽어 얻는 이 이점이 캐시 지역성입니다.

체이닝은 이 이점을 덜 받습니다. 연결 리스트의 항목은 메모리 곳곳에 흩어져 있습니다. 다음 항목으로 넘어갈 때마다 떨어진 곳을 새로 읽어야 합니다.

대신 표가 차 갈수록 체이닝이 버티는 힘이 큽니다. 키가 고르게 흩어진다고 볼 때, 표에 없는 키를 찾으며 확인하는 수는 아래와 같습니다. 체이닝은 칸 하나를 보고 그 목록을 끝까지 훑습니다. 개방 주소법은 빈 칸을 만날 때까지 칸을 훑습니다.

체이닝 쪽은 적재율에 1 을 더한 값이라 곧게 늡니다. 개방 주소법 쪽은 적재율이 1 에 가까워질수록 가파르게 늡니다.

쓸 때와 안 쓸 때

아래 표는 하려는 일마다 체이닝이 맞는지를 가립니다.

마지막 줄이 체이닝의 가장 큰 약점입니다. 정수 키처럼 작은 항목이라면 포인터가 항목만큼 메모리를 먹습니다. 흩어진 메모리를 따라가는 비용도 무시하기 어렵습니다.

이름이 같은 다른 체이닝

「체이닝」은 해시테이블 밖에서도 자주 듣는 말입니다. 무엇을 잇느냐가 다를 뿐 「줄줄이 잇는다」는 뜻은 같습니다. 백엔드 코드에서 만나는 것은 대개 아래 넷입니다.

넷 다 이 글의 체이닝과는 다른 말입니다. 해시테이블 이야기 안에서 체이닝이라고 하면 이 글의 뜻입니다.

관련 항목

이것이 올라타는 자료구조와 그 부품

해시테이블 · 해시 함수 · 해시값 · 버킷 · 배열 · 해시 충돌 · 충돌 해소

칸에 매다는 목록의 구조

연결 리스트 · 포인터 · 노드 · 균형 이진 탐색 트리 · 레드-블랙 트리

같은 역할을 두고 겨루는 충돌 해소 방식

개방 주소법 · 선형 탐사 · 이차 탐사 · 이중 해싱 · 뻐꾸기 해싱 · 로빈 후드 해싱 · 합병 연쇄법

목록 길이를 좌우하는 지표와 작업

적재율 · 리해싱 · 균등 해싱 · 해시 플러딩 · 캐시 지역성 · 묘비

이 구조로 구현하는 자료형

딕셔너리 · 해시맵 · 해시셋 · 연관 배열 · 심볼 테이블

이름이 같아 헷갈리는 다른 기법

메서드 체이닝 · 옵셔널 체이닝 · 프로미스 체이닝 · 해시 체인 · 플루언트 인터페이스

복잡도를 적는 표기와 분석

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