Hash?
해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꾸는 것
| 용어 | 설명 |
|---|---|
| 해시함수(hash function) | 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 |
| 키(key) | 매핑 전 데이터의 값 |
| 해시값(hash value) | 매핑 후 데이터의 값 |
| 해싱(hashing) | 매핑하는 과정 |
| 해시테이블(hash table) | 해시함수를 사용하여 키를 해시값으로 매핑하고,이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조 |
| 값(value) | 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야함 |
- key가 해시기반이 되기 때문에 중복된 key로 저장하지 못 한다. 만약 중복된 키가 있다면 새로운 값이 기존 값을 치환한다.
- key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간복잡도가 O(1)에 수렴하게 된다. 하지만 O(n)이 될 수 있다. 해시충돌로 인해 모든 value를 찾아봐야하는 경우도 있기 때문이다.
- 다양한 길이의 키를 일정한 길이를 가지는 해시값으로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다.
- hash 자료구조의 단점
- 순서가 있는 배열에는 어울리지 않는다.
- 데이터가 저장되기 전에 미리 공간을 확보해놓아야하기 때문에 공간 효율성이 떨어진다.
- hash function의 의존도가 높다. 해시함수가 매우 복잡하다면 해시테이블의 모든 연산의 시간 효율성은 증가할 것이다.
해시 충돌(hash collision)이란?
- 서로 다른 key에 대해 동일한 해시값을 내는 경우를 말한다.
- 예 : 생일문제
해시 충돌 해결 방법
1. Separate Chaining (분리 연결법)
위 이미지를 보면 sandra가 들어가는데 충돌이 일어나 기존에 있던 john에게 연결시켰다.
Separate Chaining은 자료 저장시, 충돌이 일어나면 해당 값을 기존 값과 연결시키는 방법이다.
이때는 연결리스트(linked list)를 이용한다.
- 장점 : (linked list 특성때문에) 한정된 저장소를 효율적으로 사용할 수 있다.
- 단점 : (linked list 특성때문에) 한 해시에 자료들이 계속 연결된다면 검색 효율을 낮출 수 있다. 외부 저장 공간을 사용하며, 외부 저장 공간 작업을 추가로 해야한다.
2. Open Addressing(개방주소법)
비어있는 해시를 찾아 데이터를 저장하는 방법이다. 따라서 개방주소법에서 해시테이블은 1개의 해시와 1개의 값이 매칭된다.
위 그림을 보면 sandra가 저장될 때 해시가 john으로 채워져 있어 그 다음 해시에 저장했고, ted도 해당 해시에 sandra가 저장되어 있어 그 다음에 저장하였다.
- 이 때 비어있는 해시를 찾는 과정은 동일해야 한다.
- 해시를 찾는 규칙
- 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장한다.
- 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
- 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.
- 장점 : 또 다른 저장공간없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다
- 단점 : 해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지 된다.
데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.
이렇게 충돌 해결을 한다고 해도 결과적으로 충돌로 인한 성능 저하는 막을 수 없다. 그래서 수용률이 일정량을 넘어가게 되는 경우에는 아예 리스트 자체의 크기를 키운 뒤에 재배열을 하는 방법을 사용한다. 다만, 이 과정 자체가 상당히 비용이 많이 드는 과정이라서 실시간으로 빠르게 처리해야되는 환경에서는 무리가 있을 수 있다. 이럴 때는 큰 리스트를 하나 더 만들어서 적당한 타이밍에 몇 개씩 점진적으로 옮기다가 다 옮기면 기존의 테이블을 없애 확장하는 방식도 있기는 하다. 다만 이 경우에는 메모리를 훨씬 더 많이 사용하게 된다.
또는 해시의 비트수를 늘이는 방법도 있다. 항목 수가 적을 때에는 짧은(적은 비트 수) 해시와 작은 저장공간를 사용하다가 충돌이 잦아지면 비트수를 1비트 늘이고 저장공간도 2배로 늘인다. 그리고 항목을 점진적으로 확장된 공간으로 이전하게 함으로써 충돌을 줄일 수 있다. Consistent hashing 이라고 하며 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 사용되고 있다.
자료를 기본적으로 정렬하지 않은 상태로 저장하기 때문에 정렬된 순서로 접근하는 것은 비용이 매우 많이 들며 순회를 하는 경우에도 무효한 값들이 많아 실제 데이터의 개수만 순회하는 것보다 더 많은 비용이 들게 된다. 그리고 부하의 임계점을 적으면 50%, 많아봐야 75% 정도로 잡기 때문에 실제 데이터의 양보다 메모리를 많이 쓰게 된다.
