해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 이 고정된 길이는 해시 함수마다 다릅니다. 하지만 동일한 해시 함수는 동일한 길이의 데이터를 출력합니다.
아래 그림과 같이, data를 hash function에 입력하면, 이 함수는 고정된 길이의 값을 출력합니다. 해시 함수에 의해 얻어지는 값을 해시 값(Hash value) 이라고 합니다.
해시 함수의 특징
해시 값은 항상 고정된 길이의 값을 가집니다.(위 설명 참고)
같은 입력값이면 해시 값은 항상 동일합니다.
다른 입력값일 때, 1bit만 다르더라도 해시 값은 크게 달라질 수 있습니다.
다른 입력값일 때, 같은 해시 값을 가질 수도 있습니다. (해시 충돌)
해시 값이 다르다면, 원래 입력값은 항상 다릅니다. (역은 성립 X)
해시 값을 원래 입력값으로 복원하는 것은 현실적으로 불가능합니다. (일방향성)
Encryption과의 큰 차이점 중 하나입니다.
해시 함수의 계산은 상대적으로 간단한 편입니다.
해시 함수의 대표적인 예는 아래와 같습니다.
MD4
MD5
SHA-0
SHA-1
SHA-2 (대부분 사용하는 알고리즘)
Hash Table
위에서 배운 해시 값의 용도 중 하나를 해시 테이블(Hash Table)이라는 자료구조에서 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에도 널리 사용됩니다.
해시 테이블은 key와 value로 이루어진 pair 값을 저장하는데 좋은 자료구조로 key를 통해 평균 O(1)에 value를 검색할 수 있습니다.
위 자료를 배열에 넣기 위해 Hash Table에서는 Key 값을 Hash Function에 input으로 넣어 출력된 Hash Value를 배열의 인덱스로 사용하여 데이터를 관리합니다.
예를 들어, Joe를 아래와 같이 Hash Function에 넣었더니 3이라는 출력값이 나왔을 때, 배열에서 인덱스가 3인 곳에 Joe의 Value인 M을 저장하게 됩니다.
위 과정을 모든 데이터에 대해 반복하여 배열에 저장을 하면 Hash Table을 완성할 수 있습니다.
해시 충돌
위와 같이 모든 데이터에 대해서 해시 값을 구하여 배열에 저장을 하다가, 다른 key 값을 가짐에도 불구하고 동일한 해시 값이 나올 수 있습니다, 이런 경우를 해시 충돌이라고 하는데, 이를 해결하는 방법은 크게 2가지가 있습니다.
Chaining
체이닝 방법은 해시 충돌 시, 연결 리스트에 추가하는 방식입니다. 즉, 아래와 같이 데이터를 저장합니다.
이렇게 추가하면, 해시 테이블의 크기가 너무 작을 경우, 해시 충돌이 빈번하게 발생하여 최악의 경우 데이터 탐색 수행 시간이 O(N)이 됩니다. 해시를 이용하는 이유는 O(1)이라는 장점으로 사용하는 것인데, O(N)이 된다면 문제가 될 수 있으므로 이런 경우 연결 리스트 대신 트리로 구성하여 더 시간 복잡도를 줄일 수도 있습니다.
반대로, 해시 테이블의 크기가 너무 클 경우, 해시 테이블(배열) 내부에 저장되지 않은 공간이 많아 메모리를 낭비하게 됩니다. 따라서 적절한 해시 테이블의 크기를 설정하는 것이 중요합니다.
또한, 해시 테이블의 크기는 보통 소수로 하는 것이 정석이라고 합니다. 체이닝은 복잡한 계산식을 사용할 필요가 없고, 삭제 또는 삽입이 용이합니다.
Open Addressing
오픈 어드레싱 방식은 충돌을 피하기 위한 다른 방법으로, 충돌 발생 시 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장합니다. 즉, 아래와 같이 해시 충돌이 발생했을 경우 다른 값이 나올 때까지 해시 함수를 통해 해시 값을 산출합니다.
해시 충돌이 해결되어 아래와 같이 연결 리스트 방식이 아닌 다른 공간에 데이터를 저장하게 됩니다.
오픈 어드레싱 장점은 포인터를 사용하지 않아도 되어서 구현이 간편하며, 추가적인 저장공간이 필요 없고, 검색도 미세하게 빨라진다고 합니다.
오픈 어드레싱 방식에는 3가지가 있습니다. 아래 수식에서 m은 해시 테이블의 크기를, k는 key를, i는 충돌 횟수를, h()는 해시 함수를 의미합니다.
선형 프로빙 (Linear probing): 해시 충돌 시 고정된 폭만큼 옮겨 다음 빈 공간을 찾아 데이터 삽입선형 프로빙은 구현은 쉬우나 primary clustering 문제가 있습니다. 즉, 한 번 충돌이 발생하면 집중적으로 충돌이 발생하는 것으로 이로 인해 평균 검색 시간이 증가합니다.
이차식 프로빙 (Quadratic probing): 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터 삽입이차식 프로빙은 선형 프로빙에 비해 충돌이 적지만 secondary clustering이 발생한다. secondary clustering은 처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게 된다는 것입니다.
이중 해시(Double hasing): 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용
이중 해시는 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m 만큼 이동하면서 탐색합니다. 충돌 발생 가능성은 가장 작지만, 추가적인 해시 연산이 들어가서 가장 많은 연산량을 요구한다는 단점이 있습니다.
해시 함수 및 해시 테이블 구현
아래 코드는 C언어로 구현한 해시 함수입니다. 해시 함수를 위한 변수 hash 값과 Hash Table 크기는 2의 제곱수에서 가장 거리가 먼 소수로 지정하는 것이 성능이 좋다고 알려져 있습니다. (참고: https://code-lab1.tistory.com/271)
저장할 데이터의 총 개수보다 큰 소수들 중 가장 작은 값으로 설정하는 것이 충돌 발생이 작고 메모리도 효율적으로 사용할 수 있을 것 같습니다. (경우마다 달라서 여러 경우를 테스트해보는 것이 좋습니다.)
#define MAX_KEY 64
#define MAX_TABLE 6151
typedef unsigned long ul;
ul hash(const char *str)
{
ul hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % MAX_TABLE; // 해시 함수
}
return hash % MAX_TABLE;
}
1. 체이닝 방식
// word를 key로 하는 hash 리스트
typedef struct st
{
char word[MAX_KEY]; // hash 키
struct st *next;
}HASHTABLE;
//메모리 풀
HASHTABLE hashTable[MAX_TABLE];
HASHTABLE POOL[4050]; // 입력 크기
int pcnt;
Hash 값 존재 여부 구현
int isExist(char* word)
{
ul h = hash(word);
for (HASHTABLE *p = hashTable[h].next; p; p = p->next)
if (strcmp(p->word, word) == 0) return 1;
return 0;
}
