[자료구조] 해시 테이블 - 충돌 문제(Collision)

다만, 다른 입력값에서 동일한 해시 값이 발생되는값이 같을 때 발생하는 충돌(Collision)문제가 있는데, 이것을 해결해야 하는 방법이 필요합니다.

 

1. 열린 어드레싱 방법 (Open Addressing Method)

 

선형 조사법(Linear Probing)

: 충돌이 발생했을때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장하는 방식

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

쉽게 옆자리가 비어있으면, 그 옆자리로..

그 옆자리가 이미 있으면 그 옆자리로..계속 식으로 이동하게 되는 것 입니다.

계산이 단순하다는 장점이 있지만, 검색에 시간이 많이 소요되고, 테이블 내에 데이터들이 일정한 키 값으로 모이는 현상이 발생합니다.

 

이차 조사법 (Quadratic Probing)

: 선형 조사법이 n칸 옆을 검사한다면, 이자 조사법은  

 칸 옆을 검사하는 것입니다.

 

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

 

이렇게 된다면, 일정한 키 값으로 모이는 현상은 방지하겠지만, 모든 공간을 다 검사하지는 않게 되겠지요.

 

이중 해시(Double Hash)

: 처음에는 하나의 해시 함수를 사용하다가 충돌이 발생하면, 두번째 해시 함수를 사용하여 해시 값을 가지는 것 입니다.

 

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

재해싱(Rehasing)

: 해시 테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞추어 다시 모든 데이터를 해싱하는 방법입니다.

다시 배치가 되는것은 좋지만 상당히 많은 비용이 발생하겠지요..

 

2. 닫힌 어드레싱 방법 (Closed Addressing Method)

 

체이닝

: 해시 테이블 자체는 포인터 배열로 만들고, 같은 버켓의 해당하는 데이터들을 체인형식으로 만들어(링크드 리스트) 연결하는 방식입니다.

이 경우 삽입 삭제가 용이 하지만 따로 동적인 공간을 할당 해야 하는 문제가 발생합니다.

 

 

 

[참고]

[사이트]https://en.wikipedia.org/wiki/Hash_tablehttp://faculty.cs.niu.edu/~freedman/340/340notes/340hash.htm
[서적]윤성우의 열형 C 자료구조