[자료구조] Hash

해시 테이블(Hash Table)

• 해시 테이블이란, (key, value)의 형태로 데이터를 저장하는 자료구조이다.
• Hash map, map, dictionary, 연관배열 등의 이름으로 알려져 있다.
• 해시 함수에 key를 적용해 나온 결과를 배열의 인덱스로 하고, 그 자리에 value를 저장한다.
• 해시 충돌이 일어나지 않는 경우, 해시테이블의 시간 복잡도는 O(1)

 

해시 함수

• key를 해쉬로 바꿔주는 역할을 한다.
• 다양한 길이를 가지고 있는 key를, 일정한 길이의 hash로 바꾸어 공간을 효율적으로 관리
• (key의 길이 > hash의 길이)
• 해시 충돌(Hash Collision)을 최소화 하는 해시 함수를 만드는 것이 중요

 

해시

• 해시 함수의 결과 값
• 저장소(bucket)에서, 값(value)와 매칭되어 저장됨

 

해시 충돌

• 서로 다른 키가 같은 해시 값을 가지는 경우
• ex) "Sam Smith"와 "Emily Kim" 을 해시 함수에 넣었을 때 같은 결과가 나오는 경우

 

해시 충돌의 해결법

 

Chaining(체이닝)

• 해시 충돌이 일어났을 때, 이를 동일한 버킷에 저장하는데, 이를 연결리스트 형태로 저장하는 방법을 말한다.
• 시간 복잡도
  • 탐색 / 삭제는 키에 해당하는 리스트의 길이에 비례함, 최악의 경우 O(K) , 이때 K는 키 값의 갯수
  • 삽입은 O(1)

체이닝

Open Addressing

• 해시 충돌이 일어날 경우, 저장소의 다른 주소도 이용할 수 있게 하는 방법

Open Addressing

• ex) "Sandra Dee"라는 키에 대해 해시 함수를 적용한 결과, 152가 나왔다. 그렇지만 152번은 이미 다른 키에 의해 사용되고 있는 공간임. 따라서 그 다음 비어있는 주소인 153에 저장함.
• 시간 복잡도
  • 탐색, 삽입, 삭제 모두 최상의 경우 O(1), 최악의 경우 O(n)
• 장/단점
  • 장점
    • 다른 저장공간 없이 해시테이블 내에서 데이터 저장이 가능하다
  • 단점
    • 해시함수의 성능에 따라 해시 테이블 전체의 성능이 좌지우지된다.
    • 데이터의 양이 늘어나면 그에 해당하는 크기의 저장소를 미리 확보해두어야 한다.
• Open Addressing에서는, 저장소가 어느정도 채워졌을 때, 저장소의 크기를 늘리는 것이 중요하다

 

 

Open Addressing의 3가지 충돌 해결 기법

 

Linear Probing(선형 탐사)

• 그 다음으로 비어있는 인덱스에 데이터 삽입
• 배열의 끝까지 갔는데 빈 공간을 찾지 못한 경우, 맨위부터 다시 탐색
• 단점 : 바로 인접한 인덱스에 데이터를 삽입하기 때문에, 데이터가 밀집되는 클러스터링(Clustering) 현상이 발생 가능 → 탐색 시간이 클러스터링의 크기만큼 길어지게 된다.

 

Quadratic Probing(제곱 탐사)

• 배열을 하나씩 이동하며 인접한 빈 공간부터 탐색하는 선형 탐사 방식과 달리, 1^2, 2^2, 3^2, 4^2 의 순으로 배열을 건너 뛰며 빈공간을 탐색하는 방식
• 더욱 폭넓은 probing
• 단점: 선형 탐사와 마찬가지로, 초기 해시값이 같을 경우 클러스터링 문제가 발생함

Double Hashing(이중 해싱)

• 클러스터링 문제를 모두 피하기 위해 도입된 것
• 서로 다른 두개의 해시 함수를 이용함
• → 첫번째 해시 함수: 해시 값을 구함
• → 두번째 해시 함수: 해시 충돌이 났을 경우, 탐사 폭을 구함

 

해시 충돌의 문제가 있음에도 해시 테이블을 쓰는 이유는 ?

• 많은 양의 데이터를 빠르게 탐색할 수 있기 때문 → 해시 충돌이 없으면 O(1)의 시간으로 탐색 가능
• 적은 자원으로 많은 양의 데이터를 효율적으로 관리할 수 있기 때문
• 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다!