[C언어로 쉽게 풀어쓴 자료구조] 14장

01 해싱에서 충돌은 언제 발생하는가?

(1) 키가 같은 경우

(2) 해시 함수의 값이 같은 경우

(3) 같은 해시 함수를 사용하는 경우

(4) 키의 길이가 같은 경우

 

02 크기가 13인 해쉬 테이블에서 입력 자료 27과 130은 어떤 인덱스로 매핑되는가? 해싱 함수는 h(key)=key%13라고 하자.

(A)1, 10

(B)13, 0

(C)1,0

(D)2,3

 

03 크기가 11인 해싱테이블을 가정하자. 해시함수로는 다음을 사용한다.

h(k)=k mod 11

입력 자료가 다음과 같은 순서로 입력된다고 하면 아래의 각 경우에 대하여 해시테이블의 내용을 그려라.

 

12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5

(1) 충돌을 선형조사법을 사용하여 처리한다.

(2) 충돌을 이차조사법을 사용하여 처리한다.

(3) 충돌을 다음과 같은 이중해시법을 사용하여 처리한다.

h'(k)=7-(k mod 7)

(4)충돌을 체인법을 사용하여 처리한다.

 

04 "cat", "dog", "lion"과 같은 동물 이름을 해쉬 테이블에 저장하고자한다. 어떤 해싱 함수를 사용하는 것이 좋을까? 동물의 이름을 사용자로부터 받아서 해쉬테이블에 저장하는 프로그램을 직접 구현하여 보자.

삽입(i), 탐색(s), 삭제(d): i
동물의 이름 : cat
인덱스 54번에 저장되었음

삽입(i), 탐색(s), 삭제(d): s
동물의 이름 : cat
cat은 해쉬 테이블 54 인덱스에 있음!
...

05 체이닝에서 새로운 키를 삽입하는 시간은 무엇에 비례하는가?

(1)적재율

(2)테이블에 있는 전체 항목의 개수

(3)버킷의 연결리스트의 항목의 개수

(4)테이블의 크기

 

06 만약 1000개의 조그만한 영상을 해싱을 사용하여 사전 구조에 저장하고 싶다고 가정해보자. 각각의 영상은 20 픽셀 x 20 픽셀이다. 각 픽셀은 256색 중의 하나이다. 즉 하나의 픽셀은 하나의 바이트로 표시된다. 여기에 사용될 수 있는 가능한 해시 함수를 생각해보라.

 

07 본문에서도 설명되었듯이 이차 조사법(quadratic probing)이란 다음의 식에 의하여 인덱스를 조사하는 것이다.

(k+i²)%M for i≥0

여기서 M은 테이블의 크기이고 k는 해시주소이다.

(1)만일 해시 테이블의 크기가 17이고 해시 주소 k가 3이라면 다음에 조사되는 인덱스들을 처음부터 6개만 나열하라.

(2)다음에 조사할 인덱스를 다음의 순환식을 이용하여 보다 효율적으로 계산할 수 있음을 보여라

K ᵢ₊₁=(kᵢ+2i+1) mod M

(3) (2)의 결과를 이용하여 본문에 잇는 소스처럼 다음과 같은 문장을 도출하여 보라.

i=(i+inc+1) % TABLE_SIZE;

inc=inc+2;

 

08 선형조사법에서 키를 삭제하는 함수는 hash_lp_delete(element item, element ht[])를 구현해보라. 본문에서도 언급되었듯이 단순히 해시 테이블의 그 버킷을 단순히 비어있다고 표시하는 것은(본문에서는 슬롯의 키의첫 번째 문자를 0으로 만드는 것) 다음번의 탐색을 불가능하게 할 수 있다. 따라서 삭제가 허용되는 경우에도 올바른 탐색을 할 수 있도록 hash_lp_search 알고리즘을 수정하라. 하나의 힌트는 해시테이블의 빈 항목들을 한 번도 사용되지 않은 항목(empty)과 사용되었지만 현재는 비어있는 항목(deleted)으로 구별하여햐 한다.

 

09 체인법을 사용하는 해싱소스에도 삭제함수가 없다. 실제로는 키를 삭제할 수도 있어야 한다. hash_chain_delete(element item, LisstNodePtr ht[])함수를 구현해보라. 삭제시키고자 하는 키를 발견하면 포인터를 조정하여 레코드를 연결 리스트에서 제거한 다음, free 함수를 호출하여 동적 메모리를 반환해야 할 것이다.

 

10 선형 조사법과 이중 조사법을 비교하는 실험을 해보자. 먼저 500개의 사용자 이름이 들어 있는 리스트를 만든다. 그리고 크기가 1000인 해시테이블을 선형 조사법과 이중 조사법으로 구현하여 500개의 이름이 해시 테이블에 추가될 대 충돌이 얼마나 일어나는지 기록하라. 동일한 실험을 테이블 크기가 950, 900,850, 800, 750, 700, 650, 600 일 때 수행해본다.