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

24 if((h->table = calloc(size, sizeof(Node *))) == NULL) {
25 h->size = 0;
26 return 0;
27 }
28 h->size = size;
29 for(i = 0; i < size; i++) /* 모든 버킷을 공백(NULL) 상태로 만듭니다. */
30 h->table[i] = NULL;
31 return 1;
32 }
33 (실습 11-4[B]에서 계속)

위의 코드에서 초록색으로 표시한 부분을 좀 더 살펴보겠습니다. 기억 영역 확보에 실패

(calloc 함수가 NULL을 반환)하면 좌변에 있는 멤버 table에 NULL을 대입하고, 멤버 size에 0을
대입합니다.
멤버 size에 0을 대입하면 해시에 데이터가 잘못 추가되는 것을 방지할 수 있습니다.

보충수업 11-1 해시와 해시 함수에 대하여

데이터를 추가할 때 충돌이 전혀 발생하지 않는다고 가정합시다. 그러면 검색, 추가, 삭제 작업은 해시
함수를 통한 인덱스 찾기로 대부분 완료됩니다. 이렇게 인덱스 찾기로 수행하는 검색, 추가, 삭제에 대
한 시간 복잡도는 O(1)입니다. 데이터 추가 시 해시 테이블을 크게 하면 충돌 발생을 억제할 수 있지만
이 방법은 메모리를 쓸데없이 많이 차지합니다. 즉, 시간과 공간의 절충(trade-off)이라는 문제가 항상
따라다닙니다.

충돌을 피하기 위해 해시 함수는 해시 테이블 크기 이하의 정수를 가능한 한 치우치지 않게 고르게 만
들어야 합니다. 그래서 해시 테이블 크기는 소수(素數)가 좋다고 알려져 있습니다. 이 밖에도 키 값이 정
수가 아닌 경우 해시 값을 구하려면 다른 방법을 사용해야 합니다. 예를 들어, 실수 키 값에 대한 비트
연산(bitwise operation)을 하는 방법, 문자열 키 값에 대한 각 문자 코드에 곱셈과 덧셈을 하는 방법이
있습니다.

키 값으로 요소를 검색하는 Search 함수
키 값이 x->no인 요소를 검색하는 함수입니다. 그러면 구체적으로 예를 들어 Search 함수가

어떻게 요소를 검색하는지 살펴보겠습니다.

438 C 알고리즘