[자료구조] 해시(Hash)

정의

키에 대응되는 값을 저장하는 자료구조.

해시 함수를 통해 키를 해시 값으로 변환한 뒤, 테이블에서 그 값에 해당하는 인덱스에 배치해 데이터를 관리한다.

 

특징

• 삽입, 삭제, 검색, 갱신에 전부 O(1)의 시간이 걸린다.
  • 단, 서로 다른 키가 같은 해시 값을 갖게 되면 충돌이 발생하게 되는데 이 충돌이 빈번해질 경우 성능이 저하된다.
  • 모든 키의 해시 값이 같은 최악의 경우 O(N)의 시간이 걸리게 된다.
  • 때문에 합리적인 해시 함수를 사용해 각 키의 해시 값을 최대한 고르게 퍼뜨려야 성능을 향상시킬 수 있다
• 일단 충돌이 발생한 경우에 대한 대표적인 대처 방법은 Chaining과 Open Addressing이 있다.
  • Chaining : 각 인덱스마다 연결 리스트를 두고 충돌 발생 시 해당 연결 리스트에 삽입해 충돌을 회피하는 방법
  • Open Addressing : 충돌 발생 시 뒤쪽으로 이동하며 처음 나오는 빈 공간에 삽입해 충돌을 회피하는 방법
    • 이렇게 배치할 경우 데이터들이 뭉쳐있는 여러 영역이 생기게 되는데 이를 Cluster 라고 한다.
    • 한 Cluster에 데이터가 추가로 삽입되면 해당 Cluster의 크기가 1 늘어나고, 이 크기가 커질수록 탐색 범위가 증가해 성능이 저하되는데 이를 Clustering(클러스터링)이라 한다.
    • Open Addressing에서 빈 공간을 찾는 방법에는 Linear Probing, Quadratic Probing, Double Hashing 등이 있다.
    • Linear Probing : 충돌 발생 시 뒤쪽으로 한 칸씩 이동해 탐색해 나가는 방법. 비슷한 값끼리 붙어있게 되므로 캐시 적중률이 높아지지만 클러스터링에 취약하다.
    • Quadratic Probing : 충돌 발생 시 처음 위치로부터 1칸, 4칸, 9칸...등 제곱으로 커지는 범위만큼 이동해 탐색해 나가는 방법. 캐시 적중률이 다소 낮아지지만 클러스터링을 다소 회피할 수 있다.
    • Double Hashing : 충돌 발생 시 이동할 칸 수를 새로운 해시 함수를 통해 계산해 탐색해 나가는 방법. 캐시 적중률이 매우 많이 낮아지지만 클러스터링을 효과적으로 회피할 수 있다.