알고리즘 [이중해싱]

🔎 충돌

해싱을 통해 해시값을 넣어줄 때 같은 셀로 매핑되는 것을 충돌이라고 한다..!

이러한 충돌에는 일관된 해결 전략이 필요!

• 분리연쇄법(연쇄법)

분리연쇄법 이란 해당 버켓리스트에 대한 각각의 참조를 저장하는 방법이다.

같은 버켓리스트로 해싱되었다면 연결리스트로 묶어서 외부의 저장공간을 사용하여 저장한다.
ㄴ 예제

• 버켓리스트의 사이즈가 13이고 넣는 키값은 랜덤이라고 가정한다면 해시함수는 K % M으로 작성할 수 있다.
• 이때, 만약 25가 주어진다면 25 % 13 = 12이기 때문에 버켓리스트의 마지막셀에 해당 주소값을 저장하게 된다(연결리스트 형태)
• 위와같이 값이 차례대로 저장되다 중복키가 들어오게 된다면 연결리스트형식으로 앞에 연결되게 된다.
  • 앞에다 달아야 삽입시 유리하다.
• 개방 주소법

충돌 항목을 테이블의 다른 셀에 저장하는 방법, 공간 사용을 절약하지만 삭제가 어렵다는 단점이 존재..

위의 예제에서 같은 셀을 참조할 때 어떠한 규칙에 의해서 다른 셀로 이동하게 되는 것 따라서 삭제가 어렵다.

종류

• 선형 조사법
  • 충돌항목을 바로 다음의 비어있는 테이블 셀에 저장
  • 만약 옆방도 채워져 있다면 다다음방으로 이동
  • 따라서 군집화(셀끼리 모이는 현상)이 생김
• 2차 조사법
  • 위에 군집화를 피하기 위해 제곱을 이용하여 셀의 군집화를 떨어트림
  • 나름대로 2차 군집화를 이루게 된다. 하지만 버켓이 소수가 아니거나, 배열이 반이상 차면 찾을 수 없을 수 도있다.
• 이중해싱
  • 주소를 결정해주는 해싱과 위치를 결정해주는 해싱을 두번 하는 것
  • 위치 계산결과는 0이면 안된다, 서로소여야 한다.

개방주소법의 삭제방법

각셀의 태그를 활성화하여 구함, flag같이 각 셀의 활성화, 비활성화, 비어있는 세가지 경우

자료구조를 위와 같이 짜면 알고리즘이 간단해진다.

• 검색의 경우 -> 비어있는 셀을 만나면 탐색 실패, 활성 셀의 항목이라면 반환
• 삽입의 경우 -> 비어있거나 비활성인 방은 셀에 저장 후 활성화
• 삭제의 경우 -> 비어있는 셀 만나면 실패, 활성 셀을 비활성화 시킴

적재율

a = n/M

적재율이란, 좋은 해시함수를 사용할 경우의 각 버켓의 기대 크기, 적재율은 낮게 유지되어야 한다.

분리연쇄법

a > 1이면, 작동은 하지만 비효율적. a <= 1이면 기대실행시간 성취 가능

개방주소법

항상 a <= 1, a > 0.5면, 선형 및 2차 조사법인 경우 군집화 가능성 농후 함

a <= 0.5면, O(a) = O(1) 기대실행시간

재해싱

해시테이블의 적재율을 상수(보통 0.75)이하로 유지하기 위해서는, 원소를 삽입할 때마다 이 한계를 넘기지 않기 위해 추가적인 작업 필요

보통 2배로 크기를 늘려서 진행함

언제?

• 적재율의 최적치를 초과하였을 때 기본 0.75정도
• 삽입이 실패한경우
• 너무많은 비활성화 셀로 포화되어 성능이 저하되었을 때

재해싱의 단계

1. 버켓 배열의 크기를 증가시킨다. (대략 두배, 소수유지)
2. 새 크기에 대응하도록 압축맵을 수정
3. 새 압축맵을 사용하여, 기존 해시테이블의 모든 원소들을 새 테이블에 삽입

정리

• 해시테이블에 대한 탐색 삽입,삭제: 최악의 경우 O(n)
• 최악의 경우: 사전에 삽입된 모든 키가 충돌할 경우
• 해시값들을 난수와 같다고 가정하면, 개방주소법에 의한 삽입을 위한 기대조사 횟수는 1/(1 - a)라고 알려짐
• 모든 ADT작업들의 기대 실행 시간은 O(1)
• 적재율이 0에 가깝지 않다면 해싱은 매우 빠름

---

응용문제 풀어보기! (기말고사 필기로 나옴)