Page 430 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

[표 11-1] 키 값과 해시 값의 대응
키 값 5 6 14 20 29 34 37 51 69 75

해시 값(13으로 나눈 나머지) 5 6 1 7 3 8 11 12 4 10

해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 아래의 해시 테이블(hash table)입
니다. 해시 테이블은 그림 11-2의 a 처럼 나타낼 수 있습니다.

예를 들어, 14를 a[1]에 저장하는 이유는 해시 값(13으로 나눈 나머지)이 1이기 때문입니다.

0 1 2 3 4 5 6 7 8 9 10 11 12
a － 14 － 29 69 5 6 20 34 － 75 37 51

b － 14 － 29 69 5 6 20 34 35 75 37 51
새로운 값(35)을 추가하더라도 다른 요소가 이동할
필요가 없습니다.

[그림 11-2] 해시에 새로운 값(35)을 추가

그러면 배열에 35를 추가하는 경우를 생각해 보겠습니다. 35를 13으로 나눈 나머지는 9이므
로 b 처럼 a[9]에 값(35)을 저장합니다. 이전의 ‘추가한 값’ 이후의 배열 요소를 모두 옮겼던
경우와는 다르게 새로운 값을 추가하더라도 다른 배열 요소를 뒤로 옮기지 않아도 됩니다.

이렇게 키 값(35)을 가지고 해시 값(9)을 만드는 과정을 해시 함수(hash function)라고 합니다.
보통 해시 함수는 여기에서 살펴봤듯이 ‘나머지를 구하는 연산 또는 이런 나머지 연산을 다시
응용한 연산’을 사용합니다. 그리고 해시 테이블의 각 요소를 버킷(bucket)이라고 합니다. 지
금부터는 해시 테이블의 요소를 버킷이라고 부르겠습니다.

충돌

이어서 배열에 새로운 값 18을 추가하는 경우를 생각해 보겠습니다. 18을 13으로 나눈 나머
지인 해시 값은 5이고 저장할 곳은 버킷 a[5]입니다. 그런데 그림 11-3처럼 이 버킷은 이미
채워져 있습니다. 이 경우에서 볼 수 있듯이 키 값과 해시 값의 대응 관계가 반드시 1대1이라

는 보증은 없습니다(보통 n대1입니다). 이렇게 저장할 버킷이 중복되는 현상을 충돌(collision)
이라고 합니다.

0 1 2 3 4 5 6 7 8 9 10 11 12
－ 14 － 29 69 5 6 20 34 35 75 37 51
삽입할 x[5]는 이미 채워져 있습니다.
18

[그림 11-3] 해시에 추가할 때의 충돌

430 C 알고리즘