Hash Function
key를 고정된 길이의 hash로 변경해주는 역할을 하는 함수. 이 과정을 hasing이라고 한다.
Hash Table
해시함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조
- 삽입, 삭제, 탐색의 기본 연산을 가진다.
- key를 통해 value를 얻을 수 있다. (탐색속도가 빠르다)
- 데이터가 저장되는 곳을
버킷혹은슬롯이라고 한다.
장점
key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있다.
단점
- 해시 충돌이 발생할 수 있다.
- 순서, 관계가 있는 배열에는 어울리지 않는다.
순서에 상관없이 key만을 가지고 삽입, 검색, 삭제하기 때문이다.
- 공간 효율성이 떨어진다.
데이터가 저장되기 전에 미리 저장공간을 확보해야하기 때문이다.
- hash function의 의존도가 높다.
평균 시간복잡도가O(1)이지만 해시함수가 복잡하다면 해시테이블의 연산 속도가 증가한다.
Hash Table의 크기
키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 한다.
키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않는다는 장점이 있다.
하지만 실제로는 극히 일부분의 키만 사용한다고 한다면, 전체 키의 개수와 테이블의 크기가 같은 것은 메모리 낭비이다.
따라서 보통의 경우 실제 사용하는 키 개수보다 적은 해시테이블을 운용한다고 한다. 그렇기에 해시 충돌이 발생할 수 밖에 없다.
해시 충돌(Hash Collision)
서로 다른 key가 같은 해시로 변경되면서 같은 공간에 2개의 value가 저장되어야 하는 상황
1. Chaining
체이닝은 저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트를 이용해 연결시키는 방법이다.
장점
한정된 저장소를 효율적으로 사용할 수 있다.
- 미리 충돌을 대비해 많은 공간을 잡아놓을 필요가 없다.
해시 함수를 선택하는 중요성이 상대적으로 적다.
- 충돌이 나도 연결을 통해 간단하게 해결이 가능하기 때문.
단점
같은 hash에 자료들이 많이 연결되면 검색 효율이 낮아진다.(쏠림 현상)
2. Open Addressing(개방주소법)
충돌이 발생하는 경우 비어있는 hash를 찾아 데이터를 저장하는 기법. 비어있는 hash를 찾아가는 방법은 여러가지가 있다.
1. 선형 탐색(Linear Probing)
해시값에서 고정폭(+n)으로 건너뛰면서 비어있는 해시가 나오면 저장
특정 해시값 주변 버킷이 모두 채워져있는 primary clustring 문제에 취약하다.
2. 제곱 탐색(Quadratic probing)
충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장
여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약하다.
3. 이중 해싱
다른 해시함수를 한번 더 적용해 나온 해시에 데이터를 저장
이중해싱을 하면 최초 해시밧이 달라지므로 탐사 이동폭이 달라지고, 이동폭이 같더라도 최초 해시값이 달라져 primary clustering, secondary clustering을 완화시킬 수 있다.
장점
또 다른 저장공간 없이 해시 테이블 내에서 데이터의 저장 및 처리가 가능
단점
해시함수의 성능에 따라 해시테이블이 성능이 좌우된다.
데이터의 길이가 늘어나면 그에 해당한느 저장소를 마련해두어야 한다.
해시함수 매핑 개선
특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라고 할 수 있다.
Division Method
- 숫자로 된 키를 해시테이블의 크기 m으로 나눈 나머지를 해시값으로 변환한다.
- 간단하면서 빠른 연산이 가능하다.
- 해시의 중복을 방지하기 위해 테이블의 크기 m은 소수로 지정해서 사용하는 것이 좋다. 하지만 남는 공간이 발생하기 때문에 메모리상으로 비효율적이다.
Multiplication Method
- 숫자 키 k, A는 0과 1 사이의 실수일 때,
h(k) = (kA mod 1) x m - 2진수 연산에 최적화된 컴퓨터구조를 고려한 해시함수라고 한다. 나눗셈법보다는 다소 느리다.
Universal Hashing
- 다수의 해시함수를 만들고, 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법.
- 서로 다른 해시함수가 서로 다른 해시값을 만들어내기 때문에 같은 공간에 매핑할 확률을 줄이는 것이 목적
