해시 충돌 !?
- 서로 다른 값을 가진 key가 해시 테이블의 한 주소에 매핑되는 경우이다.
- hashing을 해서 삽입하려 했으나 이미 다른 원소가 자리를 차지 하고 있는 상황.
이럴 경우, 해싱의 검출 속도를 떨어뜨리고 버킷 크기를 넘어 저장되어 오버 플로우가 발생한다.
해결 방안
1. 열린 어드레싱 방법 (Open Addressing Method)
- 선형 조사 : 충돌이 일어난 바로 뒷 자리로 값을 넣어준다.
이미지 출처 : http://faculty.cs.niu.edu/
- 계산이 단순하다는 장점.
- 검색에 시간이 많이 소요된다.
- 테이블 내에 데이터들이 특정 영역에 값이 몰리는 현상이 발생한다.
- 이차 조사법 : 충돌이 일어나면 2차 방정식을 이용해서 위치를 구해 값을 넣어준다.
- 선형 조사법이 n칸 옆을 검사한다면 이차 조사법은 n^2 칸 옆을 검사한다.
- 특정 영역에 값이 몰려도 그 영역을 빨리 벗어 날 수 있지만, 여러 개의 원소가 같은 초기 해쉬 값을 갖게 되면 모두 같은 순서로 조사할 수 밖에 없다.
- 이중 해싱 : 두 개의 함수를 이용하여 하나의 함수는 최초 해시값을 구하고 다른 함수는 해시 충돌이 일어났을 경우 이동할 폭을 구할때 사용한다.
- 재해싱(Rehasing) : 해시 테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞춰 다시 모든 데이터를 해싱하는 방법
- 다시 배치가 되는 것은 좋지만 많은 비용이 발생한다.
2. 닫힌 어드레싱 방법(Closed Addressing Method)
- 체이닝 : 해시 테이블 자체는 포인터 배열로 만들고 같은 버켓의 해당하는 데이터들을 체인 형식으로 만들어(링크드 리스트) 연결하는 방식.
이런 경우, 삽입,삭제가 용이하지만 따로 동적인 공간을 할당해야 하는 문제가 발생한다.
Reference
developer