해시법

지난 글 : [알고리즘/Do it 알고리즘] - Object 클래스

 

정렬된 배열에 새로운 값 추가

아래 배열 a를 보자. 요소가 13개인 배열에서 앞쪽 10개 요소에 오름차순으로 정렬된 데이터가 저장되어 있다.

a
5	6	14	20	29	34	37	51	69	75	-	-	-
===================================================================================================
b
5	6	14	20	29	34	35	37	51	69	75	-	-	
//35를 추가

이 배열에 35를 추가하는 과정은 아래와 같다.

1. 삽입할 위치가 a[5]와 a[6] 사이임을 이진 검색법으로 조사한다.
2. 배열 b와 같이 a[6] 이후의 모든 요소를 하나씩 뒤로 이동한다.
3. a[6]에 35를 대입한다.

요소 이동에 필요한 복잡도(time-complexity)는 O(n)이므로 그 비용은 결코 작지 않다. 물론 데이터를 삭제하는 경우에도 똑같은 비용이 발생한다.

 

해시법

해시법(hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구해 검색, 추가, 삭제를 효율적으로 수행한다. 위 배열 a에서 배열의 키값을 배열의 요솟수 13으로 나눈 나머지를 정리하면 아래와 같다.

해시값을 인덱스로 해 원래의 키값을 저장한 배열이 해시 테이블(hash table)이다. 위 표의 해시 테이블은 아래 a이다.

그럼 배열에 35를 추가하는 경우를 생각해보자. 35를 13으로 나눈 나머지는 9이므로 b처럼 a[9]에 값(35)을 저장한다. 가장 위 배열에서 값을 추가한 후 배열 요소를 모두 옮겼던 경우와는 다르게 새로운 값을 추가해도 다른 배열 요소를 옮기지 않아도 된다. 이렇게 키값(35)을 해시값(9)으로 변환하는 과정을 해시 함수(hash function)라 한다. 보통 여기서 살펴봤듯 '나머지를 구하는 연산' 또는 '나머지 연산을 다시 응용한 연산'을 사용한다. 그리고 해시 테이블의 각 요소를 버킷(bucket)이라 한다. 이제부터 해시 테이블의 요소를 버킷이라 하자.

 

충돌

이어서 배열에 새로운 값 18을 추가해보자. 18을 13으로 나눈 나머지(18의 해시값)는 5이고 저장할 곳은 버킷 a[5]이다. 그런데 이 버킷은 이미 채워져 있다. 이 경우처럼 키값과 해시값의 대응 관계가 반드시 1 대 1이어야 하는 것은 아니다. 이렇게 저장할 버킷이 중복되는 현상을 충돌(collision)이라 한다.

그러므로 해시 함수는 가능한 해시값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다. 

 

충돌 대처법

충돌이 발생할 때 아래 2가지 방법으로 대처할 수 있다.

- 체인법 : 해시값이 같은 요소를 연결 리스트로 관리한다.
- 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

 

참고 서적 :