해시 테이블
지난 글: [알고리즘] - 큐
해시 테이블(hash table)은 데이터 구조의 하나이며, 데이터 검색을 효율적으로 하기 위해 사용되는 구조이다.
1
해시 테이블은 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장한다. 예로 각 사람의 성별을 데이터로 저장하고 있으며, 이름을 키로, 성별을 값으로 저장하고 있다. 일반적으로 키는 데이터 식별자, 값은 데이터의 내용이라고 생각하면 된다.
2
해시 테이블의 특징을 비교하기 위해 먼저 데이터를 '배열'에 저장하는 경우를 생각해보자.
3
6개의 상자로 이루어진 배열을 준비하고 데이터를 저장한다(상자 번호는 내림차순). 여기서 상자에 저장된 Ally의 성별이 알고 싶다. 하지만 나는 Ally가 배열의 몇 번째 상자에 저장돼 있는지 모른다. 그러므로 앞에서부터 차례대로 확인한다. 이 처리를 '선형 탐색'이라 한다.
4
0번 상자에 저장된 데이터의 키는 'Joe'이다.
5
1번 상자에 저장된 키는 'Sue'다.
6
2번 상자는 'Dan', 3번 상자는 'Nell'이라는 키가 저장돼 있다.
7
4번 상자에 저장된 데이터 키가 'Ally'와 일치한다. 대응되는 값을 꺼내면 Ally(F)의 성별을 알 수 있다.
8
이처럼 선형 탐색은 데이터양에 비례해 계산 시간이 늘어난다. 배여 탐색에 시간이 걸리므로 탐색에는 적합하지 않은 구조라는 것을 알 수 있다.
9
이 문제를 해결해 주는 것이 해시 테이블이다. 먼저, 데이터를 저장하기 위한 배열을 준비한다. 여기에서는 5개의 상자로 구성된 배열을 만든다.
10
Joe(M)의 데이터를 추가하는 경우 '해시 함수'를 이용해서 Joe의 키(즉, 문자열 'Joe')에 해당하는 해시 값을 계산한다. 여기서는 4928이라는 결과가 나온다.
11
구한 해시값을 배열의 상자 수인 5로 나누어 나머지를 구한다. 나눗셈의 나머지를 구하는 연산을 'mod 연산'이라 한다. mod 연산 결과 3이라는 숫자가 나온다. 4928 mod 5 = 3
12
구한 수와 같은 배열의 3번 상자에 Joe의 데이터를 저장한다. 이 처리를 반복해 다른 데이터도 하나씩 채운다.
13
Sue(F)의 해시값은 7291이다. 5로 mod 연산을 하면 1이 나오므로 1번 상자에 Sue의 데이터를 저장한다.
14
Dan(M)의 해시값은 1539, Nell(F)의 해시값은 6276으로 각각 5로 mod 연산한 결과 4, 1 상자에 저장한다. 근데 1번 상자에는 Sue의 데이터가 이미 저장돼 있다. 데이터 저장 위치가 겹치는 것을 '충돌'이라고 한다.
15
이런 경우 리스트 구조로 기존 데이터와 연결한다. Sue -> Nell
16
Ally(F)의 해시값은 9143이고 5로 mod 연산한 결과는 3이 나온다. 배열의 3번 상자에 저장하려 하나 Joe의 데이터와 충돌하므로 리스트로 연결한다. Joe -> Ally
17
Bob(M)의 해시값은 5278이고 5 mod 연산 결과는 3이므로 리스트로 연결한다. Joe -> Ally -> Bob
18
이것으로 모든 데이터가 저장됐다. 해시 테이블을 완성한 것이다.
19
다음은 데이터 검색 방법이다. Dan의 성별을 확인하고 싶은 경우 키인 'Dan'의 해시값을 구하고 배열의 상자 수인 5로 mod 연산을 한다. 결과는 4이므로 4번 상자에 저장된 것을 알 수 있다. 배열의 4번 상자에 저장된 키가 Dan과 일치하므로 대응하는 값을 추출한다. Dan의 성별이 남성(M)인 것을 알 수 있다.
해시 테이블은 해시 함수를 이용해서 배열 내의 특정 데이터에 빠르게 접근할 수 있다. 한편, 해시 값이 충돌할 때는 리스트를 이용하고 있어서 저장할 데이터 수가 정해져 있지 않더라도 유연하게 대응할 수 있다. 해시 테이블에 사용하는 배열의 크지는 너무 작으면 충돌이 많아지고 선형 탐색의 빈도가 높아지게 된다. 반대로 너무 크면 데이터가 없는 상자가 많아져서 메모리를 낭비하게 되므로 배열의 크기를 적절히 설정하는 것이 중요하다.
참고 서적:
