해쉬(Hash) 알고리즘 파헤치기
저번 글에 이어 오늘도 알고리즘에 대한 글을 써보려고 한다!
오늘의 주제는 해시(Hash)이다.
해시 함수
해쉬 함수는 다양한 길이를 가지고 있는 key를, 일정한 길이의 해시로 바꿔주어(key의 길이 > hash의 길이) 공간을 효율적으로 관리할 수 있도록 하는 함수이다.
해시 충돌(Hash Collision)을 최소화 하는 해시 함수를 만드는 것이 중요하다.
해시
해시 함수의 결과 값을 의미한다.
저장소(bucket)에서, 값(value)와 매칭되어 저장된다.
해시 함수에 key를 적용해 나온 결과인 해시를 버킷 배열의 인덱스로 하고, 그 자리에 value를 저장한다.
해시 테이블
해시 테이블이란, (key, value)의 형태로 데이터를 저장하는 자료구조이다. Hash map, map, dictionary, 연관배열 등의 이름으로도 알려져 있다.
해시 함수에 key를 적용해 나온 결과(= 해쉬)를 배열(버킷)의 인덱스로 하고, 그 자리에 value를 저장하게 되는 것이다.
해시 충돌이 일어나지 않는 경우, 해시테이블의 시간 복잡도는 O(1)이다.
해시 충돌
서로 다른 키가 같은 해시 값을 가지는 경우를 말한다.
ex) “Sam Smith”와 “Emily Kim” 을 해시 함수에 넣었을 때 같은 결과가 나오는 경우
해시 충돌의 해결법
해시 충돌의 해결법에는 Chaining과 Open Addressing 두 가지가 있다.
Chaining(체이닝)
해시 충돌이 일어났을 때 이를 동일한 버킷에 저장하는데, 이를 연결리스트 형태로 저장하는 방법을 말한다.
시간 복잡도
- 탐색 / 삭제는 키에 해당하는 리스트의 길이에 비례함, 최악의 경우 O(K)가 된다. (이때 K는 키 값의 갯수를 의미한다.)
- 삽입은 O(1)
Open Addressing
해시 충돌이 일어날 경우, 저장소의 다른 주소도 이용할 수 있게 하는 방법이다.
ex) “Sandra Dee”라는 키에 대해 해시 함수를 적용한 결과 152가 나왔다. 그렇지만 152번은 이미 다른 키에 의해 사용되고 있는 공간이다. 따라서 그 다음 비어있는 주소인 153에 저장한다.
시간 복잡도
- 탐색, 삽입, 삭제 모두 최상의 경우 O(1), 최악의 경우 O(n)
장점
- 다른 저장공간 없이 해시테이블 내에서 데이터 저장이 가능하다
단점
- 해시함수의 성능에 따라 해시 테이블 전체의 성능이 좌지우지된다.
- 데이터의 양이 늘어나면 그에 해당하는 크기의 저장소를 미리 확보해두어야 한다.
Open Addressing에서는, 저장소가 어느정도 채워졌을 때, 저장소의 크기를 늘리는 것이 중요하다
Open Addressing의 3가지 충돌 해결 기법
- Linear Probing(선형 탐사)
그 다음으로 비어있는 인덱스에 데이터 삽입하는 방법이다.
배열의 끝까지 갔는데 빈 공간을 찾지 못한 경우, 맨위부터 다시 탐색한다.
단점 : 바로 인접한 인덱스에 데이터를 삽입하기 때문에, 데이터가 밀집되는 클러스터링(Clustering) 현상이 발생 가능하다. (탐색 시간이 클러스터링의 크기만큼 길어지게 된다.)
2. Quadratic Probing(제곱 탐사)
배열을 하나씩 이동하며 인접한 빈 공간부터 탐색하는 선형 탐사 방식과 달리, 1², 2², 3², 4² 의 순으로 배열을 건너 뛰며 빈공간을 탐색하는 방식이다.
더욱 폭넓은 probing이 가능하다.
단점 : 선형 탐사와 마찬가지로, 초기 해시값이 같을 경우 클러스터링 문제가 발생한다.
3. Double Hashing(이중 해싱)
클러스터링 문제를 모두 피하기 위해 도입된 방법이다.
서로 다른 두개의 해시 함수를 이용한다.
첫번째 해시 함수 -> 해시 값을 구한다.
두번째 해시 함수 -> 해시 충돌이 났을 경우 탐사 폭을 구한다.
해시 충돌의 문제가 있음에도 해시 테이블을 쓰는 이유는 ?
- 많은 양의 데이터를 빠르게 탐색할 수 있기 때문이다.
-> 해시 충돌이 없으면 O(1)의 시간으로 탐색 가능
2. 적은 자원으로 많은 양의 데이터를 효율적으로 관리할 수 있기 때문
-> 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다고 한다.
