개방 주소법

개방 주소법은 해시테이블에서 두 키가 같은 칸으로 갈 때 뒤에 온 키를 표 안의 다른 빈 칸으로 보내는 방법입니다. 가려던 칸이 차 있으면 정해진 규칙으로 다음 칸을 봅니다. 빈 칸을 만나면 거기에 담습니다. 표 밖에 목록을 따로 매달지 않습니다.

쉽고 빠른 이해

개방 주소법은 넣으려던 칸이 차 있으면 옆의 빈 칸을 찾아 담는 방법입니다. 키 damson 은 3번 칸에 가야 합니다. 3번이 차 있으면 4번, 5번을 차례로 보고 빈 칸에 넣습니다.

이게 없으면 겹친 항목을 버리거나, 표 밖에 목록을 하나 만들어 칸마다 매달아야 합니다. 목록을 매달면 항목마다 딸린 메모리를 더 쓰고, 찾을 때 표 밖으로 나갔다 와야 합니다.

어떻게 도나:

1. 키를 숫자로 바꿔 갈 칸을 고릅니다
2. 그 칸이 차 있으면 정해진 규칙으로 다음 칸을 봅니다
3. 빈 칸을 만나면 담습니다. 찾을 때도 같은 규칙으로 훑습니다

대가는 둘입니다. 표가 차 갈수록 빈 칸이 드물어져 훑어야 하는 칸 수가 가파르게 늡니다. 그리고 항목을 지울 때 칸을 그냥 비우면 뒤에 밀려 있던 항목을 못 찾게 되어, 지웠다는 표시를 따로 남겨야 합니다.

상세

이 절은 넣기·찾기·지우기를 칸 여덟 개짜리 표에서 따라간 뒤, 다음 칸을 고르는 규칙 셋과 적재율, 분리 연쇄법과의 차이까지 봅니다.

키가 겹치는 까닭

해시 함수는 키를 숫자 하나로 바꿉니다. 그 숫자가 해시값입니다.

해시값을 칸 수로 나눈 나머지가 키를 담을 칸 번호입니다. 이 칸을 버킷이라고도 부릅니다. 이 글에서는 계속 「칸」이라고 쓰겠습니다.

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

충돌이 났을 때 두 항목을 어디에 둘지 정하는 일이 충돌 해소입니다. 큰 갈래는 둘입니다. 분리 연쇄법은 칸마다 목록을 매달아 겹친 항목을 그 목록에 이어 붙입니다. 개방 주소법은 표 밖으로 나가지 않고 표 안의 다른 빈 칸을 찾습니다.

두 갈래가 겹친 키를 어디로 보내는지를 그림으로 보면 이렇습니다.

flowchart TD
    H["키 두 개가 같은 3번 칸으로 간다"]
    H --> A1
    H --> B1
    subgraph OA["개방 주소법 · 표 안의 빈 칸으로 보낸다"]
        A1["3번 칸 · cherry"] --> A2["4번 칸 · 뒤에 온 키"]
    end
    subgraph SC["분리 연쇄법 · 칸에 목록을 매단다"]
        B1["3번 칸"] --> B2["cherry"] --> B3["뒤에 온 키"]
    end

지정 주차 칸 비유

차마다 대야 할 칸 번호가 정해진 주차장을 떠올려 봅니다. 내 칸은 3번입니다. 거기 다른 차가 이미 있으면 4번, 5번으로 한 칸씩 내려가 빈 칸을 찾습니다.

나중에 그 차를 찾는 사람도 같은 규칙을 따릅니다. 3번부터 시작해 한 칸씩 내려갑니다.

넣기와 찾기

키가 갈 첫 칸은 해시값이 정합니다. 그 칸이 차 있으면 다음 후보를 계산해 봅니다. 후보 칸을 차례로 만들어 내는 일이 탐사입니다. 그렇게 만들어진 칸 번호의 줄을 탐사 순서라고 부릅니다.

가장 단순한 규칙은 한 칸씩 옆으로 옮기는 것입니다. 칸이 여덟 개인 표라면 첫 칸이 3번인 키의 j 번째 후보는 (3 + j) % 8 입니다. 나머지 연산을 쓰는 까닭은 표의 끝에 닿았을 때 0번 칸으로 되돌아오기 위해서입니다.

여덟 칸을 늘어놓고 키 damson 이 앉을 칸을 따라가 보겠습니다.

flowchart TD
    K["키 damson · 첫 칸은 3번"] --> C3
    subgraph T["칸 여덟 개짜리 표"]
        C0["0번 · 빈 칸"] --> C1["1번 · apple"]
        C1 --> C2["2번 · 빈 칸"]
        C2 --> C3["3번 · cherry"]
        C3 -->|"차 있다"| C4["4번 · banana"]
        C4 -->|"차 있다"| C5["5번 · 빈 칸"]
        C5 --> C6["6번 · 빈 칸"]
        C6 --> C7["7번 · fig"]
        C7 -->|"나머지 연산이 0번으로 되돌린다"| C0
    end
    C5 --> P["빈 칸을 만났다 · damson 을 5번에 담는다"]

찾을 때도 같은 순서로 훑습니다. 3번부터 시작해 키가 같은 항목을 만나면 그것이 답입니다.

빈 칸을 만나면 그 키가 표에 없다고 판정하고 멈춥니다. 넣을 때도 빈 칸을 만나는 순간 거기에 담았을 테니, 빈 칸 너머에 그 키가 있을 수 없기 때문입니다. 이 판정이 개방 주소법의 조회를 짧게 끝내 줍니다.

지우기가 끊는 탐사 사슬

앞 그림의 표에서 banana 를 지운다고 해 보겠습니다. 4번 칸을 그냥 빈 칸으로 되돌리면 어떻게 되는지를 아래 표가 보입니다.

이제 damson 을 찾으면 3번에서 시작해 4번에서 빈 칸을 만납니다. 조회는 거기서 없다고 판정하고 멈춥니다. 5번에 멀쩡히 있는 항목을 못 찾는 것입니다.

그래서 개방 주소법은 지운 칸에 「여기 있던 것을 지웠다」는 표시를 남깁니다. 이 표시가 묘비입니다. 조회는 묘비를 만나면 멈추지 않고 지나갑니다. 새로 넣을 때는 묘비가 놓인 칸을 빈 칸처럼 써도 됩니다.

조회는 칸마다 셋 중 하나를 보고 멈출지 말지를 정합니다.

flowchart TD
    S["첫 칸 3번부터 훑는다"] --> Q1{"빈 칸인가"}
    Q1 -->|"빈 칸이다"| A1["표에 없다 · 멈춘다"]
    Q1 -->|"아니다"| Q2{"묘비인가"}
    Q2 -->|"묘비다 · 다음 후보 칸으로"| Q1
    Q2 -->|"아니다"| Q3{"찾는 키와 같나"}
    Q3 -->|"같다"| A2["찾았다 · 멈춘다"]
    Q3 -->|"다르다 · 다음 후보 칸으로"| Q1

묘비는 공짜가 아닙니다. 넣고 지우기를 오래 되풀이하면 묘비만 늘어납니다. 그러면 담긴 항목이 적어도 조회가 길어집니다. 이때는 표를 새로 잡고 살아 있는 항목만 다시 담습니다. 이 일이 리해싱입니다.

다음 칸을 고르는 세 규칙

앞에서는 한 칸씩 옆으로 가는 규칙만 썼습니다. 규칙을 바꾸면 훑는 칸이 흩어지는 모양이 달라집니다. 널리 쓰는 셋을 아래 표가 견줍니다. h 는 해시값이 정한 첫 칸 번호입니다. j 는 몇 번째 후보인지를 0부터 세는 수입니다.

첫 줄이 말하는 메모리 이점부터 풀어 두겠습니다. 메모리는 칸 하나씩 실어 오지 않습니다. 이웃한 여러 칸을 한 묶음으로 함께 실어 옵니다. 그래서 바로 옆 칸은 대개 이미 읽혀 있습니다. 이 이점이 캐시 지역성입니다.

여덟 칸짜리 표에서 첫 칸이 3번이면 밟는 칸도 규칙마다 다릅니다. 선형 탐사는 3·4·5·6 으로 붙어 갑니다. 이차 탐사는 3·4·7 로 튀었다가 다시 4번으로 돌아옵니다.

이중 해싱은 해시 함수를 둘 씁니다. 첫 함수 h₁ 이 첫 칸을 정합니다. 둘째 함수 h₂ 는 키마다 다른 걸음 폭을 냅니다.

이 걸음 폭은 0이 되면 안 됩니다. 폭이 0이면 같은 칸을 무한히 다시 보게 됩니다.

폭을 아무 수로나 잡아도 되는 것은 아닙니다. 칸이 여덟 개인 표에서 걸음 폭이 4면 3번 다음은 7번, 그다음은 다시 3번입니다. 칸 두 개만 오가고 나머지 여섯은 못 봅니다.

그래서 걸음 폭은 칸 수와 공약수가 없게 고릅니다. 칸 수를 소수로 잡는 구현이 많은 까닭입니다.

몰림(클러스터링)

선형 탐사에서는 찬 칸이 이어 붙어 한곳에 몰립니다. 이 몰림이 클러스터링입니다. 이 글에서는 그 뭉치를 「덩어리」라고 부르겠습니다.

덩어리가 문제인 까닭은 스스로 자라기 때문입니다. 덩어리 안 어느 칸으로든 떨어진 키는 덩어리 끝까지 훑은 뒤 그 뒤에 붙습니다. 그러면 덩어리가 한 칸 더 길어집니다. 길어진 덩어리는 더 많은 키를 받아들입니다.

세 단계로 끊어 보면 되먹임이 드러납니다.

flowchart TD
    subgraph S1["1 · 찬 칸 셋이 이어 붙는다"]
        A["3·4·5 번 칸이 차 있다"]
    end
    subgraph S2["2 · 덩어리로 떨어진 키는 끝까지 밀린다"]
        B["첫 칸이 3·4·5 중 하나면 6번에 붙는다"]
    end
    subgraph S3["3 · 덩어리가 네 칸이 된다"]
        C["이제 3·4·5·6 이 입구다 · 받을 키가 늘었다"]
    end
    S1 --> S2 --> S3
    S3 -.->|"같은 일이 되풀이된다"| S1

이차 탐사와 이중 해싱은 후보를 멀리 떨어뜨려 이 되먹임을 끊습니다. 대신 캐시 지역성의 이점을 내줍니다. 어느 쪽이 나은지는 표의 크기와 항목 수가 정합니다.

적재율과 복잡도

표에 담긴 항목 수를 칸 수로 나눈 값이 적재율입니다. 개방 주소법은 항목이 전부 표 안에 있으므로 적재율이 1을 넘을 수 없습니다. 칸이 다 차면 더 넣지 못합니다.

훑어야 하는 칸 수는 적재율이 1에 가까워질수록 가파르게 늘어납니다. 표에 없는 키를 찾을 때가 가장 오래 걸립니다. 빈 칸을 만날 때까지 멈출 수 없기 때문입니다. 후보 칸이 고르게 흩어진다고 볼 때 이때 훑는 칸 수는 평균 1 / (1 - 적재율) 쯤입니다.

값 넷만으로는 「가파르다」가 잘 안 보이므로 같은 식을 곡선으로도 그려 둡니다.

xychart-beta
    title "적재율이 오를수록 훑는 칸 수"
    x-axis "적재율" ["0.5", "0.6", "0.7", "0.8", "0.9", "0.95", "0.99"]
    y-axis "평균 훑는 칸 수" 0 --> 100
    line [2, 2.5, 3.3, 5, 10, 20, 100]

적재율 0.99 줄이 요점입니다. 칸을 거의 다 채우면 조회 하나가 수십, 수백 칸을 훑습니다. 그래서 구현은 적재율이 정해 둔 선을 넘는 순간 칸 수를 늘리고 모든 항목을 다시 담습니다.

적재율을 그 선 아래로 유지하면 넣기·찾기·지우기가 모두 평균 O(1) 입니다. 항목이 백만 개든 천 개든 훑는 칸 수가 몇 개로 일정하다는 뜻입니다.

평균이 그렇다는 것입니다. 가장 오래 걸리는 경우는 O(n) 입니다. 해시 함수가 키를 고르게 흩지 못해 모든 키가 한 줄로 몰리면 표를 끝까지 훑게 됩니다.

공간은 칸 배열 하나면 끝입니다. 항목마다 다음 항목을 가리키는 포인터를 붙일 일이 없어서, 같은 항목 수라면 분리 연쇄법보다 딸린 메모리가 적습니다.

분리 연쇄법과의 차이

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

메모리 읽기 줄이 개방 주소법을 고르는 가장 흔한 이유입니다. 선형 탐사가 다음에 볼 칸은 앞서 말한 그 묶음 안에 대개 이미 들어와 있습니다.

지우기 줄은 반대 방향입니다. 지우기가 잦은 표라면 묘비와 리해싱을 감당해야 합니다. 목록에서 빼면 끝나는 분리 연쇄법 쪽이 손이 덜 갑니다.

쓸 때와 안 쓸 때

아래 표는 하려는 일마다 개방 주소법이 맞는지를 가립니다.

항목 수를 못 가늠하는 경우가 개방 주소법의 가장 큰 제약입니다. 표가 넘칠 때 늘리는 일을 구현이 알아서 해 주지 않는 환경이라면, 칸 수를 잡는 일이 그대로 설계 부담이 됩니다.

관련 항목

다음 칸을 고르는 규칙

선형 탐사 · 이차 탐사 · 이중 해싱 · 균등 해싱 · 탐사 · 탐사 순서

이것을 비틀어 배치를 바꾼 기법

로빈 후드 해싱 · 뻐꾸기 해싱 · 홉스카치 해싱 · 선형 탐사 압축

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

분리 연쇄법 · 체이닝 · 외부 연쇄법 · 오버플로 영역

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

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

조회 길이를 좌우하는 지표

적재율 · 클러스터링 · 균등 분포 · 리해싱 · 캐시 지역성

지운 칸에 남기는 표시와 그 뒤처리

묘비 · 리빌드 · 단편화