인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Open Addressing에 의한충돌 해결

• 모든 키를 해쉬 테이블 자체에 저장

• 테이블의 각 칸(slot)에는 1개의 키만 저장

• 충돌 해결 기법

  • Linear probing

  • Quadratic probing

  • Double hashing

Linear probing

h(k), h(k)+1, h(k)+2, … 순서로 검사하여 처음으로 빈 슬롯에 젖아 테이블의 끝에 도달하면 다시 처음으로 circular하게 돌아감

• Linear probing의 단점

  • primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미

  • 이런 cluster가 생성되면 이 cluster는 점점 더 커지는 경향이 생김

• Quadratic probing
  • 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2, h(k)+3^2, … 순서로 시도
    (꼭 n^2가 2일 필요는 없고 임의의 숫자면 된다)

• Double hashing

  • 서로 다른 두 해쉬 함수 h1과 h2를 이용하여
    h(k, i) = (h1(k) + i*h2(k)) mod m

Quadratic probing

충돌 발생시 h(k), h(k)+1^2, h(k)+2^2, h(k)+3^2, … 순서로 시도

Double hashing

(두번째 해쉬 함수는 0이면 안된다)

Open Addressing - 키의 삭제

• 단순히 키를 삭제하는 경우 문제가 발생

  • 가령 A2, B2, C2가 순서대로 모두 동일한 해쉬함수값을 가져서 Linear probing으로 충돌 해결(왼쪽 그림)

  • B2를 삭제한 후(가운데 그림) C2를 검색