해시 테이블, 해시 함수, 해시 충돌과 해결방법

해시란?

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키(key)를 활용해 데이터 탐색을 빠르게 한다. 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다. 키와 대응한 값이 저장되어 있는 공간을 해시 테이블(Hash Table)이라 하며, 해시 테이블의 각 데이터를 버킷(Bucket)이라고 부른다.

 

해시의 특징

1. 해시는 단방향으로 동작한다. 즉, 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수 없다.
2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.
3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.
4. 해시는 데이터를 저장하고 검색하거나, 보안이 필요할 때 주로 활용된다. (비밀번호 관리, 데이터베이스 인덱싱, 블록체인, ...)

 

해시 테이블(Hash Table)이란?

해시 테이블은 key-value 형태로 데이터를 저장하는 자료구조이다. key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용하여 value를 찾는 방식으로 동작한다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷 또는 슬롯)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블의 평균 시간복잡도는 O(1)이다.

 

 

해시 함수(Hash Function)이란?

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 실제로 자주 사용하는 해시 함수를 알아보자.

1. 나눗셈법(Division Method) 
   • 나눗셈법은 키를 소수로 나눈 나머지를 인덱스로 사용한다.
   • 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시한다. 예를 들어, 7%2 = 1 이다.
   • 수식 : h(x) = x mod k     (x : 키, k : 소수)
   • 소수를 사용하는 이유는 다른 수를 사용할 때보다 충돌이 적기 때문이다. 예를 들어, k에 소수가 아닌 15를 적용하면 x가 3의 배수인 경우 규칙적으로 계속 같은 해시값이 반복된다. 이렇게 되면 해시값이 충돌된다. 따라서, k는 1과 자신 빼고는 약수가 없는 수, 즉, 소수를 사용하는 것이 좋다. 
   • 단점 : 나눗셈법은 해시 테이브르이 크기가 자연스럽게 k가 된다. 왜냐하면 k에 대해 모듈러 연산을 했을 때 나올 수 있는 값은
     0~(K-1)이기 때문이다. 상황에 따라 많은 데이터를 저장해할 때, 매우 큰 소수를 구하는 효율적인 방법이 아직 없다
2. 곱셈법(Multiplicaion Method)
   • 곱셈법은 황금비를 사용하므로 나눗셈법처럼 소수가 필요 없다는 장점이 있다. 따라서, 해시 테이블의 크기가 커져도 추가 작업이 필요 없다.
   • 수식 : h(x) = (((x * A) mod 1) * m)     (A : 황금비, m : 최대 버킷의 갯수)
     • 황금비는 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율과 같은 비율을 뜻한다. 황금비는 무한소수로 대략 1.6180339887.. 이다.
3. 문자열 해싱
   • 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수이다.
   • 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.
   • 1단계 다음 그림은 알파벳 a부터 z까지 숫자와 매치한 표와 키이다.
   • 2단계 “a”는 매치 표를 보면 1이다. 따라서 “apple”의 “a”는 1이다. 그러므로 수식의 s[0] * p0는 1 * 1이므로(31의 0승은 1입니다) 1이다.
   • 3단계 두 번째 문자열 “p”에 대해 연산을 진행한다. “p”는 16이다. 여기에 p1을 곱하면 496이다.
   • 4단계 이렇게 곱한 값들을 더하면 최종값은 4,990,970이다. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 된다.

문자열 해싱 - 1단계

문자열 해싱 - 2단계

 

문자열 해싱 - 3단계

 

문자열 해싱 - 4단계

 

•  키가 문자열이면 각 문자열의 문자들을 적절한 숫자로 변경한 다음 해시 함수를 적용해야 한다. 이런 변환 과정을 통해 문자열이 키인 데이터에도 해시를 사용할 수 있다. 하지만 해시 함수를 적용한 값이 해시 테이블 크기에 비해 너무 클 수 있다. 그래서 해시 함수가 내는 결과의 크기를 해시 테이블 크기에 맞도록 하는 작업이 필요하다. 그림을 보면 “apple”이라는 간단한 문자열을 해싱했는데도 결괏값은 4,990,970으로 굉장히 크다. 오버플로가 발생시킬 여지가 있으므로 다음 연산 법칙을 활용해 문자열 해시 함수를 수정할 수 있다.

 

3-1. 문자열 해시 함수 수정하기

덧셈을 전부한 다음 모듈러 연산을 하는 왼쪽 수식 대신, 오른쪽 수식처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있다.  (두 수식의 실제 결과는 같다.)

이를 활용해서 앞서 본 문자열 해싱 공식을 수정하면 다음과 같다.

해시 함수뿐 아니라 보통 수식에 모듈러 연산이 있는 문제 중 큰 수를 다루는 문제는 이런 오버플로 함정이 있는 경우가 많다. 

 

해시 충돌

서로 다른 두 개의 key가 동일한 hash 값을 갖는 경우 "해시 충돌" 이라고 한다. 해시 충돌을 해결하는 방법은 Chaining과 Open Addressing 방법이 있다.

 

1. 체이닝(Chaining) 기법

버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화하는 방법이다.

  

중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다. 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다. 해시를 사용하는 이유는 O(1)이라는 장점으로 사용하는 것인데 O(n)이 된다면 문제가 된다. 이런 문제로 트리로 구성하여 더 시간 복잡도를 줄일 수도 있다.

참고로, 자바에서 HashMap 클래스는 체이닝을 사용하여 해시 충돌을 처리한다. 다만, 충돌 발생 시 데이터 접근 시간 복잡도가 O(N)으로 늘어나는 무넺가 있으므로 링크드리스트로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 링크드리스트를 이진 탐색 트리로 변환하여 데이터 접근에 O(logN)의 성능이 나오도록 개선한다.

 

2. 개방 주소법(Open Addressing) 기법

충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.

개방 주소법은 충돌을 피하기 위해 빈 버킷을 찾아 충돌값을 삽입한다.. 오픈 어드레싱의 장점은 포인터를 사용하지 않아도 되어 구현이 간편하며, 검색도 미세하게 빨라진다. 또, 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다. 오픈 어드레싱은 총 3가지 종류가 있다.

 

2-1. 선형 탐사법(Linear probing)

선형 탐사법은 충돌이 발생할 경우 빈 slot이 나올 때까지 탐색 후, 빈 slot이 나오면 위치가 결정된다. 선형 탐사법은 아래와 같은 해시 함수가 사용된다. 여기서 k는 키, i는 충돌 횟수, h()는 해시 함수, m은 해시 테이블 크기를 의미한다.

- 장단점 : 선형 탐사법의 장점은 구현은 매우 쉬우나 1차 군집 현상(primary clustering) 문제가 있다. 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생긴다. 이를 클러스터를 형성한다고 한다. 이로 인하여 평균 검색 시간이 증가한다. 따라서, 해당 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용하다.

 

2-2. 제곱 탐사법(Quadratic probing)

제곱 탐사법은 선형 탐사법처럼 한 칸씩 찾는 것이 아닌 제곱으로 늘리면서 빈 버킷을 찾는다. 제곱 탐사법은 아래와 같은 해시 함수를 사용한다. i에 대한 2차 함수 꼴로 slot을 이동하면서 빈 슬롯을 찾는다. 여기서 h는 보조 해시 함수, c1와 c2는 0이 아닌 상수이다.

- 장단점 : 제곱 탐사법은 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 역역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있다. 선형 탐사법에 비해 충돌이 적지만 secondary clustering이 발생한다. secondary clustering은 처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게 된다는 의미이다. 즉, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수 밖에 없어 비효율적인 상황이 발생할 수 있다.

 

2-3. 이중 해시(Doubld hasing)

이중 해싱은 해시 충돌이 발생하는 경우, 보조 해시 함수를 사용하는 방법이다. 이중 해시는 다음과 같은 형태의 해시 함수를 사용한다. 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m 만큼 이동하면서 탐색한다.

- 장단점 : 이중 해싱 방법은 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구된다.

 

[참고]

도서 - 코딩 테스트 합격자 되기(김희성 지음)

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

https://ryu-e.tistory.com/87

해시(Hash)와 해시 충돌 해결 방법