체이닝

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

상세

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

키가 겹치는 까닭

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

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

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

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

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

칸에 매단 목록

체이닝에서 표의 칸마다 목록이 하나씩 딸립니다. 같은 칸 번호를 받은 항목은 전부 그 목록에 들어갑니다.

키는 정수라고 해 보겠습니다. 칸 번호는 「키를 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번 칸에 달린 두 항목만 봅니다. 표에 항목이 백만 개 있어도 한 칸에 달린 몇 개만 보면 끝납니다.

지우기

지우기는 찾기처럼 칸의 목록을 훑습니다. 지울 노드를 만나면 그 앞 노드가 가리키던 곳을 지울 노드의 다음 노드로 바꿉니다. 그러면 지운 노드는 목록에서 떨어져 나갑니다.

아래 두 그림은 목록 하나만 떼어 그린 것입니다. 2번 칸에 12 · 7 · 17 이 달려 있습니다. 그중 7 을 지웁니다.

flowchart TD
    subgraph B["지우기 전"]
        S1["2번 칸"] --> A12["12"] --> A7["7"] --> A17["17"]
    end

flowchart TD
    subgraph A["지운 뒤"]
        S2["2번 칸"] --> B12["12"] --> B17["17"]
    end

12 가 가리키는 곳이 7 에서 17 로 바뀌었습니다. 바뀐 포인터는 하나뿐입니다. 다른 칸은 손대지 않았습니다.

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

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

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

목록 대신 매다는 그릇

칸에 매다는 것이 꼭 연결 리스트일 필요는 없습니다. 키로 찾을 수 있는 그릇이면 무엇이든 매달 수 있습니다. 칸마다 무엇을 매달든 「칸마다 그릇 하나」라는 모양은 같으므로 여전히 체이닝입니다.

목록 대신 매달 수 있는 그릇 가운데 하나가 균형 이진 탐색 트리입니다. 이진 탐색 트리는 항목을 크기 순으로 나눠 담습니다. 왼쪽 아래로는 작은 키, 오른쪽 아래로는 큰 키가 갑니다.

flowchart TD
    C2["2번 칸"] --> R12["12"]
    R12 --> L7["7"]
    R12 --> R22["22"]
    R22 --> L17["17"]
    R22 --> R27["27"]

이 그림은 2번 칸에 7 · 12 · 17 · 22 · 27 을 트리로 매단 것입니다. 17 을 찾을 때는 12 보다 크니 오른쪽, 22 보다 작으니 왼쪽으로 내려갑니다.

「균형」은 트리의 왼쪽과 오른쪽 깊이를 비슷하게 맞춰 둔다는 말입니다. 그래서 비교 한 번마다 남은 후보의 절반쯤을 건너뜁니다. 목록처럼 앞에서부터 다 훑지 않습니다.

대가는 노드가 커진다는 것입니다. 트리 노드는 다음 하나가 아니라 왼쪽과 오른쪽 둘을 가리킵니다. 그래서 목록이 짧을 때는 연결 리스트로 둡니다. 한 칸에 항목이 몰려 목록이 길어질 때만 트리로 바꾸는 구현도 있습니다.

적재율과 목록 길이

표에 담긴 항목 수를 칸 수로 나눈 값이 적재율입니다. 항목 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"]

가장 긴 목록이 넷에서 둘로 줄었습니다. 리해싱은 모든 항목을 한 번씩 옮기므로 그 순간에는 비쌉니다. 칸 수를 두 배씩 늘리면 리해싱이 점점 드물어집니다. 이 비용을 넣기 한 번마다 얼마로 셈하는지는 「복잡도」 절이 다룹니다.

개방 주소법과의 차이

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

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

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

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

대신 표가 차 갈수록 체이닝이 버티는 힘이 큽니다. 개방 주소법은 표가 찰수록 빈 칸을 만나기까지 훑는 칸이 가파르게 늡니다. 체이닝은 목록이 적재율만큼 곧게 길어질 뿐입니다. 두 쪽의 수치는 「복잡도」 절에 있습니다.

쓸 때와 안 쓸 때

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

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

이름이 같은 다른 체이닝

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

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

복잡도

적재율을 일정한 선 아래로 묶어 두면 넣기·찾기·지우기는 항목이 아무리 늘어도 평균 시간이 일정합니다. 모든 키가 한 칸에 몰리면 세 연산 모두 항목 수에 비례해 느려집니다. 이 절은 그 두 끝을 표로 세웁니다. 그다음 평균이 어떤 가정에 기대는지, 최악이 언제 오는지를 봅니다.

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

아래에서 n 은 표에 담긴 항목 수, m 은 칸 수입니다. 적재율은 n 을 m 으로 나눈 값입니다. 기호로는 α(알파)라고 적습니다.

표의 평균 칸에는 두 가지 셈이 들어 있습니다. 찾기와 지우기의 평균은 키가 고르게 흩어진다고 볼 때 기대되는 값입니다. 넣기의 평균은 여기에 가끔 오는 리해싱 비용을 넣기 여러 번에 나눠 얹은 값입니다. 두 셈은 아래 「평균을 떠받치는 가정」과 「리해싱의 몫」이 차례로 풉니다.

평균을 떠받치는 가정

평균 O(1) 은 단순 균등 해싱이라는 가정 위에 섭니다. 어느 키든 m 개 칸 가운데 하나에 같은 확률로 떨어진다고 보는 가정입니다. 해시 함수가 키를 고르게 흩는다는 말을 셈할 수 있게 적은 것입니다.

이 가정 아래서 한 칸의 목록 길이는 평균 α 입니다. 찾기 한 번은 칸 번호를 계산해 칸을 한 번 봅니다. 그다음 그 칸의 목록을 훑습니다.

그래서 찾기의 평균은 O(1 + α) 입니다. 앞의 1 은 칸을 보는 몫입니다. 뒤의 α 는 목록을 훑는 몫입니다.

구현은 α 가 선을 넘으면 리해싱으로 칸을 늘립니다. α 가 상수 하나 아래로 묶이므로 O(1 + α) 는 O(1) 이 됩니다. 항목이 백만 개든 천 개든 한 칸의 목록은 몇 개로 남습니다.

최악이 오는 조건

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

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

칸에 목록 대신 균형 이진 탐색 트리를 매달면 최악이 O(log n) 으로 내려갑니다. 키끼리 크기를 비교할 수 있어야 쓸 수 있는 방법입니다. O(log n) 은 항목이 두 배로 늘 때 비교가 한 번씩만 느는 정도입니다. 트리는 비교 한 번마다 후보를 절반씩 줄이기 때문입니다.

넣기를 맨 앞에 붙이기만으로 끝내면 목록을 훑는 몫이 없어집니다. 칸이 목록 첫 노드를 가리키므로 맨 앞에는 훑지 않고 바로 붙습니다. 이때 같은 키가 목록에 두 번 들어가지 않는다는 것은 부르는 쪽이 보장해야 합니다.

그래도 그 넣기가 리해싱을 일으키면 O(n) 이 걸립니다. 칸 수가 고정된 표라면 리해싱이 없으므로 최악도 O(1) 입니다.

공간

칸이 m 개, 항목이 n 개면 공간은 O(n + m) 입니다. 칸 배열이 m 을, 노드가 n 을 차지합니다.

여기에 노드마다 다음 노드를 가리키는 포인터가 하나씩 더 붙습니다. 개방 주소법은 항목을 표 안에 담으므로 이 포인터가 없습니다. 트리를 매달면 노드마다 포인터가 둘로 늡니다.

리해싱의 몫

리해싱 한 번은 항목 n 개를 전부 옮기므로 O(n) 입니다. 넣기 하나가 하필 리해싱을 일으키면 그 넣기만 O(n) 이 걸립니다.

칸 수를 두 배씩 늘리면 이 비용이 드물게만 옵니다. 항목을 n 개 넣는 동안 리해싱이 옮기는 항목 수를 다 더해도 2n 을 넘지 않습니다. 그 합을 넣은 횟수 n 으로 나누면 넣기 한 번의 몫은 상수입니다.

이렇게 드물게 오는 큰 비용을 여러 번의 연산에 나눠 셈하는 법이 분할 상환 분석입니다. 표의 넣기 평균 O(1) 은 리해싱을 이 셈으로 넣은 값입니다.

개방 주소법과 견준 확인 수

표에 없는 키를 찾을 때 몇 번 확인하는지를 두 방식으로 견줍니다. 칸 하나를 보는 것과 목록 노드 하나를 보는 것을 각각 1로 셉니다. 두 값 모두 키가 고르게 흩어진다는 가정 아래의 기대값입니다. 개방 주소법은 키마다 칸을 훑는 순서까지 고르게 흩어진다고 봅니다.

체이닝은 칸 하나를 본 뒤 그 목록을 끝까지 훑으므로 1 + α 번입니다. 개방 주소법은 빈 칸을 만날 때까지 칸을 훑으므로 많아야 1 / (1 − α) 번입니다. 개방 주소법 쪽 값은 기대값의 상한입니다.

체이닝 쪽은 α 에 1 을 더한 값이라 곧게 늡니다. 개방 주소법 쪽은 α 가 1 에 가까워질수록 분모가 0 으로 다가가 가파르게 늡니다.

예시

체이닝이 들어가 있는 실물 둘을 봅니다. 하나는 언어 런타임의 표준 자료형입니다. 다른 하나는 운영체제 커널의 해시테이블입니다.

자바 HashMap

OpenJDK 의 java.util.HashMap 은 평소에는 칸마다 노드 목록을 다는 해시테이블로 돕니다. HashMap 은 칸을 bin 이라고 부릅니다. 이 글의 칸과 같은 것입니다.

한 칸의 목록이 너무 길어지면 그 칸을 트리 노드(TreeNode) 묶음으로 바꿉니다. 트리 노드는 자바의 다른 표준 맵인 java.util.TreeMap 의 노드와 비슷하게 짜여 있습니다. 앞의 「목록 대신 매다는 그릇」에서 본 바꿔 담기가 이것입니다.

언제 바꾸는지는 상수 넷이 정합니다.

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

「표를 키우며 칸이 갈라질 때」는 상세의 리해싱 그림에서 2번 칸이 2번 칸과 7번 칸으로 나뉜 것과 같은 일입니다.

트리로 바꾸는 까닭은 최악을 묶는 데 있습니다. 트리 칸은 노드를 먼저 해시값 순서로 줄 세웁니다. 해시값이 같은 노드끼리는 키의 크기를 비교해 줄 세웁니다. 이 비교는 두 키가 같은 클래스이고 그 클래스가 자바의 크기 비교 방식(Comparable)을 갖췄을 때만 씁니다.

같은 칸에 든 키라도 해시값은 서로 다를 수 있습니다. 칸 번호는 해시값을 칸 수로 나눈 나머지입니다. 해시값이 달라도 나머지만 같으면 같은 칸에 듭니다. 그래서 키의 해시값이 서로 다르거나 키끼리 크기를 비교할 수 있으면 최악이 O(log n) 으로 묶입니다.

hashCode() 는 키 객체가 자기 해시값을 돌려주는 메서드입니다. 이 메서드가 값을 고르게 못 흩는 경우에도 성능이 한꺼번에 무너지지 않고 조금씩 나빠집니다. 실수로 그렇게 짠 경우와 일부러 노린 경우를 둘 다 겨냥한 것입니다.

트리 노드는 보통 노드의 두 배쯤 큽니다. 칸에 노드가 충분히 쌓였을 때만 트리를 씁니다. 지우거나 표를 키워 노드가 줄면 다시 보통 칸으로 되돌립니다.

해시값이 무작위라면 트리 칸은 드뭅니다. 「적재율과 목록 길이」에서 본 대로 한 칸의 평균 노드 수는 적재율과 같습니다. 그런데 0.75 는 적재율이 오를 수 있는 끝, 곧 표를 키우는 문턱입니다. 표를 키우면 칸이 한꺼번에 크게 늘어 적재율이 뚝 떨어집니다. 그 뒤 항목이 쌓이면서 다시 0.75 까지 오릅니다. 그래서 평소의 적재율은 0.75 보다 낮은 곳에 머뭅니다.

HashMap 의 구현 노트는 이때 한 칸의 노드 수가 평균 0.5 쯤인 푸아송 분포를 따른다고 적습니다. 푸아송 분포는 드문 일이 몇 번 겹치는지를 셀 때 쓰는 확률 분포입니다. 노트는 표를 키우는 단위가 커서 이 평균이 크게 오르내린다는 말도 함께 적습니다.

오르내림을 무시하고 평균을 0.5 로 놓고 셈한 확률은 아래와 같습니다.

노드가 8개 몰린 칸은 천만 칸에 한 칸꼴도 안 됩니다. 트리 전환 문턱이 8 이니 고르게 흩어진 해시값에서는 트리 칸이 거의 생기지 않습니다.

리눅스 커널 hashtable.h

리눅스 커널은 크기가 고정된 해시테이블을 매크로와 인라인 함수 몇 개로 제공합니다. 칸 배열을 선언하는 매크로가 DEFINE_HASHTABLE 입니다.

#define DEFINE_HASHTABLE(name, bits)						\
	struct hlist_head name[1 << (bits)] =					\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

칸 배열의 원소가 struct hlist_head, 곧 목록의 첫머리입니다. 칸은 목록 첫 노드를 가리키기만 하는 꼴입니다. 칸 수는 1 << (bits), 곧 2의 bits 제곱으로 고정됩니다. bits 가 10 이면 칸이 1024 개입니다.

넣기와 같은 칸 훑기는 이렇게 생겼습니다.

#define hash_add(hashtable, node, key)						\
	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

#define hash_for_each_possible(name, obj, member, key)			\
	hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)

hash_add 는 키로 칸 번호를 고른 뒤(hash_min) 그 칸 목록의 맨 앞에 노드를 붙입니다(hlist_add_head). 매크로 본문에 같은 키를 찾는 단계가 없습니다. 「복잡도」 절의 「맨 앞에 붙이기만」 넣기가 이것입니다. 칸 수가 고정이라 리해싱도 없습니다.

node 인자는 넣을 객체 안에 든 struct hlist_node 입니다. 목록을 잇는 포인터가 객체 구조체 안에 들어 있는 셈입니다. 목록 노드를 따로 만들지 않고 객체 자체를 칸 목록에 겁니다.

hash_for_each_possible 은 같은 칸으로 간 객체를 전부 돕니다. 이름 그대로 「그 키일 수도 있는」 객체들입니다. member 는 구조체 안에서 hlist_node 가 든 필드 이름입니다.

지우기는 인라인 함수 hash_del(node) 하나입니다. 노드만 받아 hlist_del_init 으로 목록에서 뺍니다. 칸 번호를 다시 계산하는 단계가 없습니다.

경계

합병 연쇄법(coalesced chaining)도 이 편의 체이닝인가. 아닙니다.

합병 연쇄법도 겹친 항목을 목록으로 잇습니다. 이름에 chaining 이 들어갑니다. 「목록으로 충돌을 푸는 방식」이라는 무리로 함께 묶이기도 합니다. 헷갈리는 까닭이 여기 있습니다.

갈림은 목록이 어디 있느냐입니다. 합병 연쇄법의 목록은 표 바깥이 아니라 표 안의 칸들을 따라 이어집니다. 충돌한 항목은 배열의 다음 빈 칸에 들어갑니다. 그 칸이 목록 끝에 이어 붙습니다. 다음 빈 칸은 개방 주소법이 칸을 훑는 방식으로 찾습니다.

그러면 이 편의 체이닝이 내세운 두 성질이 둘 다 성립하지 않습니다.

겹친 항목을 표 밖에 두느냐 안에 두느냐가 체이닝의 정의선입니다. 합병 연쇄법도 목록을 씁니다. 그런데 항목은 표 안에 둡니다. 그래서 이 편에 들지 않습니다.

사용처

체이닝을 고른 곳마다 까닭이 다릅니다. 예시에 쓴 자바 HashMap 과 리눅스 커널 말고 셋을 봅니다.

Redis

Redis 는 dict.c 에 메모리 위 해시테이블을 둡니다. 칸 수는 2의 거듭제곱입니다. 필요하면 크기를 스스로 바꿉니다. 충돌은 체이닝으로 풉니다.

표를 키울 때 Redis 는 새 표를 하나 더 마련합니다. 항목은 한꺼번에 옮기지 않습니다. 리해싱 한 걸음은 칸 하나를 옛 표에서 새 표로 옮깁니다.

체이닝이라 그 칸에 키가 여럿 달려 있을 수 있습니다. 그 키들이 함께 옮겨 갑니다.

이 한 걸음은 찾기나 고치기를 할 때마다 끼워 돕니다. 그래서 표는 쓰이는 동안 옛 표에서 새 표로 조금씩 옮겨 갑니다.

리해싱을 잠시 멈춰 둔 동안에는 이 한 걸음을 건너뜁니다. 표의 항목을 차례로 도는 반복자가 리해싱 도중에 있으면 두 표를 건드릴 수 없습니다. 건드리면 반복자가 항목을 빠뜨리거나 두 번 볼 수 있습니다.

옛 표에는 빈 칸도 섞여 있습니다. 한 걸음은 옮길 칸을 찾아 빈 칸을 지나갑니다. 한 걸음이 들르는 빈 칸은 열 개까지입니다. 상한이 없으면 한 걸음의 일이 끝없이 늘어 함수가 오래 막힐 수 있기 때문입니다. 그래서 한 걸음이 칸 하나도 못 옮기고 끝날 수 있습니다.

PostgreSQL

PostgreSQL 은 dynahash.c 에 체이닝을 쓰는 해시테이블을 둡니다. 한 프로세스 안에서만 쓰는 표와 여러 프로세스가 함께 보는 공유 메모리 표를 둘 다 받칩니다.

공유 표를 잠금 하나로 지키면 많이 쓰는 표에서 병목이 됩니다. 이를 피하려고 분할 모드를 둡니다. 분할 모드는 칸들을 여러 묶음으로 갈라 묶음마다 다른 잠금(LWLock)을 겁니다.

dynahash 는 평소에 표를 쓰는 도중 칸을 쪼갤 수 있습니다. 칸을 쪼개면 한 칸에 달린 항목 일부가 다른 칸의 목록으로 넘어갑니다. 분할 모드는 이 쪼개기를 막습니다.

그러면 칸마다 달린 목록이 다른 칸과 상관없이 돕니다. 그래서 칸을 어떤 묶음으로 나누든 묶음마다 따로 잠글 수 있습니다.

PostgreSQL 에는 simplehash 라는 해시테이블 구현이 하나 더 있습니다. 그것과 견줘 dynahash 가 내세우는 장점이 분할 말고도 셋 더 있습니다.

둘째 장점은 견주는 상대인 simplehash 가 충돌 때 항목을 옮긴다는 것을 깔고 있습니다. 항목이 크면 옮길 때마다 복사할 바이트가 많습니다. 체이닝은 항목을 노드에 둔 채 목록의 포인터만 고칩니다.

GCC 의 libstdc++

libstdc++ 는 GCC 가 딸려 내는 C++ 표준 라이브러리 구현입니다. 그 해시테이블 _Hashtable 은 칸마다 따로 목록을 두지 않습니다. 노드 전부를 단일 연결 리스트 하나에 잇습니다. 단일 연결 리스트는 노드가 다음 노드 하나만 가리키는 연결 리스트입니다.

칸은 목록을 갖는 대신 이 줄의 한 노드를 가리킵니다. 가리키는 노드는 그 칸 첫 노드의 바로 앞 노드입니다. 빈 칸은 아무것도 가리키지 않습니다.

줄 맨 앞에는 값을 담지 않는 표시 노드 _M_before_begin 이 있습니다. 줄 맨 앞 노드가 든 칸은 이 표시 노드를 가리킵니다.

아래 그림은 상세의 칸 다섯 개짜리 표를 이 배치로 옮긴 것입니다. 칸 묶음이 줄에 놓이는 순서는 예로 든 것입니다.

flowchart TD
    subgraph K["칸 배열"]
        K0["0번 칸"]
        K1["1번 칸 · 비었다"]
        K2["2번 칸"]
        K3["3번 칸"]
        K4["4번 칸 · 비었다"]
    end
    subgraph L["노드 한 줄"]
        BB["표시 노드 _M_before_begin"] --> N10["10"] --> N12["12"] --> N7["7"] --> N3["3"]
    end
    K0 -.-> BB
    K2 -.-> N10
    K3 -.-> N7

2번 칸은 자기 첫 노드 12 가 아니라 그 앞 노드 10 을 가리킵니다. 3번 칸도 3 의 앞 노드 7 을 가리킵니다. 0번 칸의 첫 노드 10 은 줄 맨 앞이라 표시 노드를 가리킵니다.

앞 노드를 쥐는 까닭은 넣기와 빼기에 있습니다. 「지우기」에서 본 것처럼 연결 리스트에서 노드를 빼려면 앞 노드의 포인터를 고쳐야 합니다. 칸이 앞 노드를 쥐고 있으면 넣기는 「그 노드 뒤에 넣기」로, 빼기는 「그 노드 뒤를 빼기」로 끝납니다.

표 전체를 도는 순회는 노드 줄을 따라가기만 합니다. 칸마다 목록을 두는 꼴에서는 순회가 빈 칸도 하나씩 거쳐야 합니다. 이 배치에서는 다음 노드로 넘어가는 비용이 빈 칸 수와 상관없습니다.

대가도 있습니다. 한 칸의 노드를 훑다 보면 줄이 다음 칸 노드로 넘어갑니다. 그림에서 2번 칸의 7 다음이 3번 칸의 3 입니다. 그래서 노드마다 해시값을 확인해 아직 같은 칸인지 가려야 합니다.

노드가 해시값을 품고 있는 것은 해시값을 노드에 저장해 두는 설정(__cache_hash_code)을 켰을 때뿐입니다. 끄면 칸을 가리는 이 확인을 할 때마다 그 노드의 키로 해시값을 다시 계산해야 합니다. 이 설계는 해시 함수가 꽤 빠르다고 가정합니다. 다시 계산하는 일이 되풀이되어도 견딜 만하다고 보는 것입니다.

그 계산을 아예 없애는 길이 설정을 켜 두는 것입니다. libstdc++ 가 이 설정을 켜 두기를 강하게 권하는 까닭 가운데 하나가 칸을 가리는 확인입니다. 기본으로 켜져 있는지는 자료에 없습니다(미확인).

이 배치는 libstdc++ 한 구현의 것입니다. C++ 표준이 체이닝을 강제한다는 근거로 읽으면 안 됩니다.

관련 항목

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

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

칸에 매다는 그릇의 구조

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

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

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

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

적재율 · 리해싱 · 점진적 리해싱 · 단순 균등 해싱 · 균등 해싱 · 해시 플러딩 · 묘비

체이닝이 비용을 치르는 메모리 계층

CPU 캐시 · 캐시 라인 · 캐시 지역성 · 캐시 미스

이 구조로 구현하는 자료형과 제품

딕셔너리 · 해시맵 · 해시셋 · 연관 배열 · 심볼 테이블 · HashMap · Redis · PostgreSQL · 리눅스 커널 · libstdc++

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

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

복잡도를 적는 표기와 분석

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 분할 상환 분석 · 분할 상환 비용 · 푸아송 분포 · 반복자