Open Hashing - Chaining

 

참고 문헌

뇌를 자극하는 알고리즘, 쉽게 풀어쓴 자료구조

 

개념

구현할 방식은 Chaining방식이다.

 

해시 주소가 같은 탐색 키들을

하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다.

이러한 리스트는 그 크기를 예측할 수 없으므로,

연결 리스트로 구현하는 것이 가장 바람직하다.

각 버킷에 고정된 슬롯을 할당하는 것이 아니라,

각 버킷에 삽입과 삭제가 용이한 연결리스트를 할당한다.

당연히 버킷 내에서 원하는 항목을 찾을 때는 연결리스트를 순차 탐색한다.

 

예를 들어, 크기가 7인 해시 테이블에 h(k) = k mod 7 의 해시 함수를 이용하여

8,1,9,6,13을 삽입할 때에의 체이닝에 의한 충돌 처리를 보자.

 

1. h(8) = 8 mod 7 = 1          (저장)

2. h(1) = 1 mod 7 = 1          (충돌 발생 -> 새로운 노드 생성해서 저장)

3. h(9) = 9 mod 7 = 2          (저장)

4. h(6) = 6 mod 7 = 6          (저장)

5. h(13) = 13 mod 7 = 6      (충돌 발생 -> 새로운 노드 생성해서 저장)

 

위의 내용을 그냥 보면, 이해가 안될수 있으니까, 아래의 그림으로 보자.

한 가지 결정을 해야 하는 것은 연결 리스트의 어디에다가

새로운 항목을 삽입하느냐 하는 것이다.

만약 탐색 키들의 중복을 허용한다면

연결 리스트의 처음에다가 삽입하는 것이 가장 능률적이다.

만약, 중복이 허용이 되지 않는다면 연결 리스트를 처음부터 탐색하여야 하므로

어차피 연결 리스트의 뒤로 가야하고, 여기에다 삽입하는 것이 자연스럽다.

결론은 연결 리스트의 확장판임을 알 수 있다.

 

구현

common.h

 

 

HashTableHeader.h

 

HashTable.h

 

HashTable.c

 

 

main.c

 

실행결과

 

소스 파일 & 헤더 파일

common.h

0.00MB

HashTable.c

0.00MB

HashTable.h

0.00MB

HashTableHeader.h

0.00MB

main.c

0.00MB