자료구조 - 해시 함수(Hash Collision)종류와 충돌 처리 방식

해시 충돌(Hash Collision)이란

- 서로 다른 키를 가진 레코드들이 하나의 버킷에 매핑되는 경우

- 아래 그림을 보면 John Smith 와 Sandra dee를 해시함수 하여 동일한 해시값(02) 가 출력된 것을 볼 수 있는데 이가 해시 충돌이다.

문제점

- 해시 함수의 충돌은 해싱의 검출 속도를 떨어뜨리는 결과를 초래한다

- 버킷 오버플로우가 발생한다

해시 함수

- 해시함수는 해시테이블의 공간 전체에 고르게 저장할 수 있어야 한다(최대한 충돌을 발생하지 않게 해야한다.)

- 충돌이 많이 발생할 수록 저장하는 시간과 검출 시간이 오래걸린다.

- 계산이 간단해야한다.

1. Division - 저장하려는 데이터를 해시 테이블의 크기로 나눈 나머지의 값을 해시값(저장될 주소)으로 하여 저장

2. 제곱함수 - http://itstory.tk/entry/%ED%95%B4%EC%8A%81Hashing-%ED%95%B4%EC%89%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%89%AC-%ED%95%A8%EC%88%98

3. folding - 

4. radix 변환 - 

5. random method - 

버킷 오버플로우(Bucket Overflow)란

- 그림과 같이 버킷의 크기가 1인 경우 서로 다른 2개 이상의 키를 해시함수하여 같은 해시값이 나온다면

  버킷의 크기를 넘어서 저장하게된다 이를 버킷 오버플로우라고 한다.

문제점

- 버킷의 크기를 넘어 저장하는 경우 다른 버킷이 사용하는 주소공간을 침범하여 사용할 수 있다.

충돌 처리방법 (버킷의 슬롯 크기가 1인 경우 충돌 발생시 바로 오버플로우가 발생하므로 오버플로 해결방법 이라고도 함)

1. Seperate Chaning (Open Hashing)

- 충돌이 발생하면 주어진 해시테이블 공간외에 새로운 공간을 할당하여 해결한다.

- 이러한 특성으로 Open Hashing(개방해싱) 이라고도 한다.

( 0번 버킷에 이미 데이터가 저장되어 있는 상태에서 0번 버킷에 또다시 자료를 저장하려 할 때

   주어진 해시테이블 외에 새로운 공간을 할당하여 데이터를 저장하고 이전 노드가 그 공간을 가리킨다. )

*자바에서 Seperate Chaning을 사용한다 HashMap에서 remove()는 빈번히 일어나는데 OpenAddressing 방식은 데이터를 삭제할때 비효율적이기 때문이다.

자바 2~7 까지는 버킷을 가리키기위해 링크드리스트를 사용했으나 자바 8에서부터는 성능 향상을 위해 트리를 사용하여 성능을 크게 향상하였다.

평소에는 링크드리스트로 Seprate Chaning을 구현하다가 키와 값쌍이 8개 이상이면 트리로 변환하고 

키와 값쌍이 다시 6개 이하면 링크드리스트로 변환한다.

 (6개이하면 트리와 링크드리스트의 서치 시간은 비슷하나 트리의 메모리 사용량이 더 높음)

2. Open Addressing (Closed Hashing)

- 주어진 해시테이블에서 정해진 규칙에 따라 다음 버킷을 찾아 저장하는 방법이다.

- 정해진 해시테이블내에서만 저장이 되는 특징이 있다 때문에 Closed Hasing(폐쇄 해싱) 이라고도 한다.

OpenAdddressing 시뮬레이터 - https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html

Open Addressing의 다음 버킷 결정방법

1) 선형 조사 - 충돌이 일어난 바로 다음 자리에 저장하는 방법

*과정

아래 그림과 같이 특정 키값을 해시함수 한결과 3이란 버킷을 가리키는데 이때 3버킷에 이미 자료가 저장되어 있어 바로 다음 버킷인 4를 조사한다 하지만 이 역시 자료가 저장되어 있으므로 그 다음 버킷인 5에 저장하게 된다.

*문제점 - 제1 군집현상 발생

*제1 군집 현상 : 특정 영역에 데이터가 몰릴때 링크드리스트의 순차 탐색으로 데이터의 저장공간이 지정되어                             성능이 치명적으로 저하 된다. , 이차원 조사로 해결 가능하다

   

2) 이차원 조사 - 충돌이 발생한 경우 다음 데이터의 자리를 아래 그림의 이차 함수로 결정 

   - 제1 군집현상을 해결   

*quadratic Method 

(n이 소수일 때 성능이 좋다)

*문제점 - 제2 군집현상 발생

3) 더블 해싱

4) 무작위 처리 방법