단순하게 데이터를 찾는다고 하면 순차 탐색을 생각할 수 있는데요. 이는 최악의 경우 모든 데이터를 살펴봐야 하기에 대용량 데이터를 다루기에는 적절하지 않죠.

어떠한 값이 저장되는 위치를 어떤 규칙으로 정한다면 바로 접근해서 찾아낼 수 있을 텐데요. 이런 개념으로 탄생한 자료구조가 hash 입니다.

hash는 JS에서 Object로 쉽게 쓸 수 있지만 내부적으로는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아서 키, 값으로 저장하는 방식으로 구현되어 있는데요. 더 자세하게 알아봅시다.

INFO

해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있습니다.

개념

해시는 우리의 일상 생활에서 정말 많이 사용하는 자료구조에요. 연락처는 이름 이라는 key에 대응되는 번호 라는 value 를 가진 hash로 볼 수 있죠. hash에서 key를 갖고 value를 찾기 위해서는 중간에 key를 해시값 또는 인덱스로 변환해주는 해시 함수가 필요합니다. 해시 함수에 대한 설명은 아래에서 더 자세히 하겠습니다. 우선 특징부터 살펴봅시다.

특징

1. 해시는 단방향으로 동작합니다. 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없습니다.
2. O(1)의 시간 복잡도로 찾고자 하는 값을 바로 찾을 수 있습니다. 해시 함수에 의해서 key 자체가 인덱스가 되서 탐색 과정이 필요 없는 것이죠.
3. 값을 인덱스로 사용하려면 적절한 변환 과정을 거쳐야 합니다.

단방향으로 동작하는 해시

단방향으로만 동작하는 해시는 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용됩니다.

이름에 맞는 전화번호를 찾아야 할 때 hash가 없다고 해봅시다. 해시를 사용하지 않으면 위의 사진처럼 모든 배열을 순차 탐색해서 해당 이름을 찾은 후에 해당 인덱스에 맞는 또 다른 배열을 이용해서 전화번호를 찾아야 할 것입니다. 탐색 효율이 떨어지는 것을 볼 수 있습니다.

하지만 해시를 사용한다면 이야기가 달라집니다. 해시 함수를 통해서 특정 값이 있는 위치를 바로 찾을 수 있기 때문에 탐색 효율이 좋습니다.

NOTE

해시 테이블: 키와 대응한 값이 저장되어 있는 공간 bucket: 해시 테이블의 각 데이터

해시의 특성을 활용하는 분야

해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있습니다. 이러한 특징으로 인해 데이터를 저장하고 검색하거나, 보안이 필요한 때에 활용됩니다.

해시가 사용되는 실제 사례

• 비밀번호 관리: 비밀번호를 저장할 때 해시 함수를 활용해서 비밀번호를 저장합니다.
• 데이터베이스 인덱싱: 데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용합니다.
• 블록체인: 블록체인의 각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있습니다.

구현

처음 설명했던 것처럼 JS에서는 Object만 사용해도 hash를 쓸 수 있는데요. hash의 원리를 이해하면 이 구조를 다른 좀 더 큰 계층에서도 사용할 수 있기에 알아는 두는 것이 멋진 개발자가 되는 길입니다.

해시 함수

해시 함수를 구현에서 고려해야 하는 사항들이 있어요.

첫번째로 해시 함수로 반환되는 값은 해시 테이블을 넘어선 안됩니다. 해시 함수의 반환 값이 인덱스로 되기 때문에 해시 함수의 반환값은 해시 테이블의 크기인 N보다 작은 0부터 N-1까지의 값이어야 해요.

두 번째로 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 합니다. 해시 함수의 충돌이 안 날수는 없으나 최소한으로 줄이는 것이 좋아요.

자주 사용하는 해시 함수

실제로는 어떤 해시 함수를 사용하는지 알아봅시다.

숫자 해시 함수

나눗셈법

나눗셈법은 가장 떠올리기 쉬워요. 키를 소수로 나눈 나머지를 인덱스로 활용하는 방법입니다.

h(x) = x mod k ( x%k, k는 소수로 해야 충돌이 적어요. )

소수를 사용하는 방식이 충돌이 적은 이유

소수 대신 15를 사용해봅시다. 15를 적용하면 위 그림처럼 규칙적으로 계속 같은 해시값이 반복되는 것을 확인하실 수 있습니다. k의 약수 중 하나인 3, 5의 배수면 전부 이런 형태로 진행되죠.

이유는 간단합니다. N의 약수 중 하나를 M이라고 한다면 M * K = N이 되는 수가 무조건 있기 때문입니다. 그렇기에 K가 1 또는 자기 자신만 있는 수인 소수를 사용하는 것입니다.

나눗셈 법을 사용하면 테이블의 크기는 나눗셈 법에서 사용하는 소수 K가 됩니다. 아주 많은 데이터를 저장해야 한다면 그만큼 큰 소수를 구해야 하는데요. 현재로써는 그 수를 구하는 효율적인 방법이 없다고 합니다. 그래서 다른 방식들도 생겨나게 되었어요.

곱셈법

곱셈법에서는 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수를 활용하지 않아요.

h(x) = ( ( ( x _ A ) mod 1 ) _ m) (m은 최대 버킷의 개수, A는 황금비)

황금비는 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율과 같은 비율을 뜻합니다. 지금은 계산에서 실제 황금비인 1.618033...을 사용하지 않고 소수부인 0.618033... 만 사용하겠습니다.

공식을 진행해봅시다.

1. x * A: x와 황금비 A를 더합니다.

2. ( ( x * A ) mod 1 ): 정수 부분을 버리고 소수 부분만 취합니다. ( ex) 3.1523이면 0.1523만 남게 된다. )

   

3. ( ( ( x _ A ) mod 1 ) _ m): 최대 버킷의 개수인 m을 곱해서 해시 테이블에 매핑합니다. 2단계에서 소수 부분만 취했기 때문에 0 ~ 0.99... 까지의 범위에 있었는데 여기에 m을 곱해줘서 0 ~ m-1 의 범위를 갖게 되었습니다. 곱셈법은 소수 대신 황금비를 사용하여 로직을 구현합니다. 따라서 테이블의 크기가 커져도 추가 작업이 필요 없죠.

문자열 해시 함수

키의 자료형이 문자열인 해시를 만들어 봅시다. 문자열 해싱은 문자열의 문자를 숫 자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱합니다.

이를 위해 polynomial rolling method을 사용합니다.

hash(s) = (s[0] + s[1] _ p + s[2]_ p² + ... + s[n− 1]* p"-1) mod m ( p는 31, m은 해시 테이블 최대 크기 )

메르센 소수

2^N-1 형식으로 표시할 수 있는 숫자 중 소수인 수를 말한다.

해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있다.

동작 과정은 다음과 같아요.

1. a부터 z까지 숫자와 매치한 표와 키
2. 표에 맞춰서 계산 ( s[0]*p⁰은 1*1입니다. )
3. 그 이후인 s[1]부터는 테이블의 크기를 넘어간 수가 나오기 시작합니다. 우선 전부 순회해줍니다.
4. 모든 수들을 순회하고 나면 해당 값들을 전부 더하고 해시 테이블의 크기로 모듈러 연산을 해서 해시 테이블의 크기에 맞춰줍니다. 위 과정을 통하면 문자열을 해싱 함수를 통해 숫자로 만들 수 있는데요. 이때 문제는 apple이라는 단순한 문자열임에도 너무 큰 수가 결과로 나온 것입니다. 여기서 더 문자열이 커지게 되면 오버플로우가 발생할 수 있어요. 이를 위해 다음의 연산을 수행해줍니다.

(a+b)%c=(a%c+b%c)%c

간단하게 설명하면 최종값을 모듈러 연산하는 것이 아니라 각 계산 과정마다 모듈러 연산을 수행하는 것입니다. 해시 함수가 직접 적용하면 다음의 형태입니다

hash(s) =(s[0]%m+s[1]_ p%m+s[2]_ p² %m ...... s[n -1]* p(n-1)%m)%m

해시 함수 충돌 처리

서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌이라고 합니다. 하나의 버킷에는 2개의 값을 넣을 수 없기 때문에 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 합니다.

이를 해결하기 위해선 다양한 방법이 존재합니다.

체이닝으로 처리

연결리스트로 같은 해시값을 가지는 데이터를 연결합니다.

해시 함수를 거친 반환값이 충돌한다면 해시 테이블의 원소 자체를 연결 리스트로 만들어 연결함으로써 문제를 해결할 수 있어요. 하지만 여기에는 두가지 단점이 존재합니다.

1. 해시 테이블 공간 활용성: 충돌이 일어날수록 해시 테이블 공간을 덜 사용하고 연결 리스트의 길이가 점점 길어질 수 있습니다.
2. 검색 성능 저하: 충돌이 일어날수록 순회해야 하는 연결리스트가 커지면서 결국 O(N)의 시간복잡도를 갖게 됩니다.

개방 주소법으로 처리

빈 버킷을 찾아 충돌값을 삽입하는 방법입니다. 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용하게 되죠.

선형 탐사 방식

충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. (보통 간격은 1이다.)

h(k,i) = ( h(k) + i ) mod m (m은 수용할 수 있는 최대 버킷, i는 간격)

선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용합니다. 물론 이 방식도 완벽할 순 없어요. 1칸씩 내려가다 보면 결국 충돌이 발생한 값끼리 모이는 영역이 생겨요. 이를 클러스터(cluster)라고 합니다. 클러스터가 생길 때마다 해시값은 겹칠 확률이 더 올라갑니다.

NOTE

이를 방지하기 위해 제곱수만큼 이동하는 방법도 있지만 문제의 확률이 작아졌을 뿐 없어지진 않아요.

이중 해싱 방식

해시 함수를 2개 사용하는 방식이며 때에 따라 N개를 사용하기도 해서 좀 더 견고한 해싱을 하는 방식이에요.

두번째 해시 함수의 역할은 첫번째 해시 함수로 충돌이 발생했을 때 어떻게 할지 정하는 역할입니다.

h(k,i) = (h₁(k) + i*h₂(k)) mod m (h_n은 n차 해시)

선형 탐사와 비슷하게 더하는 방식이지만 클러스터를 줄이기 위해서 m을 제곱수나 소수로 합니다. 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 해서 클러스터 형성을 최대한 피하기 위함입니다.

참고 문헌

https://product.kyobobook.co.kr/detail/S000213641007

SUMMARY

알고리즘은 꾸준히 공부해주지 않으면 개념들이 유독 빠르게 사라지는 것 같아요. 사라지면 다시 채워넣을 수 있도록 꾸준히 공부해보겠습니다. 잘못된 지식이 있다면 댓글 부탁드려요!

읽어주셔서 감사해요.