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

11-1 해시법

해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법입니다.

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

아래 그림 11-1 a 의 배열 a를 봅시다. 요소가 13개인 배열의 앞쪽 10개의 요소에 데이터가
오름차순으로 정렬된 상태로 저장되어 있습니다.

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

b 5 6 14 20 29 34 35 37 51 69 75 － －

추가하는 위치에 따라 모든 요소를 이동해야
할 수도 있습니다.
[그림 11-1] 정렬된 배열에 데이터를 추가

이 배열에 35를 추가하려면 아래와 같은 작업이 필요합니다.

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

요소 이동에 필요한 복잡도(time-complexity)는 O(n)이며 이 비용은 적은 비용이 아닙니다.
데이터를 삭제할 때도 같은 비용 O(n)이 발생합니다.

해시법
해시법(hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만
아니라 추가, 삭제도 효율적으로 수행하는 방법입니다. 다음 그림 11-2의 a 에서 볼 수 있는

배열의 키 값(각 요소의 값)을 배열의 요소 개수 13으로 나눈 나머지로 다시 정리하면 표 11-1
과 같습니다. 이렇게 표에 정리한 값을 해시 값(hash value)이라고 하며, 이 해시 값은 데이터
에 접근할 때 사용합니다.

hash는 ‘다진 고기 요리’, ‘뒤범벅’, ‘뒤죽박죽’, ‘잡동사니’라는 뜻이 담겨 있습니다.
11•해시 429