해시 테이블 충돌 해결 방법

체이닝

- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리

• 장점 : 적재율이 1이 넘어도 사용할 수 있다.

• 단점 : 삽입시간은 연결리스트의 길이에 비례하므로 비용이 더든다

• 저장 : 연결리스트에서의 순서는 저장된 순서의 역순이다.
  ex) 저장된 순서가 55,42,3,94 순서이면 연결리스트에서는 94, 3, 42, 55가 된다.
  

• 검색 : 94를 찾을 때는 연결리스트 주소를 찾으면 바로 나오지만 3이나 42를 찾고 싶을 때에는 앞순서에 있는 94나 3까지 다 조사하고선 찾게된다.

• 삭제 : 삭제할 시에는 연결리스트에서 그 원소를 삭제하면 된다.

개방주소

체이닝과 달리 추가 공간을 허용하지않음. 만약 충돌이 나더라도 주어진 테이블 공간에서 해결한다.

주의
1. 적재율이 1을 넘을 수 없다
2. 삭제 시 주의해야한다.

• 만약 2주소에서 충돌로 인해 2번째 원소가 밀려난 후 1번째 원소를 삭제한 후, 2번째 원소를 찾으면 알고리즘은 2주소만 봐라보고 있기에 못찾는다
• 해결방안 : 삭제 후 삭제한 위치에 원래 원소가 있었다 삭제했다는 표시인 DELETED 라는 상수 값을 저장하면된다.

-삽입 : 빈칸을 찾을 때 까지 계속 찾는다.

개방주소방법의 세가지 충돌 해결 방법

1. 선형조사

• 가장 간단한 충돌 해결 방법
• 충돌이 얼어난 바로 뒷자리를 본다.
• 빈자리를 찾을 때 까지 계속 돌아다닌다.

단점 : 한가지 영역에 여러 원소가 물릴시 성능이 떨어진다. 이를 1차군집이라한다.(한가지 주소가아니라 비슷한주소)

2. 이차원 주소

• 바로 뒷자리를 보는게 아닌 보폭을 이차함수로 넓혀가면서 본다.

• 장점 : 선형조사보단 보폭이 넓기에 빈자리를 빨리 찾을 수 있다.

• 단점 : 여러개의 원소가 동일한 초기 해시 함수 값을 갖게 되면 모두 같은 순서로 조사를 할수밖에 없어 효율이 떨어짐(보폭을 이차함수로 넓히기에 바로뒤에 공간이 있어도 못먹음) -> 이런현상을 2차군집
  

3. 더블 해싱

-2개의 함수를 사용함

• 과정 : 첫번째 해시함수는 데이터를 해시테이블의 인덱스로 맹핑함, 두번 째 해시함수가 충돌이 발생한경우 두번째 해시 함수만큼 보폭을 이동함

-장점 : 2차 군집이 발생하지않는다.

출처
쉽게 배우는 알고리즘