해시 Hash 자료구조

해시의 목적

해시 테이블의 가장 큰 목적은 O(1)로 찾고자 하는 데이터를 찾는 것이다.

search의 시간 복잡도가 O(1)이 되는 것. 고정된 길이의 데이터로 매핑하는 것이고, 일반적으로 해싱에 쓰이는 메모리는 매우 비싸다. 

 

해시는 index을 통해서 Random access가 가능하다. 이를 위해선 index가 어디있는지를 알아야 하며, 해당 index는 해시 함수(해시 알고리즘으로 index값을 계산해주는 알고리즘이다.)을 통해서 알 수 있다. 

 

해시의 개념

해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑전 원래 데이터의 값을 Key라고 하고, 매핑 후 데이터의 값을 해시값(value)라고 한다. 매핑하는 과정 자체를 hashing한다고 한다. 

 

해시 함수는 해시 값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many to one)하기 때문에 해시함수가 서로 다른 두개의 키에 대해 동일한 해시값을 내는 해시충돌(hash collision)이 발생한다. 

데이터를 키우면 되지 않느냐고 말을 할 수 있지만, 해시에 사용되는 캐시 메모리가 비싸다고 한다. 

 

아무튼, 많은 데이터를 유한한 개수의 해시값으로 매핑함으로써, 삽입, 삭제, 탐색의 모든 계산 복잡성을 O(1)을 지향한다고 한다. 

 

해시 충돌 문제 해결법:

- chaining: 유연하다는 장점이 있으나 메모리 문제를 야기할 수 있다는 단점이 있다. 

해시테이블의 개수가 m이고 실제 사용하는 데이터 개수가 n이면 평균 개수는 n/m이 된다. 버킷 하나당 n/m개를 갖게 된다. 

따라서 평균적인 탐색의 시간복잡도는 O(1 + n/m)이 된다. 

문제점: Worst Case로 모든 n이 한개의 버킷에 쏠리면 시간 복잡도는 O(n)이 될 수 있다.

- open addressing:

chaining과 달리 버킷당 엔트리가 하나뿐이다. 

7로 나눈 나머지로 mapping중이다. 85를 insert하는 시점에 50과 충돌한다. 이경우 다음 빈 버킷에 저장해 둔다. 

다음의 빈 버킷에 저장하는 것을 open addressing이라고 한다.

또 18번을 삭제한다고 했을 때, 그냥 삭제하면 26번을 탐색할 수 없어진다. 이를 위해 DEl 표시를 남긴다. 

 

- probing: 

open addressing은 특정 해시값에 키가 몰리게 되면 open addressing의 효율성이 떨어진 다는 것이다. 이를 위해 probing이라는 기법이 도입되었다. 

Linear probing과 Quadratic probing, 이중해싱 기법이 존재한다. 

Linear probing은 open addressing과 고정폭으로 증가한다는 것의 차이점이 있다. k씩 증가하느냐와 1씩 증가하느냐의 차이이다. 

Quadratic probing은 고정폭이 아닌 제곱 폭으로 증가한다. 데이터 충돌이 일어 났을 때 1, 2^2, 3^2 씩 증가하면서 데이터를 탐사한다.

이중 해싱: 2개의 해시함수를 준비하여, 충돌이 나게 될경우 나머지 해시함수를 통해 탐사 이동폭을 얻는다. 

 

계산 복잡성: 

open addressing은 chaining과 달리 Load Factor인 n/m이 1보다 작거나 같다 .

 

해시 함수:

해시 함수를 통해 해시충돌을 완화시키는 방법을 찾아보자. 충돌이 나지 않게 최대한 고르게 분포시키는 함수가 좋은 함수이다. 

 

division method: 

나눗셈법으로 해시 테이블 크기(m)으로 나눈 나머지를 해시 값으로 반영한다. m은 대개 소수가 좋다고 한다.

 

multiplication method:

h(k) = (kA mod 1) * m이다. 키가 k이고 A는 0과 1 사이의 실수이다. m은 상수이다. 

잘쓰이지 않는 방법이다.

 

Resizing:

해시 테이블의 크기를 동적으로 변경시키기도 한다.

해시 함수도 다시 구성되고, 해당 함수를 이용하여 기존 값들을 재배치한다.

 

 

해시 함수의 이용 예시:

OS, DB, 캐시 메모리, HashMap(코딩할 때 사용하는 거) 등등.