해시 테이블: 이름으로 자리를 바로 찾기

사물함 열쇠에 번호가 적혀 있으면 사물함을 처음부터 하나씩 열어 보지 않습니다. 해시 테이블은 키(이름)를 숫자로 바꿔, 그 숫자로 자리를 바로 계산합니다. 낱말 하나가 숫자가 되고, 칸 번호가 되고, 칸에 들어가는 것을 한 걸음씩 따라가 보세요.

한 줄 답. 해시 테이블은 키를 숫자로 바꿔(해시 함수) 그 숫자로 자리를 바로 정하는 표입니다. 넣을 때와 찾을 때 같은 계산을 하므로 표 전체를 훑지 않고 칸 하나만 봅니다. 그래서 보통은 한두 번 비교하면 찾지만, 여러 키가 한 칸에 몰리면(충돌) 느려지고 최악의 경우는 n 개를 모두 비교합니다. Python 의 dict 와 set 이 키의 해시 값으로 자리를 찾습니다.

    「다음」을 누르면 한 걸음씩 나아갑니다. 위 회색 칸에 낱말과 그 걸음의 계산이, 아래에 무엇을 보고 무엇을 왜 했는지가 나옵니다. 화살표는 그 걸음에 한 일 하나만 가리킵니다. 파란 화살표는 낱말 → 해시 값, 계산 → 칸, 주황 화살표와 「≠」는 지금 비교하는 낱말, 초록 화살표는 새로 넣은 낱말과 찾은 낱말, 검은 화살표는 줄 끝(없음)입니다. 파란 테두리는 지금 보는 칸, 「이미 있음」은 넣으려는 칸에 먼저 와 있던 낱말입니다. 낱말 칸에 a ~ z 로 1 ~ 8 글자를 적고 「넣기」나 「찾기」를 누르면 그 일의 걸음이 끝에 붙습니다. 지어낸 낱말 mok, zel, rua, tib, pim, har, nul, vio, kesa, dop 을 써 보세요.

    해 볼 것. ① 「다음」을 24 번 누르면 낱말 여섯을 넣고 tib 를 찾습니다. 칸 4 에서 mok 과 비교하고, 다음 tib 에서 찾아 비교한 횟수가 2 번입니다. ② 낱말 칸의 nul 로 「찾기」를 누르면 해시 값 92, 칸 4 입니다. mok, tib 와 비교하고 줄이 끝나 「없다」로 끝납니다. 다른 칸은 보지 않습니다. ③ kesa 와 dop 을 차례로 넣어 보세요. 글자가 전혀 다른데 해시 값이 둘 다 82 라서 칸 2 에 줄줄이 매달립니다. ④ mok 을 한 번 더 넣으면 칸 4 에서 같은 낱말을 찾아 넣지 않습니다.

    1. 해시 테이블이란: 키를 숫자로 바꿔 자리를 정한다

    배열은 번호(0, 1, 2 …)로 칸을 바로 엽니다. 7 번 칸을 열려고 0 번부터 훑지 않습니다. 그런데 우리가 가진 것은 번호가 아니라 이름(키)일 때가 많습니다. 사용자 아이디, 낱말, 상품 코드 같은 것입니다. 해시 테이블은 이름을 번호로 바꾸는 계산을 하나 정해 두고, 그 번호의 칸(버킷, bucket)에 넣습니다. 찾을 때도 같은 계산을 하면 같은 칸이 나오니, 그 칸만 보면 됩니다.

    이름을 숫자로 바꾸는 계산이 해시 함수, 나온 숫자가 해시 값입니다. 해시 값은 클 수 있으니 칸 수로 나눈 나머지를 칸 번호로 씁니다. 나머지는 늘 0 ~ (칸 수 − 1) 이라 있는 칸에 떨어집니다. 이 쪽의 장난감 해시 함수는 이렇습니다.

    해시 값 = (첫 글자 번호 × 1) + (둘째 글자 번호 × 2) + (셋째 글자 번호 × 3) + …   (a = 1, b = 2, … z = 26)
    칸 번호 = 해시 값 ÷ 칸 수 의 나머지                                             (해시 값 % 칸 수)
    
    넣기: 칸 번호를 구한다 → 그 칸의 줄에 같은 키가 있나 비교한다 → 없으면 줄 끝에 매단다
    찾기: 칸 번호를 구한다 → 그 칸의 줄을 앞에서부터 비교한다 → 같으면 찾음, 줄이 끝나면 없음

    자리 번호를 곱하는 까닭은 글자 순서를 섞기 위해서입니다. 그냥 더하기만 하면 mok 과 kom 이 같은 값이 됩니다(자리를 곱하면 76 과 80). 실제로 쓰는 해시 함수도 글자의 자리를 섞습니다. 예를 들어 앞까지의 값에 31 같은 작은 소수를 곱하고 다음 글자를 더해 가는 방식이 있습니다(출처의 algs4 3.4절). 이 쪽의 함수는 손으로 따라가기 쉽게 만든 것이라 고르게 흩어 주는 힘이 약합니다.

    2. 손으로 따라가기

    칸 8 개짜리 빈 표에 지어낸 낱말 여섯을 차례로 넣고, tib 를 찾습니다. 실험의 처음 차례와 같습니다.

    넣는 낱말글자 번호 × 자리해시 값÷ 8 의 나머지 = 칸넣은 뒤 그 칸의 줄(까닭)
    mok13×1 + 15×2 + 11×3764mok (칸이 비어 그대로)
    zel26×1 + 5×2 + 12×3720zel (칸이 비어 그대로)
    rua18×1 + 21×2 + 1×3637rua (칸이 비어 그대로)
    tib20×1 + 9×2 + 2×3444 (충돌)mok → tib (mok ≠ tib 라 줄 끝에)
    pim16×1 + 9×2 + 13×3731pim (칸이 비어 그대로)
    har8×1 + 1×2 + 18×3640 (충돌)zel → har (zel ≠ har 라 줄 끝에)
    1. 76 ÷ 8 = 9 … 나머지 4. mok 은 칸 4 에 들어갑니다. 해시 값이 72, 63 인 zel, rua 는 칸 0, 칸 7 로 갑니다.
    2. tib 의 해시 값은 44, 44 ÷ 8 = 5 … 나머지 4. 칸 4 에는 이미 mok 이 있습니다. 서로 다른 키가 같은 칸에 떨어지는 것을 충돌이라고 합니다. mok 과 비교해 같은 낱말이 아닌 것을 보고, mok 뒤에 tib 를 매답니다.
    3. har 의 64 ÷ 8 = 8 … 나머지 0. 칸 0 의 zel 뒤에 매달립니다.
    4. tib 찾기. 다시 44, 나머지 4 를 계산해 칸 4 로 갑니다. 줄의 첫째 mok 과 비교하면 다르고, 둘째 tib 와 비교하면 같습니다. 비교 횟수 2 번. 다른 일곱 칸은 보지 않았습니다.

    끝난 표: 칸 0 은 zel → har, 칸 1 은 pim, 칸 4 는 mok → tib, 칸 7 은 rua, 나머지 네 칸은 비었습니다. 넣은 여섯 낱말을 하나씩 찾으면 비교하는 횟수가 1, 2, 1, 1, 1, 2 번이라 평균 8 ÷ 6 ≈ 1.33 번입니다.

    3. 충돌: 체이닝과 선형 탐사

    칸보다 키가 많으면 충돌은 반드시 납니다. 칸 수보다 적어도 우연히 겹칩니다(손 예제는 여섯 개를 넣었는데 두 번 겹쳤습니다). 그래서 해시 테이블은 충돌을 처리하는 규칙을 꼭 가집니다. 많이 쓰는 방법은 둘입니다.

    방법넣을 때찾을 때적재율(load factor, 키 수 ÷ 칸 수)
    체이닝(separate chaining, 이 쪽의 실험)칸마다 줄(목록)을 두고, 같은 칸에 온 키를 그 줄에 매단다그 칸의 줄을 앞에서부터 비교한다1 을 넘어도 된다. 칸 하나에 평균 몇 개가 매달렸는지가 된다
    선형 탐사(linear probing)칸이 차 있으면 다음 칸, 그다음 칸 … 빈칸이 나올 때까지 옆으로 가서 넣는다같은 칸에서 출발해 옆으로 가며 비교한다. 빈칸을 만나면 없는 것칸 하나에 키 하나라 늘 1 보다 작아야 한다
    체이닝(이 쪽의 실험) tib: 44 % 8 = 4 ① 이미 있음 칸 4 mok tib ② 줄 끝에 매단다 선형 탐사 tib: 44 % 8 = 4 ① 이미 있음 ② 옆 칸 5 가 비어 있어 넣는다 mok tib 칸 3 칸 4 칸 5 칸 6
    충돌이 났을 때 두 방법. tib 의 칸은 44 % 8 = 4 인데 칸 4 에는 mok 이 먼저 와 있습니다(손 예제). 체이닝은 mok 뒤에 tib 를 매달고, 선형 탐사는 다음 칸 5 가 비어 있어 거기에 넣습니다.

    선형 탐사는 줄을 따로 두지 않아 메모리가 단순하지만, 차 있는 칸이 이어져 덩어리가 생기면 느려지고, 지울 때 그냥 빈칸을 만들면 그 뒤로 밀려난 키를 못 찾게 되어 손이 더 갑니다. 이 쪽은 체이닝만 실험으로 봅니다.

    4. 적재율과 재해싱

    체이닝에서 적재율은 넣은 키 수 n ÷ 칸 수 m 입니다. 줄 길이를 모두 더하면 n 이니, 적재율이 곧 줄 길이의 평균입니다. 키가 칸에 고르게 흩어지면 찾을 때 비교하는 수도 이 평균에 비례합니다(algs4 의 Property L). 그래서 키가 늘어 적재율이 오르면 느려집니다.

    해결은 칸을 늘리고 모두 다시 넣는 재해싱(rehashing)입니다. 칸 수가 바뀌면 해시 값 % 칸 수 도 바뀌므로, 줄을 그대로 옮길 수 없고 키마다 칸 번호를 다시 계산해야 합니다. 재해싱 한 번은 n 개를 모두 옮기는 큰일이지만, 칸을 두 배로 늘리면 다음 늘리기까지 그만큼 많이 넣을 수 있어서, 넣기 한 번에 돌아가는 몫은 평균하면 일정합니다(분할 상환, amortized).

    칸 8 개 칸 0 의 줄 zel har 72 % 16 = 8 64 % 16 = 0 칸 16 개 zel har 칸 8 칸 0
    재해싱은 키마다 칸을 다시 계산합니다. 칸 8 개일 때 칸 0 에 같이 매달렸던 zel 과 har 가, 칸 16 개에서는 72 % 16 = 8, 64 % 16 = 0 이라 칸 8 과 칸 0 으로 갈라집니다. 그래서 줄을 통째로 옮길 수 없습니다.

    낱말은 고정 씨앗 난수기로 지어낸 3 ~ 5 글자 48 개이고, 막대나 숫자 칸으로 앞에서부터 몇 개를 넣을지 고릅니다. 해시 함수는 실험 ① 과 같습니다. 세로 눈금은 늘 0 ~ 9 로 고정이라 칸을 늘렸을 때 막대가 줄어드는 것을 그대로 비교할 수 있습니다.

    해 볼 것. ① 처음은 낱말 24 개, 칸 8 개입니다. 적재율 3, 가장 긴 줄 6, 있는 낱말을 찾는 데 평균 2.33 번 비교합니다. ② 「칸 수 두 배로」를 한 번 누르면 칸 16, 적재율 1.5, 가장 긴 줄 5, 평균 1.88 번. 두 번이면 칸 32, 0.75, 가장 긴 줄 3, 평균 1.5 번. 세 번이면 칸 64, 0.38, 가장 긴 줄 3, 평균 1.33 번입니다. 평균이 1 에 다가가지만, 64 칸 가운데 47 칸이 비어 메모리를 그만큼 씁니다. ③ 「8칸으로」 돌아가 낱말을 48 개로 늘리면 적재율 6, 가장 긴 줄 9, 평균 3.81 번입니다.

    5. 꼭 알아야 할 성질

    성질쉬운 말실험에서
    보통은 칸 하나만 본다키가 고르게 흩어지고 적재율이 낮으면 n 이 커져도 비교하는 수가 거의 늘지 않는다(O(1), 「n 이 두 배여도 그대로」). 해시 값을 내는 데는 키의 길이만큼 든다② 에서 칸 64 의 평균 1.33 번
    최악의 경우는 n 번모든 키가 한 칸에 몰리면 줄 하나에 n 개가 매달려, 리스트를 앞에서부터 훑는 것과 같다(O(n), 「n 이 두 배면 두 배」). 해시 함수가 약하거나 누가 일부러 같은 칸에 떨어지는 키만 넣으면 생긴다③ 의 kesa 와 dop
    적재율이 오르면 느려진다줄 길이의 평균이 곧 적재율이다. 칸을 늘려 다시 넣으면 다시 빨라진다「칸 수 두 배로」
    순서가 없다자리는 해시 값이 정한다. 키의 크기 차례와 상관없이 흩어진다mok 은 칸 4, zel 은 칸 0
    키는 바뀌지 않는 값이어야 한다넣은 뒤 키가 바뀌면 해시 값이 바뀌어 다른 칸을 보게 된다아래 「키는 바뀌지 않는 값」

    순서가 없다

    칸 번호는 해시 값의 나머지라 키의 크기와 상관이 없습니다. 그래서 「가장 작은 키」나 「b 로 시작하는 키 모두」, 「100 과 200 사이의 키」를 찾으려면 표 전체를 훑어야 합니다. 이런 일이 잦으면 순서를 지키는 정렬된 배열과 이분 탐색이나 이진 탐색 트리를 씁니다. Python 의 dict 는 순서를 기억하지만 넣은 차례입니다(자주 묻는 것 3).

    키는 바뀌지 않는 값이어야 한다

    mok 을 칸 4 에 넣은 뒤 키를 몰래 mox 로 바꿨다고 합시다. mox 를 찾으면 해시 값이 달라 다른 칸으로 가고, 칸 4 에 분명히 있는데 못 찾습니다. 그래서 Python 은 list 나 dict 처럼 넣은 뒤에 내용이 바뀔 수 있는 값을 dict 의 키나 set 의 원소로 받지 않습니다. 여러 값을 묶어 키로 쓸 때는 바뀌지 않는 tuple 을 씁니다({(3, 5): "길"}).

    6. 언제 무엇을 쓰나

    「키로 하나 찾기」를 하는 네 가지 방법입니다. n 은 들어 있는 키의 수입니다.

    방법찾기: 최선 · 평균 · 최악넣기(평균)순서대로 보기 · 범위 찾기더 드는 메모리쓰는 경우
    정렬 안 된 리스트를 앞에서부터(x in list)1 · n · n
    (n 이 두 배면 두 배, O(n))
    끝에 붙이기 1안 됨(정렬해야)없음몇 개 안 될 때, 쌓기만 하고 거의 안 찾을 때
    정렬된 배열 + 이분 탐색1 · log n · log n
    (n 이 두 배면 한 번 더, O(log n))
    n(뒤를 한 칸씩 밀어야)된다없음한 번 만들어 두고 자주 찾을 때, 범위 찾기
    이진 탐색 트리1 · log n · n
    (한쪽으로 치우치면 n)
    log n된다키마다 자식을 가리키는 칸 둘넣고 빼면서 순서도 필요할 때(치우치지 않게 하려면 레드-블랙 트리)
    해시 테이블(dict, set)1 · 1 · n
    (보통은 n 과 상관없이 몇 번, O(1))
    1(가끔 재해싱, 평균하면 일정)안 됨빈칸, 줄을 잇는 칸키로 바로 찾기, 중복 거르기, 개수 세기

    빅오 표기는 시간 복잡도 쪽에서 봅니다. 해시 테이블의 「평균 1」은 해시 함수가 키를 고르게 흩어 준다는 가정 위의 말입니다(출처의 Python 위키도 같은 가정을 적습니다).

    7. Python 으로

    체이닝을 그대로 옮기면 이렇습니다. 칸을 늘려 다시 넣는 부분은 줄이려고 뺐습니다. hash() 는 Python 이 주는 해시 함수입니다.

    class ChainedTable:
        def __init__(self, size=8):
            self.buckets = [[] for _ in range(size)]      # 칸마다 [키, 값] 의 줄
        def put(self, key, value):
            chain = self.buckets[hash(key) % len(self.buckets)]
            for pair in chain:
                if pair[0] == key:                          # 같은 키: 값만 바꾼다
                    pair[1] = value
                    return
            chain.append([key, value])                      # 없으면 줄 끝에 매단다
        def get(self, key):
            for k, v in self.buckets[hash(key) % len(self.buckets)]:
                if k == key:
                    return v
            raise KeyError(key)

    실제로는 표준의 dict 와 set 을 씁니다.

    ages = {"mok": 3, "tib": 5}     # dict: 키 → 값
    ages["tib"]                     # 5
    "zel" in {"mok", "tib"}         # set: 있나 없나. False

    어디에 쓰나

    자주 묻는 것

    있는지 없는지 볼 때 왜 list 대신 set 을 쓰나요?

    list 는 앞에서부터 하나씩 비교해서 n 개면 n 번까지 봅니다. set 은 키의 해시 값으로 칸을 바로 계산해 그 칸의 짧은 줄만 봅니다. 그래서 보통은 n 이 커져도 비교하는 수가 거의 늘지 않습니다. 다만 키가 한 칸에 몰리는 나쁜 경우에는 set 도 n 번까지 봅니다.

    dict 의 키로 list 를 쓸 수 없는 까닭은 무엇인가요?

    list 는 넣은 뒤에도 내용이 바뀔 수 있습니다. 내용이 바뀌면 해시 값이 바뀌고, 찾을 때 다른 칸을 보게 되어 분명히 넣은 키를 못 찾습니다. 그래서 Python 은 list, dict 처럼 바뀌는 값을 키로 받지 않습니다. 여러 값을 묶어 키로 쓰려면 바뀌지 않는 tuple 을 씁니다.

    Python 의 dict 는 순서를 기억하지 않나요?

    기억합니다. 다만 넣은 차례이지 크기 차례가 아닙니다. Python 3.7 부터 dict 는 넣은 차례대로 돈다고 문서에 정해져 있습니다. 키를 크기 차례로 보거나 「a 와 c 사이의 키」 같은 범위를 찾으려면 따로 정렬해야 합니다. set 은 순서가 없는 모음이라고 문서에 적혀 있습니다.

    낱말

    여기서 쓴 말책에서 부르는 말
    키를 숫자로 바꿔 자리를 정하는 표해시 테이블(hash table), 해시 맵. 키와 값의 짝을 담으면 심볼 테이블(symbol table), 매핑(mapping)
    이름을 숫자로 바꾸는 계산, 나온 숫자해시 함수(hash function), 해시 값·해시 코드(hash value, hash code)
    칸버킷(bucket), 슬롯(slot)
    칸 수로 나눈 나머지로 자리 정하기나머지 해싱(modular hashing)
    다른 키가 같은 칸에 떨어짐충돌(collision)
    줄줄이 매달기분리 연결법, 체이닝(separate chaining)
    옆 빈칸 찾기개방 주소법(open addressing), 선형 탐사(linear probing)
    찬 비율적재율, 부하율(load factor, α)
    칸을 늘려 모두 다시 넣기재해싱(rehashing), 크기 조정(resizing)
    가끔 큰일이 있어도 평균하면 일정분할 상환(amortized)
    바뀌지 않는 값, 해시 값을 낼 수 있는 값불변(immutable), 해시 가능(hashable)

    출처

    ← 이진 탐색이진 탐색 트리 →