[자료구조] Hash, Hashing, Hash Table(해시, 해싱, 해시 테이블)

[자료구조] Hash, Hashing, Hash Table(해시, 해싱, 해시 테이블)

 

해시

사전적 의미 : 잘게 썲

• 임의의 크기를 가진 데이터 key를 고정된 크기의 데이터 value로 변화시켜 저장하는 것이다.
• 키에 대한 해시값을 사용하여 값을 저장하고 key-value 쌍의 개수에 따라 동적으로 크기가 증가하는 연관배열이다.
• key에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며, 이때 사용하는 함수(알고리즘)를 해시함수라 한다.
• 해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다.

 

 

직접 주소 테이블(Direct Address Table)

• 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다.
• 이렇게 직접 주소 테이블은 값에 접근하기는 편하지만, 공간 효율이 좋지 않다는 단점이 있다. 그래서 이 단점을 보완한 게 바로 해시 테이블이다.
• 즉, 고정된 길이의 데이터로 매핑하는 매핑함수를 사용하여 해시 테이블은 공간 효율을 높인다.

 

 

해시 테이블(Hash Table)

해시 테이블은 연관배열 구조를 이용하여 키(Key)에 결과 값(value)을 저장하는 자료구조이다.

해시 : 잘게 썰었다는 사전적 의미를 가지고 있고, 

연관배열구조(Associative array) : 키 1개와 값 1개가 1:1로 연관되어 있는 자료구조

해시 함수 : key를 

 

 

 

 

해시 테이블 구조

 

 

 

 

 

Hash Collision(해시 충돌)

해시 테이블은 Insertion, Deletion, Search 모두 평균 O(1)의 시간복잡도를 갖고 있어 매우 우수하다.

하지만 해시 값이 충돌을 일으키는 경우가 발생할 수 있다.

 

John과 Sandra의 hash가 같다. 이런 현상을 hash collision이라 한다.

이를 해결하는 방법은 2개의 방법이 존재한다.

 

1. Chaining
2. Open Addressing(개방주소법)

 

 

 

 

1. Chaining

Sandra가 충돌을 일으켜 기존에 있던 John의 값에 연결하였다.

이는 연결리스트 자료구조를 이용한다.

 

장점

• 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
• 해시 함수를 선택할 때 hash collision을 걱정하지 않아도 된다.
• 상대적으로 적은 메모리를 사용한다. (미리 공간을 잡을 필요가 없다.)

 

단점

• 한 Hash에 자료들이 계속 연결된다면 쏠림 현상으로 검색 효율을 낮출 수 있다.
• 외부 저장 공간을 사용

 

Chaining 시간복잡도

해시 테이블의 저장소(Bucket)의 길이 n, 키(key)의 수를 'm'이라 가정했을 때, 평균적으로 저장소에 1개의 hash당 (m/n)개의 키가 들어있다.

m/n = α (1개의 Hash당 평균적으로 α개의 키가 들어있다)

 

Insertion

충돌시 해당 해시(Hash)가 가진 연결리스트의 Head에 자료를 저장할 경우, O(1)의 시간복잡도를 가진다.

반면 Tail에 저장할 경우, O(α)의 시간 복잡도를 가진다.

최악의 경우 한 해시에 모든 자료가 연결되어 O(n)을 가진다.

 

Deletion & Search

삭제와 검색은 시간 복잡도 측면에서 비슷하다. Hash의 연결리스트를 차례로 살펴보아야하므로 O(α)의 시간복잡도를 가진다. 최악의 경우 O(n)의 시간복잡도를 가진다.

 

 

 

2. Open Addressing(개방주소법)

개방주소법은 해시 충돌이 발생할 경우 비어있는 해시(Hash)를 찾아 데이터를 저장한다.

아래 그림에서 Sandra가 저장될 때 해시가 John으로 채워져 있으므로 그 다음 Hash에 저장했다. 그 후 Ted의 해시도 Sandra가 저장되어 있으므로 그 다음 해시에 Ted를 저장했다.

 

이 때, 비어있는 해시(Hash)를 찾는 과정은 동일해야한다.

해시를 찾는 규칙은 다음과 같다.

1) 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장
2) 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
3) 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.

 

장점

• 추가 저장 공간이 필요 없다.

 

단점

• 해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지된다.
• 데이터 길이가 늘어나면 그에 해당하는 저장소를 마련해야한다.

 

 

Chaining 시간 복잡도

 

Insertion & Deletion & Search

삽입, 삭제, 검색 모두 hash를 찾아가는 과정에 따라 시간복잡도가 계산된다.

Hash가 비어있지 않으면 다음 버킷을 찾아야한다. 이 횟수가 많아질수록 시간복잡도는 증가한다.

최상의 경우 O(1), 최악의 경우O(n) - 저장소 모두를 확인

 

따라서 저장소가 어느 정도 채워졌을 때 저장소의 사이즈를 늘려 비어있는 공간을 확보하는 것이 필요하다.

 

 

 

 

Hash Table Data Structure의 단점

• 순서가 있는 배열에 적합하지 않다.
• 공간 효율성이 떨어진다. - 미리 저장공간을 확보해 놓아야 한다. 공간이 부족하거나, 아예 채워지지 않은 경우가 생길 수 있다.
• Hash Function의 의존도가 높다. - 평균 시간복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않은 결과이다 해시함수가 복잡하다면 해시테이블의 모든 연산의 시간 효율성은 증가할 것이다.