[해시 테이블] 충돌 해결

• 충돌
  • 어떤 키가 이미 자리잡고 있는 상태에서 다른 키가 삽입을 시도하는 것
  • 동일한 주소에 2개 이상의 키가 해싱되는 상황
• 충돌 해결 방법
  • 체이닝
  • 개방 주소 방법

 

체이닝

• 같은 주소로 해싱되는 키를 모두 하나의 연결 리스트에 매달아서 관리함
• 해시테이블의  크기가 m이면 최대 m개의 연결 리스트가 존재할 수 있음
• 같은 주소로 들어온 키들은 해당 헤더 다음에 연결리스트로 매달려 있음
• 체이닝은 임의의 키를 삽입할 때  해시값이 가리키는 연결리스트에 삽입함
• 리스트의 맨 앞에 삽입하는 것이 좋음
• 키를 검색할 때 해당 연결 리스트의 키들을 차례로 지나가면서 찾음
• 적재율이 1을 넘어도 사용할 수있음

 

 

 

개방 주소 방법

• 체이닝과 달리 추가 공간을 사용하지 않음. 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결함
• 모든 키가 반드시 자신의 해싯값과 일치하는 주소에 저장된다는 보장이 없음
• 해시 함수를 계산 -> 계산 주소에 다른 키가 없으면 그 자리에 넣음
• 해시 함수를 계산 -> 계산 주소에 다른 키가 있으면 정해진 규칙에 의해 다음 차리를 찾음(빈자리가 나올 때까지 계속 찾음) : 순차적 해시함수. 선형 탐색
• 테이블에 주어진 공간만 사용할 수 있으므로 적재율이 1을 넘을 수 없음
• 적재율이 어느 정도 이상 높아지면
  • 효율이 급격히 떨어지므로 적당한 임계점을 설정하고 그 임계점을 넘으면 해시 테이블의 크기를 2배로 키우는 것이 일반적
  • 테이블 크기가 바뀌면 해시 함수가 바뀌므로 모든 키를 다시 해싱
• 조심 해야하는 경우 : 키를 삭제 했을 때
• 중간에 있는 주소의 키가 삭제되었을 때 원래는 키가 있던 자리였음을 표시해주어야 함

 

개방 주소 방법의 충돌 해결 방법

• 선형 탐색
  • 충돌이 일어난 바로 뒷자리를 보는 것
  • i에 관한 일차함수의 보폭으로 점프
  • 테이블의 경계를 넘어갈 경우 맨 앞으로 가면 됨
  • 특정 영역에 키가 몰릴 때 치명적으로 성능이 떨어짐 : 1차 군집
  • 영역이 커질수록 해당 영영그올 해싱될 확률(충돌 확률)이 커지므로 군집이 심하지 않은 영역에 비해 영역의 크기가 빨리 커짐

 

• 이차원 탐색
  • 바로 뒷자리를 보면서, 보폭을 이차 함수에 의해 넓혀가면서 봄
  • 1차 군집 영역을 이차원 탐색 방법을 이용해서 벗어남
  • 여러 개의 키가 동일한 초기 해시 함숫값을 가지면 모두 같은 순서로 탐색하게 되므로 비효울을 피할 수 없음 : 2차 군집
  • 보폭은 점점 넓어지지만 최초의 해싯값이 같은 키들은 이차원 탐색으로 인해 이득을 보지 못함

 

• 더블 해싱
  • 2개의 함수를 사용함. h(x)와 f(x)는 서로 다른 해시 함수
  • 충돌이 생겨 다음에 볼 주소를 계산할 때 두번째 해시 함숫값만큼씩 점프함
  • 두 키의 첫번째 해싯값이 같더라도 두 번째 함수값이 같은 확률은 매우 작으므로 서로 다른 보폭으로 점프하게됨
  • 해시 함수 정할때 권장법
  • 소수 m에 대하여 h(x)=x%m으로 잡고, m보다 조금 작은 소수m'에 대해 f(x)=1+(x%m')
  • 조심할 점: 두번째 해시 함수값 f(x)가 해시 테이블 크기 m과 서로 소인 값이어야함

 

체이닝의 검색 기대 시간

• 이론적
  • 체이닝 방법을 이용해서 적재율이 a일 때, 탐색 횟수의 기대치는  a에 비례함
  • 개방 부소 방법의 이론적 성능은 체이닝보다 못함
  • 자신이 해시되지 않은 주소에 저장될 수 있으므로 복잡해짐
• 실제
  • 체이닝은 우선 각 연결 리스트마다 헫를 하나씩 두어야 하고, 연결 리스트를 만들기 위해 각 키마다 연결을 위한 공간이 필요함. 따라서 적재율이 그리 높지 않을 때는 개방 주소 방법이 더 선호됨
  • 대신 개방 주소 방법은 적절하게 낮은 적재율을 유지할 필요가 있

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」