[자료구조] 해시테이블과 충돌 해결

Hash Table

• 해시 테이블을 사용하는 이유?
  • 적은 자원으로 많은 데이터의 효율적인 관리
  • 언제나 동일한 해시 값을 리턴하므로 찾고자하는 값의 index를 알면 빠른 검색이 가능

Hash Function

• 단방향의 해시 함수를 구현하여 해시 값을 리턴한다.
• 데이터가 많아지면 다른 데이터가 동일한 해시 값으로 충돌나는 현상이 ‘Collision’ 이다.
• 좋은 해시 함수란, 데이터는 고르게 분포하고 충돌을 최소화할 수 있는 함수이다.

Resolve Collision

• Open Addressing

출처: https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

 

• Linear Probing
  • index에 대한 충돌이 발생했을 때, index 뒤에 있는 버킷 중에 빈 버킷을 찾아 데이터를 넣는 방식
  • 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)
    • 다음 버킷에도 데이터가 있으면 고정폭으로 또 옮겨 액세스하는 방식

출처: https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

• Quadratic probing
  • Linear Probing와 달리 폭이 제곱수로 늘어난다는 특징을 가지는 방식
• Double hashing
  • 탐사할 해시값의 규칙성을 없애 clustering을 방지하는 방식
  • 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화하는 특징 존재

출처: https://en.wikipedia.org/wiki/Hash_table

• Separate Chaining
  • 각 index에 데이터를 저장하는 linked list에 대한 포인터를 저장하는 방식
  • 삭제할 때는, key에 대한 index가 가리키는 linked list에서 해당 노드를 삭제한다.
• Resize
  • Open Addressing의 경우에는 고정적인 크기의 배열을 사용하기 때문에 확장해야한다.
  • Separate Chaining의 경우에는 버킷이 일정 수준으로 차게 되면, 각 버킷에 연결되어 있는 리스트의 길이가 늘어나므로 버킷의 개수를 늘려줘야 한다.
  • 이를 Resizing이라하고, 더 큰 array를 새로 만들고 해당 array에 해시를 다시 계산해서 복사한다.