제7장 · 해시 테이블로 초고속 검색

§ 1 · 빠른 읽기해시 테이블 등장

패스트푸드 메뉴의 가격을 배열로 저장하면, 정렬되지 않은 경우 조회에 O(N), 정렬된 경우 O(log N)이 든다. 해시 테이블(hash table)은 이를 O(1)로 끌어내린다.

해시 테이블은 언어마다 다른 이름으로 불린다 — 해시(hash), 맵(map), 해시 맵, 딕셔너리(dictionary), 연관 배열(associative array). 모두 같은 자료구조다.

해시 테이블로 구현한 메뉴 — Ruby

menu = { "french fries" => 0.75, "hamburger" => 2.5,
         "hot dog" => 1.5, "soda" => 0.6 }

menu["french fries"]   # => 0.75 — 단 한 단계

해시 테이블은 쌍을 이루는 값의 목록이다. 첫 항목은 키(key), 두 번째는 값(value). 키 "french fries"와 값 0.75가 짝을 이뤄 "감자튀김은 75센트"를 나타낸다.

§ 2 · 문자를 숫자로해시 함수로 해싱

어릴 적 비밀 코드를 떠올려 보자. A=1, B=2, C=3, D=4 …. 문자를 숫자로 바꾸는 이 과정이 해싱(hashing)이고, 변환에 쓰는 코드가 해시 함수(hash function)다.

이 책에서는 "곱셈" 해시 함수를 쓴다 — 각 문자의 숫자를 모두 곱한다.

곱셈 해시 함수

BAD → 2 × 1 × 4 = 8

해시 함수의 유일한 기준 — 같은 문자열은 적용할 때마다 항상 같은 숫자로 변환해야 한다. 난수나 현재 시각을 쓰는 함수는 일관성이 없어 무효다.

모션 · 키가 해싱되어 버킷에 들어간다 단계 01 / 0

space 재생 · → 단계 · R 리셋

핵심 해시 테이블 조회가 O(1)인 이유 — 컴퓨터는 ① 조회하는 키를 해싱하고 ② 그 결과 셀로 바로 점프해 ③ 값을 읽는다. 단계 수가 일정하다.

§ 3 · 같은 칸의 충돌충돌 처리

"bad"는 2×1×4=8, "dab"도 4×1×2=8로 해싱된다. 이미 채워진 셀에 데이터를 넣으려는 것을 충돌(collision)이라 한다.

고전적 해결책은 분리 연쇄법(separate chaining)이다. 충돌이 나면 셀에 단일 값 대신 배열에 대한 참조를 둔다. 그 배열에는 [키, 값] 하위 배열들이 담긴다.

모션 · 충돌과 분리 연쇄법 단계 01 / 0

space 재생 · → 단계 · R 리셋

함정 충돌이 잦으면 컴퓨터는 셀 안의 배열을 선형 검색해야 한다. 모든 데이터가 한 셀에 몰리면 해시 테이블은 배열보다 나을 게 없다 — 최악의 경우 조회는 O(N)이다.

§ 4 · 로드 팩터위대한 균형 행위

해시 테이블의 효율성은 세 요인에 달렸다 — ① 저장하는 데이터의 양, ② 사용 가능한 셀의 수, ③ 해시 함수. 좋은 해시 함수는 데이터를 모든 셀에 고르게 분산시킨다.

셀이 너무 적으면 충돌이 잦고, 너무 많으면 메모리 낭비다. 컴퓨터 과학자들의 경험 법칙은 — 데이터 7개당 셀 10개.

로드 팩터 — Load Factor

7 개 요소 ÷ 10 개 셀 = 0.7

데이터 대 셀의 비율을 로드 팩터(load factor)라 한다. 이상적인 값은 0.7. 데이터가 늘면 컴퓨터가 셀을 추가하고 해시 함수를 바꿔 다시 고르게 분산시킨다.

다행히 해시 테이블 크기, 해시 함수, 확장 시점은 대부분 언어가 알아서 관리한다. 우리는 그저 해시 테이블의 O(1) 조회를 누리면 된다.

§ 5 · 추적과 집계실용적인 예

해시 테이블은 어떤 값이 존재하는지 추적하고 싶은 모든 상황에 완벽하다. 4장의 중복 검사를 떠올려 보자. 두 번째 구현(보조 배열)은 양의 정수만 다뤘다. 해시 테이블을 쓰면 문자열도 처리하면서 여전히 O(N)이다.

전자 투표 — 집계도 O(1)로 — JavaScript

var votes = {};

function addVote(candidate) {
    if(votes[candidate]) {
        votes[candidate]++;
    } else {
        votes[candidate] = 1;
    }
}

function countVotes() {
    return votes;   // 집계가 진행 중이라 O(1)
}

투표를 배열에 쌓으면 마지막 집계가 O(N)으로 오래 걸린다. 처음부터 해시 테이블에 후보별 카운트를 저장하면, 삽입도 O(1)이고 집계는 이미 끝나 있어 O(1)이다.

§ 6 · 정리이 장이 남긴 것

해시 테이블은 효율적인 소프트웨어의 필수 도구다. O(1) 읽기와 삽입으로 이기기 어려운 자료구조다. 그러나 모든 자료구조가 속도만으로 평가되는 것은 아니다. 다음 장에서는 코드의 우아함을 높이는 자료구조를 만난다.

관련중복 검사의 두 구현 관련해시 테이블로 그래프 구현