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

같은 해시 값을 갖는 데이터 저장하기
여기에서도 키 값을 13으로 나눈
다음 그림 11-4는 체인법으로 구현한 해시의 한 예입니다. 나머지를 해시 값으로 지정합니다.

체인법은 같은 해시 값을 갖는 데이터를 연결 리스트에 의해 사슬 모양으로 연결합니다. 배열
의 각 버킷(해시 테이블)에 저장하는 값은 그 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째

노드(node)에 대한 포인터입니다(배열 이름을 table로 지정했습니다).

예를 들어, 그림 11-4에서 69와 17의 해시 값은 모두 4이며, 이들을 연결하는 연결 리스트의

첫 번째 노드에 대한 포인터를 table[4]에 저장합니다. 또 해시 값(인덱스) 0과 2처럼 데이터가
하나도 없는 버킷의 값은 널(NULL) 포인터 값을 저장합니다.

각 버킷에 저장하는 값은 ‘같은 해시 값을 갖는 노드를 연결한 리스트’의 첫 번째 노드에 대한 포인터입니다.
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２

14 29 69 5 6 20

NULL
17 33

같은 해시 값을 갖는 데이터를 연결 리스트(사슬 모양)로 연결합니다.

[그림 11-4] 체인법으로 해시 구현

회원 프로그램과 마찬가지로 체인법을 구현하는 프로그램도 헤더(header) 부분과 소스
(source) 부분으로 나누어 만듭니다. 실습 11-3의 ChainHash.h 파일이 헤더입니다. 아래에
서 프로그램을 비교하며 살펴보겠습니다.

Node Node
no
버킷용 구조체 Node data name
개별 버킷을 나타내는 것이 구조체 Node형입니다. 이 구조체는 next
다음 노드에 대한 포인터
그림 11-5에 나타냈듯이 두 멤버 data, next로 구성됩니다.
[그림 11-5] 버킷을 나타내는 구조체

실습 11-3 •완성 파일 chap11/ChainHash.h

01 /* 체인법으로 구현한 해시(헤더) */
02 #ifndef ___ChainHash
03 #define ___ChainHash
04

434 C 알고리즘