해시테이블

해시테이블은 키를 주면 그 키에 묶인 값을 곧바로 꺼내 줍니다. 데이터가 아무리 많아도 처음부터 훑지 않습니다. 키를 숫자로 바꿔 값이 든 칸을 바로 계산해 내기 때문입니다. 대신 넣은 순서나 크기 순서는 지켜 주지 않습니다.

상세

이 절은 해시테이블이 키를 어떻게 칸 번호로 바꾸는지부터 봅니다. 그다음 두 키가 같은 칸으로 오는 충돌과 그 뒤처리, 칸이 모자랄 때 늘리는 방법을 봅니다. 예는 짧은 문자열 키 몇 개와 칸 8개짜리 작은 표 하나로 듭니다.

끝에서는 조회가 언제 빠르고 언제 느려지는지를 복잡도로 정리합니다. 그리고 어떤 일에 맞고 어떤 일에 안 맞는지를 견줍니다.

번호 붙은 사물함에 빗대면

사물함이 줄지어 있고 문마다 번호가 붙어 있다고 해 봅니다. 이름을 넣으면 사물함 번호를 알려 주는 계산표가 입구에 있습니다. 짐을 맡길 때도 찾을 때도 그 계산표로 번호를 얻어 그 문만 엽니다.

이 비유는 한 군데서 어긋납니다. 계산표가 서로 다른 두 이름에 같은 번호를 줄 수 있습니다. 그럴 때 어떻게 하는지가 아래 「충돌」 소절입니다.

키와 값

해시테이블이 담는 것은 키와 값의 짝입니다. 키는 찾을 때 대는 이름입니다. 값은 그 이름에 묶어 둔 데이터입니다. 아이디 "kim" 에 회원 정보를 묶어 두는 식입니다.

이렇게 키로 값을 넣고 찾는 기능을 추상적으로 부르는 이름이 맵입니다. 딕셔너리나 연관 배열이라고도 부릅니다. 해시테이블은 맵을 만드는 방법 가운데 하나입니다. 같은 기능을 이진 탐색 트리로도 만들 수 있습니다.

배열도 번호로 값을 곧바로 꺼냅니다. 하지만 배열의 번호는 0부터 이어지는 정수여야 합니다. 해시테이블은 문자열처럼 아무 키나 받아서 그 키를 배열 번호로 바꿔 줍니다. 배열의 빠른 꺼내기를 아무 키에나 쓰게 만든 것이라고 보면 됩니다.

버킷과 해시 함수

해시테이블 안에는 칸을 늘어놓은 배열이 하나 있습니다. 이 칸 하나를 버킷이라고 부릅니다. 짝은 어느 한 버킷에 들어갑니다.

키를 버킷 번호로 바꾸는 일은 해시 함수가 맡습니다. 앞의 비유에서 입구의 계산표에 해당합니다. 해시 함수는 어떤 데이터든 받아 정수 하나로 바꿔 주는 함수입니다. 이 정수를 해시값이라고 부릅니다.

해시 함수에는 지켜야 할 조건이 하나 있습니다. 같은 키를 넣으면 언제나 같은 해시값이 나와야 합니다. 그래야 넣을 때 고른 버킷과 찾을 때 고른 버킷이 같습니다.

해시값은 버킷 수보다 훨씬 클 수 있습니다. 그래서 해시값을 버킷 수로 나눈 나머지를 버킷 번호로 씁니다. 나머지는 늘 0부터 버킷 수보다 하나 작은 수 사이에 들어옵니다.

아래는 자바 문자열의 해시값으로 버킷 8개짜리 표의 번호를 구한 것입니다.

"ab".hashCode()      // 3105
"ab".hashCode() % 8  // 1
"ba".hashCode() % 8  // 7

"ab" 는 1번 버킷, "ba" 는 7번 버킷으로 갑니다. 글자가 같아도 순서가 다르면 해시값이 달라 다른 버킷으로 흩어집니다.

넣기와 찾기

넣기와 찾기는 앞 절반이 같습니다. 둘 다 키로 버킷 번호를 먼저 구합니다.

넣을 때는 그 버킷에 짝을 둡니다. 같은 키가 이미 있으면 값만 새것으로 바꿉니다. 찾을 때는 그 버킷을 열어 키가 같은 짝을 꺼냅니다. 없으면 「없다」고 답합니다.

아래 그림은 둘 가운데 찾기의 길을 그린 것입니다.

flowchart TD
    K["키"] --> H["해시 함수로 해시값을 구한다"]
    H --> M["버킷 수로 나눈 나머지를 구한다"]
    M --> B["그 번호의 버킷을 연다"]
    B --> C{"키가 같은 짝이 있나"}
    C -->|있다| V["값을 돌려준다"]
    C -->|없다| N["없다고 답한다"]

버킷을 연 뒤에도 키를 한 번 더 견줍니다. 다른 키가 같은 버킷에 와 있을 수 있어서입니다. 그 경우가 다음 소절의 충돌입니다.

충돌

서로 다른 두 키가 같은 버킷 번호를 받는 일을 충돌이라고 부릅니다. 자바 문자열 "Aa" 와 "BB" 는 해시값부터 같습니다.

"Aa".hashCode()      // 2112
"BB".hashCode()      // 2112
"BB".hashCode() % 8  // 0

두 키는 다르지만 둘 다 0번 버킷으로 갑니다. 해시값이 달라도 나머지가 같으면 역시 같은 버킷으로 갑니다.

충돌은 피할 수 없습니다. 키로 올 수 있는 문자열은 끝없이 많고 버킷 수는 정해져 있습니다. 칸보다 넣을 것이 많으면 어느 칸엔가 둘이 들어가게 됩니다. 이것을 비둘기집 원리라고 부릅니다.

그래서 해시테이블은 충돌을 없애려 하지 않습니다. 충돌이 나도 두 짝을 다 담아 두고 맞게 찾는 방법을 붙입니다. 이 방법을 충돌 해소라고 부릅니다. 대표적인 방법이 둘입니다.

분리 연쇄법

분리 연쇄법은 버킷마다 짝을 담는 목록을 하나씩 둡니다. 같은 버킷으로 온 짝은 그 목록 뒤에 이어 붙입니다. 목록으로는 흔히 연결 리스트를 씁니다.

아래 그림은 버킷 8개 가운데 셋만 그렸습니다. 0번에는 충돌한 두 짝이 줄지어 매달렸습니다. 1번과 7번에는 짝이 하나씩 있습니다.

flowchart TD
    subgraph 버킷배열["버킷 배열 · 8칸 중 셋"]
        B0["0번"]
        B1["1번"]
        B7["7번"]
    end
    B0 --> A["Aa · 값"] --> BB["BB · 값"]
    B1 --> AB["ab · 값"]
    B7 --> BA["ba · 값"]

"BB" 를 찾으면 0번 버킷의 목록을 앞에서부터 훑습니다. "Aa" 와 견줘 보니 달라서 넘어갑니다. 다음 짝이 "BB" 라서 그 값을 돌려줍니다. 목록이 짧으면 훑는 일도 금방 끝납니다.

지우기도 단순합니다. 목록에서 그 짝 하나를 빼면 됩니다. 대신 짝마다 목록 연결을 가리키는 포인터를 따로 들고 있어서 메모리를 더 씁니다.

개방 주소법

개방 주소법은 목록을 따로 두지 않습니다. 버킷 하나에 짝 하나만 담습니다. 가려던 버킷이 이미 차 있으면 정해진 규칙으로 다른 버킷을 차례로 들여다봅니다. 이렇게 빈 버킷을 찾아 나서는 일을 탐사라고 부릅니다.

가장 단순한 규칙은 선형 탐사입니다. 바로 옆 버킷으로 한 칸씩 가는 방법입니다. "BB" 를 넣을 때 0번에 "Aa" 가 있으면 1번을 봅니다. 1번에도 "ab" 가 있으면 2번을 봅니다. 2번은 비어 있어서 거기 넣습니다.

flowchart TD
    S["BB 를 넣는다 · 계산한 번호는 0번"] --> P0["0번 · Aa 가 있다"]
    P0 --> P1["1번 · ab 가 있다"]
    P1 --> P2["2번 · 비었다"]
    P2 --> D["2번에 BB 를 넣는다"]

찾을 때도 같은 길을 따라갑니다. 0번부터 옆으로 가며 키를 견주다 "BB" 를 만나면 멈춥니다. 빈 버킷을 만나면 그 키는 없는 것입니다.

지우기는 조심해야 합니다. 1번의 "ab" 를 그냥 비우면 나중에 "BB" 를 찾을 때 1번에서 멈춰 버립니다. 그래서 지운 버킷에는 「여기 있다가 지워졌다」는 표시를 남깁니다. 이 표시를 툼스톤이라고 부릅니다. 찾기는 툼스톤을 만나도 멈추지 않고 지나갑니다.

선형 탐사는 찬 버킷이 한 덩어리로 뭉치기 쉽습니다. 이 뭉침이 클러스터링입니다. 덩어리가 길어지면 그 안으로 온 키는 덩어리 끝까지 옆으로 가야 해서 탐사도 길어집니다.

뭉침을 줄이려면 한 칸씩 옆으로 가지 않고 더 멀리 뜁니다. 그렇게 뛰는 방법으로 이차 탐사와 이중 해싱이 있습니다. 어떻게 뛰는지는 각 항목에서 다룹니다.

두 방법의 차이를 나란히 놓으면 이렇습니다.

적재율

해시테이블이 얼마나 찼는지는 적재율로 잽니다. 적재율은 담긴 짝의 수를 버킷 수로 나눈 값입니다. 버킷 8개에 짝이 6개면 적재율은 0.75 입니다.

적재율이 조회 속도를 좌우합니다. 분리 연쇄법에서 적재율은 버킷 하나에 매달린 목록의 평균 길이와 같습니다. 개방 주소법에서는 적재율이 1에 가까울수록 빈 버킷이 드물어져 탐사가 길어집니다. 개방 주소법은 적재율이 1을 넘을 수 없습니다.

그래서 해시테이블은 적재율이 정해 둔 문턱을 넘지 않게 관리합니다. 문턱을 얼마로 잡을지는 구현마다 다릅니다.

리해싱

적재율이 문턱을 넘으면 버킷 배열을 더 크게 새로 만듭니다. 흔히 버킷 수를 두 배로 늘립니다. 그리고 기존 짝을 전부 새 배열로 옮깁니다. 이 작업을 리해싱이라고 부릅니다.

옮길 때 짝의 버킷 번호를 다시 계산해야 합니다. 번호는 해시값을 버킷 수로 나눈 나머지라서, 버킷 수가 바뀌면 나머지도 바뀔 수 있습니다.

"ab".hashCode() % 16  // 1
"ba".hashCode() % 16  // 15

버킷이 8개일 때 1번과 7번이던 두 키입니다. 16개가 되자 "ab" 는 1번에 남았습니다. "ba" 는 15번으로 옮겨 갔습니다. 어느 키가 움직일지는 계산해 보기 전에는 모르니 전부 다시 계산합니다.

리해싱 한 번은 짝 수만큼 시간이 듭니다. 그 순간의 넣기 하나가 유독 오래 걸립니다. 대신 배열을 두 배씩 키우면 리해싱은 점점 드물게 일어납니다.

셈을 쉽게 하려고 짝이 버킷 수만큼 차면 두 배로 늘린다고 해 봅니다. 버킷 8개가 차서 16개로 늘리면 짝 8개를 옮깁니다. 다음 리해싱은 짝이 16개가 될 때라서 그 사이에 넣기가 8번 있습니다. 옮긴 8개를 그 8번에 하나씩 얹으면 넣기 한 번에 옮기기 한 번꼴입니다.

버킷이 16개에서 32개로 갈 때도 셈은 같습니다. 그래서 넣기 한 번에 드는 평균은 일정한 시간으로 남습니다. 드문 큰 비용을 여러 번에 나눠 세는 이 방식을 분할 상환 분석이라고 부릅니다.

응답 시간이 고르게 짧아야 하는 서비스라면 이 한 번이 문제가 될 수 있습니다. 넣을 개수를 미리 알면 처음부터 버킷을 넉넉히 잡아 리해싱을 피합니다.

복잡도

자료구조가 얼마나 빠른지는 빅오 표기법으로 적습니다. O(1) 은 데이터가 늘어도 걸리는 시간이 거의 그대로라는 뜻입니다. O(n) 은 데이터 수 n 에 비례해 시간이 는다는 뜻입니다.

평균이 O(1) 인 까닭은 적재율을 문턱 아래로 묶어 두기 때문입니다. 한 버킷에서 견줄 짝의 수가 평균적으로 일정하게 남습니다.

최악이 O(n) 인 까닭은 모든 키가 한 버킷으로 몰릴 수 있어서입니다. 그러면 분리 연쇄법은 목록 하나를 끝까지 훑습니다. 개방 주소법은 찬 버킷을 줄줄이 지나갑니다. 해시 함수가 키를 고르게 흩지 못할 때 이 일이 생깁니다.

O(1) 은 해시값을 구하는 시간을 일정하다고 치고 센 값입니다. 키가 긴 문자열이면 해시값을 구하느라 그 길이만큼 시간이 듭니다.

일부러 한 버킷으로 몰 때

최악은 우연으로만 생기지 않습니다. 해시 함수가 알려져 있으면 같은 버킷으로 가는 키를 미리 잔뜩 만들 수 있습니다. 앞의 "Aa" 와 "BB" 는 해시값이 같았습니다. 자바 문자열은 이 둘을 이어 붙인 조합끼리도 해시값이 같습니다.

"AaAa".hashCode()  // 2031744
"AaBB".hashCode()  // 2031744
"BBAa".hashCode()  // 2031744
"BBBB".hashCode()  // 2031744

두 조각으로 네 글자짜리 키 네 개가 나왔습니다. 조각을 하나 더 이으면 여덟 개, 또 이으면 열여섯 개가 됩니다. 같은 해시값을 내는 키를 이렇게 얼마든지 늘릴 수 있습니다.

공격자가 그런 키만 골라 요청 매개변수나 JSON(JavaScript Object Notation) 필드 이름으로 보내면 서버의 해시테이블이 목록 하나로 무너집니다. 요청 하나를 처리하는 데 CPU(Central Processing Unit, 중앙 처리 장치)가 오래 묶입니다. 이런 공격을 해시 플러딩이라고 부릅니다.

막는 방법은 공격자가 해시값을 미리 계산하지 못하게 하는 것입니다. 프로그램을 띄울 때마다 임의 값을 뽑아 해시 계산에 섞는 방식이 쓰입니다. 이 임의 값을 해시 시드라고 부릅니다.

키가 지켜야 할 약속

해시테이블은 키 두 개가 「같다」고 판정되면 해시값도 같다고 믿고 돕니다. 이 믿음이 깨지면 넣은 짝을 못 찾습니다. 같은 키인데 해시값이 달라 다른 버킷을 열기 때문입니다.

그래서 키로 쓸 타입은 두 계산을 맞춰야 합니다. 자바라면 같음을 판정하는 equals 와 해시값을 내는 hashCode 두 메서드입니다. equals 가 같다고 답하는 두 객체는 반드시 같은 hashCode 를 내야 합니다.

equals 만 고쳐 쓰고 hashCode 를 그대로 두면 이 약속이 깨집니다. 내용이 같은 키로 넣은 짝을 다른 버킷에서 찾게 되어 못 찾습니다. 거꾸로 해시값이 같다고 같은 객체일 필요는 없습니다. 그건 충돌일 뿐입니다.

넣은 뒤에 키를 고치는 것도 같은 문제를 낳습니다. 키의 내용이 바뀌면 해시값이 바뀝니다. 짝은 옛 해시값의 버킷에 남아 있는데 찾기는 새 해시값의 버킷을 엽니다. 그래서 키로는 한번 만들면 안 바뀌는 불변 객체를 씁니다.

순서가 없다

해시테이블을 처음부터 훑으면 짝이 버킷 번호 순서로 나옵니다. 버킷 번호는 해시값의 나머지라서 키의 크기나 넣은 순서와 무관합니다. 그래서 키의 크기로 보나 넣은 순서로 보나 뒤섞여 나옵니다.

리해싱이 일어나면 그 순서마저 바뀔 수 있습니다. 훑는 순서에 기대는 코드는 데이터가 늘어나면 다르게 돕니다.

순서가 필요한 질문에는 약합니다. 「가장 작은 키」를 찾으려면 버킷을 전부 봐야 합니다. 「kim 부터 lee 까지」 같은 범위 조회도 마찬가지입니다. 이런 질문이 잦으면 키를 정렬된 채로 두는 B-tree나 레드-블랙 트리 같은 트리를 씁니다.

쓸 때와 안 쓸 때

맞는 쓰임과 안 맞는 쓰임을 함께 놓아 봅니다.

해시테이블은 일상적으로 쓰는 언어마다 기본으로 들어 있습니다. 자바의 HashMap, 파이썬의 dict, Go 의 map 이 이 자료구조입니다.

관련 항목

해시테이블을 이루는 구성 요소

버킷 · 해시 함수 · 해시값 · 키-값 쌍 · 적재율 · 툼스톤 · 해시 시드

해시테이블이 충돌을 뒤처리하는 방법

충돌 해소 · 분리 연쇄법 · 개방 주소법 · 선형 탐사 · 이차 탐사 · 이중 해싱 · 로빈 후드 해싱 · 뻐꾸기 해싱 · 클러스터링

해시테이블의 크기와 속도를 따지는 개념

리해싱 · 분할 상환 분석 · 빅오 표기법 · 비둘기집 원리 · 생일 문제 · 균등 분포 · 해시 충돌

해시테이블로 구현하는 추상 자료형

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

해시테이블과 같은 역할을 두고 겨루는 자료구조

이진 탐색 트리 · 레드-블랙 트리 · B-tree · 트라이 · 스킵 리스트 · 배열 · 연결 리스트

해시테이블 위에 얹히는 기법과 쓰임

캐시 · 메모이제이션 · 해시 인덱스 · 해시 조인 · 블룸 필터 · 일관성 해싱 · 분산 해시 테이블 · 완전 해싱

해시테이블을 노리는 공격과 그 방어

해시 플러딩 · 서비스 거부 공격 · SipHash · 불변 객체

해시테이블이 속하는 상위 분류

자료구조 · 알고리즘 · 해싱