[CS 노트] : Hash table에서 Collistion 해결하기

• Hash table에서 Collision 해결 방법은?
  • 대표적인 방법으로 2개가 있다.
  • open addressing
    • 충돌 발생 시 규칙에 따라 table의 비어있는 slot을 찾는다.
    • slot를 찾는 방법은 3가지가 있다.
      • Linear Probing
      • Quadratic Probing
      • Double Hashing
  • separete chaining
    • linked list를 사용한다.
    • 충돌 발생 시 노드(slot)을 추가해 데이터를 저장한다.

---

• Open addressing
  • 충돌이 발생하면 규칙에 따라 table의 비어있는 slot을 찾는다.
  • linked List나 tree를 사용하지 않는다.
    • 때문에 separate chaining에 비해 메모리를 적게 사용한다.
  • Linear Probing, 선형 조사법
    • 충돌이 발생한 해시값에서 일정 값만큼 건너 뛰어 비어있는 slot에 데이터를 저장한다.
  • Quadratic Probing, 이차 조사법
    • 충돌이 발생한 해시값에서 제곱수로 건너 뛰어 비어있는 slot을 찾는다.
  • 위 두 방법은 충돌 횟수가 증가하면 데이터가 몰리게 되는 클러스터링 현상이 발생되는데 이것을 해결하기 위해 Double Hashing을 사용한다.
  • Double Hashing, 이중, 중복 해시
    • 충돌 발생 시 문제를 해결할 때 주로 사용한다.
    • 말 그대로 2개의 해시 함수를 사용한다.
    • 첫 함수로 해시 값을 얻고, 두 번째 값은 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용한다.

---

• Separate chaining
  • 해시 함수를 통해 나온 해시 값을 그대로 Key에 저장하는 게 아니라 그 값을 node(slot)에 연결한다.
  • 즉, Linked list 형식으로 연결을 하게 된다.
  • 시간복잡도
    • 삽입은 linked list에 node를 추가해 데이터를 저장하기 때문에 O(1)이다.
    • 조회는 기본은 O(1)이지만 최악은 O(n)이 될 수 있다.
      • 최악인 경우는 n개의 key가 해시값이 모두 다 같을 때 n의 linked list가 생성되는 경우이다.
    • 삭제는 삭제를 위해 조회를 해야하니, 조회랑 같다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.