해시테이블(HashTable)과 해시함수(HashFunction)에 대해서

시작하기 전에...

해시테이블(hash table)이란 주요 자료구조 중의 하나로, 말 그대로 여러 데이터들을 저장하고 관리하는 여러 방식 중의 하나라고 보면 된다.

해시테이블에 대해서 검색해 본 사람이라면 해시함수에 대해서도 같이 들어본 적 있을 것이다. 

해시테이블과 해시함수는 뗄레야 뗄 수 없는 관계이며, 이에 대해서 이제 자세하게 정리해보고자 한다.

 

해시테이블(HashTable)이란?

해시테이블은 (key,value)로 데이터를 저장하는 자료구조 중 하나이다. 

key?value? 뭔가 객체의 느낌이 물씬나는 자료구조이다. 즉, 연결리스트와 같은 자료구조는 배열을 떠올리게 하는 자료구조였다면, 해시테이블은 객체를 떠올리게 하는 자료구조이다.

즉 내가 찾고자 하는 value값을 쉽게 불러올 수 있는 key값이 지정되고, 데이터를 찾고자 한다면, 자료구조를 한바퀴 돌 필요없이, key값만 알면 된다. 즉, 해시테이블은 빠르게 데이터를 검색할 수 있는 자료구조이다.

 

 

그런데 해시테이블에 저장되는 자료들이 정확히 객체의 형태를 띄는 것은 아니다. (빠른 데이터 탐색에 대한 이해가 쉽도록 객체를 비유로 든 것일 뿐)

정확히는, 해시테이블(객체의 형태)->storage(배열의 형태) : key를 해쉬함수를 돌린 값들이 인덱스로 들어가고 그 인덱스에 bucket이 저장 -> buckets(배열의 형태)->tuple(key, value) 의 형태로 데이터가 저장된다. 하단의 그림을 참고 해보자.

해시테이블의 형태

 우리가 저장하고자 하는 데이터, data=1234이다. 이 data가 저장되는 value값이 된다. 그리고 이 data가 해시함수를 거쳐서, 어떠한 암호화된 값이 만들어진다. 이를 index라고 새로 선언해보자. 이 index가 일종의 key값이 되어서 value와 함께 저장된다. 즉 데이터가 저장될 때, (index,data) 의 형태로 buckets에 저장되는 것이다. 이때 index즉 key값의 역할은, 우리가 찾고자 하는 data에 부여되는 고유한 자리번호이다. 

-> 여기서 핵심! 해시함수를 통과한 고유한 인덱스는 숫자로 나온다고 생각하고 index 처리해주는 것이 좋다!

  내부적으로 중복 체크를 할 때, 객체로 저장해서 문자화된 key 값을 체크하는 것보다

   인덱스로 숫자를 체크하는게 속도가 더 빠르다고 함!

 

여기서 데이터들이 저장되는 buckets이란 무엇일까?

 데이터는 해시함수를 거쳐서 암호화 된 key 값을 부여받게 되고, 이를 인덱스 삼아서, 본 데이터는 숨어서 저장이 된다.

이 때, 해시함수의 어떠한 로직으로 인해, 데이터 값은 다르지만, 해시함수를 거쳐서 같은 key값이 나온다면??

이런 경우, key값이라는 고유한 인덱스를 중심으로 이 인덱스를 가진 데이터 값들을 저장하는 해시테이블 내의 또 다른 데이터 묶음들을 buckets이라고 부른다. 

즉, 데이터는 bucket내에 저장되고, bucket들과 각 key값의 묶음이 해시테이블 내에 저장되는 것이다.

만약에 bucket이란 개념 없이, 바로 key와 value가 저장된다면?

위에서 설명한 고유한 키값-데이터의 1대1 대응이란 해시 테이블의 개념 자체에 모순이 된다. 

해시 테이블 내에 같은 키값이 중복으로 존재하게 되고, 따라서 키값을 알아도 그 키값이 중복으로 존재해버리게 되는 것이다. 

 

이는 실제로 해시충돌 즉, key 값이 같은 경우 발생하는 문제와 관련된 개념이다. 

bucket 안에 일종의 연결리스트처럼 나열하여, 같은 키값을 지닌 데이터를 붙어서 저장하는 방법 뿐 아니라,

다른 해결 방법도 존재하고 해시충돌과 그 해결방법에 대해서는 조금있다 정리해보고자 한다.

 

해시함수(HashFunction)란?

해시 함수란 주어진 데이터를 암호화 된 키값으로 변경해주는 함수를 의미한다.

이 때, 데이터가 해시함수를 거치는 과정을 해싱이라고 부른다.

위에서 언급한 바와 같이, 해싱의 본질적인 의미는 각 데이터에 고유한 키값을 주는 것이다.

그러나 여러 데이터에 동일한 키값을 줄 수 밖에 없는 경우가 발생하고, 이러한 해시충돌을 최대한 적게 만들어주는 해시함수가 좋은 해시함수이다. 

즉 키값을 고르게 만들어 내는 것이다.

해시함수의 방식에는 크게 3가지 방법이 있다. 사실 해시함수 방식에 대해서 까지 외우고 있을 필요는 없다고 개인적으로 생각한다...

 

division method 

나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수이다. 숫자로 된 키를 해시테이블 크기 mm으로 나눈 나머지를 해시값으로 반환한다. 

mm은, 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 한다.

 

multiplication method

숫자로 된 키가 kk이고 AA는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의된다. 

mm이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 한다.

나눗셈법보다는 다소 느리다고 합니다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.

 

universal hasing

다수의 해시함수를 만들고, 이 해시함수의 집합 HH에서 무작위로 해시함수를 선택해 해시값을 만드는 기법이다. 

HH에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m1/m로 만드려는 것이 목적이다.

 

해시충돌이란?

중요한 개념이라 빨간색으로 강조해서 제목을 만들어봤다.

위에서 이미 언급한 바와 같이, 해시 충돌이란 서로 다른 데이터가 해싱을 거친 후 같은 키값을 가지게 되는 경우이다.

 

여기서 잠깐 다른 이야기를 하자면, 해시테이블과 해시함수에 대해서 설명할 때, 키값과 데이터는 1대1 대응을 한다고 하는데, 

실질적으로 해시충돌 발생 가능성을 고려한다면, 데이터->키값의 1대1 대응은 맞을 수 있으나, 키값->데이터는 1대1대응이 아니라고 봐야 할 것이다. 각 데이터는 무조건 하나의 키값을 가지지만, 키값 하나에는 여러 데이터가 만들어질 수 있기 때문이다. 

따라서 이를 다르게 생각하면 해시함수를 통해 데이터를 키값으로 암호화는 가능하나, 그 키값을 다시 해시함수를 역으로 거쳐서 데이터 값으로 일종의 복호화 하는 과정은 불가능하다고 봐야 한다.

 

다시 해시 충돌로 돌아와서, 고유한 키값에 1대1로 데이터가 대응하여 저장이 되어야 하는데, 이런 경우에는 어떻게 데이터를 저장하고 관리 할 수 있을 지에 대한 개념은 매우 중요하다고 볼 수 있다.

충돌에 의한 해결 방법은 크게 2가지 방식이 있다.

 

chaining

이는 간단히 연결리스트자료구조(LinkedList)를 생각하면 이해하기 쉬울 것이다.

해시충돌 시, chaining 방식

추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하는 것이다.

즉 해시테이블 자료구조 내에 버킷이라는 연결리스트 자료구조가 존재 하는 것이다. 

장점은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며 삭제 작업이 간단하다는 것이고,

단점은 데이터의 수가 많아지면 그만큼 연결되는 리스트 또한 많아지며 캐시의 효율성이 떨어지게 된다.

 

Open Addressing

이는 버킷 내에 데이터들을 이어붙이는 것이 아니라, 해시테이블의 남는 공간을 활용하는 방법이다. 

Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

 

1. Linear Probing: 순차탐색을 한다. 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

2. Quadratic Probing: 2차함수를 이용한다. 해시의 저장순서 폭을 제곱으로 저장하는 것이다.  예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

해시충돌 시, open addressing 방식

 

해시테이블의 시간복잡도

자료구조	탐색	추가하기	삭제하기
Hash Table	O(1)	O(1)	O(1)

각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.

하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

 

해시테이블의 버킷 확장(Resize)

버킷 확장은 말그대로, 해시 테이블 내에서 데이터를 저장할 수 있는 버킷을 늘려주는 것이다.

여기서 생각해 볼 수 있는 점은, 확장을 해줘야 한다는 점은, 우리가 생각하는 배열이나 객체처럼 무작정 데이터를 저장하는 자료구조의 크기가 늘어나는 것이 아니라, 임의로 늘려줘야 한다는 것이다.

 

그렇다. 해시 테이블을 만들때, 일정 버킷수를 할당해준다. 따라서 데이터를 저장하다가 테이블 내의 버킷 수가 일정 임계점에 도달하면, 버킷수를 늘려줘야 한다.

 

일반적으로는 데이터가 들어있는 해시 버킷의 갯수가 75%가 됐을때, 버킷의 수를 두배로 늘려준다.

 

 

참고 자료

https://dayzen1258.tistory.com/entry/%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94%EC%9D%B4%EB%9E%80

해시테이블이란?

https://mangkyu.tistory.com/102

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

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

해싱, 해시함수, 해시테이블 · ratsgo's blog