#.8 Hash Table

1. Hash Table

1.1 정의

해시 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다.

• 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 Direct address table과 달리
• 해시 테이블은 키 값을 입력받아서 해시 함수를 통해 얻은 해시를 인덱스 배열(버킷)로 환산해서 데이터에 접근한다.
• 이렇듯 해시 테이블은 각각의 key에 해시 함수를 적용해 해시를 생성하고, 해시를 활용해 값을 저장하거나 검색한다.

1.2 해시 테이블 구성 요소

1) 키(Key)

• 키는 고유한 값으로, 다양한 길이의 값이 될 수 있으모, 해시 함수의 input이 된다.
• 키는 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야하기 때문에 해시 함수로 값을 바꾸어 저장이 된다.
• 이를 통해 공간의 효율성을 추구한다.

2) 해시 함수(Hash Function)

• 키를 해시로 바꾸어주는 함수
• 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 한다.
• 해시 함수의 첫 번째 핵심은, 데이터를 고르게 분포시켜, 데이터가 특정 위치에만 밀집하는 clustering을 줄이는 것이다.
• 해시 함수의 두 번째 핵심은 해시 충돌을 일으키는 확률을 최대한 줄이는 것이다. 
• 해시 테이블에 사용되는 대표적인 해시 함수는 아래의 4가지이다.

 

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

3) 해시(Hash)

• 해시 함수의 결과물이며, 버킷에서 값(value)과 매칭되어 저장된다.

4) 값(Value)

• 버킷에 최종적으로 저장되는 값으로, 키와 매칭된다.

5) 저장소(bucket, slot)

• 데이터가 저장되는 공간을 뜻한다.

1.3 해시 테이블 예시

• 위의 그림은 해시 테이블의 예시이다.
• 만약 위의 그림에서 John Smith(key)를 hash function을 적용하면 02라는 해시 값을 얻는다.
• 그러면 521-1234(value)는 미리 확보한 공간(0~15) 중 02(hash)에 저장되게 된다.
• 이후 key 값에 John Smith를 입력하면, hash function을 통해 02라는 주소 값을 알게 되고, 해당 주소에 저장된 521-1234 라는 value를 얻을 수 있게 된다.
• 이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로, 매우 빠르게 데이터를 저장, 삭제, 조회 할 수 있다.

2. 해쉬 충돌 (Hash Collision)

해시 테이블에서 가장 문제가 되며 중요한 부분이 바로 해시 충돌이다. 충돌을 이해하기 위해서 선행되어야하는 지식이 있다.

2.1 적재율(Load Factor)

적재율이란 해시 테이블의 크기 대비, 키의 개수를 뜻한다.
키의 개수를 K, 해시 테이블의 크기를 N이라 했을 때, 적재율은 K/N이다.

• 위에서 잠시 언급한 Direct Address Table의 경우 키 값을 인덱스로 사용하기 떄문에, 적재율이 1 이하인 반면,
• 해시 테이블의 경우 적재율이 1을 초과할 수 있으며, 이 때는 반드시 해시 충돌이 발생하게 된다.

2.2 해시 충돌과 시간 복잡도

• 위의 사진과 같이 해쉬 충돌이 일어나면 무엇이 문제일까? 바로 효율의 문제가 발생한다.
• 해시 테이블은 데이터를 저장, 삭제, 검색하는 것에 매우 효율적인 자료구조이다.
• 해시 테이블의 적재율이 1 이하라면, 시간 복잡도는 O(1)이다.
• 그러나 적재율이 1을 초과하여 해시 충돌이 일어난다면, 최악의 경우 시간 복잡도는 O(N)이 되어버린다.
• 효율성을 생각한다면, 해시 충돌은 절대 피할 수가 없다는 것을 의미한다.

연산속도를 빠르게 하는 것이 해시 테이블의 핵심이라면, 피할 수 없는 해시 충돌을 완화하여 골고루 분산 혹은 감소 시켜주는 것이 해시 함수의 핵심이라 할 수 있겠다.

3. 해시 충돌을 개선하는 2가지 방식

• 위와 같은 해시 충돌을 개선하는 2가지 방식이 존재한다.
• 바로 분리 연결법과 개방 주소법이다.

3.1 체이닝(Chaining)

• 체이닝이란 해시 충돌이 발생했을 떄, 이를 동일한 버킷에 링크드 리스트 형태로 저장하는 방법을 뜻한다.
• 즉 다른 키를 넣었는데, 동일한 해시 값이 나오고 버킷에 데이터가 이미 있다면, 링크드 리스트처럼 이미 저장되어있는 버킷이 다음 노드를 가리키게하는 방식이다.
• 체이닝 방식은 해시 값을 찾기 위해, 링크드 리스트 방식을 사용해야하기 때문에 최악의 경우 O(N)의 시간 복잡도를 가지게 된다.
• 리스트로 연결 방식을 짜는 것이 일반적인 방식이다. (트리로 시간 복잡도를 낮추는 시도도 있다) 

3.2 개방 주소법(Open Addressing)

• 개방 주소법은 추가적인 메모리를 사용하는 체이닝 방식과 다르게, 비어있는 해시 테이블의 공간을 활용하는 방식이다.
• 즉 충돌 발생시 다른 버킷에 데이터를 저장하는 것으로, 다른 버킷을 어떻게 찾느냐에 따라서 3가지 방법으로 나뉜다.

1) 선형탐색(Linear Probing)

• 선형탐색은 가장 기본적인 해시 충돌 해결 방법이다. 
• 계산된 해시 값에 대한 버킷이 이미 차있다면, 다음 버킷으로 이동하면서 비어있는 곳에 저장한다. (Probing)
• 계산은 단순하지만, 검색 시간이 많이 소요된다. (O(N)까지도 가능)
• 선형탐색은 인접한 버킷에 데이터를 삽입하기 때문에 데이터들이 특정 위치에만 밀집하는 clustering이 발생할 수 있다.

2) 제곱 탐색(Quadratic Probing)

• 제곱 탐색은 검색 폭을 제곱으로 탐색하여 저장하는 방식이다.
• 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
• 선형탐색에 비해 더 폭넓게 탐색하기 떄문에 탐색과 삭제, 고르게 분포시키는 것에 효율적일 수 있다.
• 그러나 초기 해시 값이 같을 경우 여전히 clustering 문제가 발생할 수 있다.

3) 이중 해싱(Double Hashing)

• 이중 해싱은 선형 탐색과 재곱 탐색에서 발생하는 클러스터링 문제를 해결하기위해 도입된 방식이다.
• 처음 해시함수로는 해시 값을 찾고, 두번째 해시 함수는 해시 충돌시 탐색 이동 폭을 계산하기 위해 사용된다.
• 최초 해시 값이 같더라도 탐색 이동 폭이 다르기 때문에 클러스터링 문제를 해결 가능하다.

 

참고 자료 및 출처

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash

https://baeharam.netlify.app/posts/data%20structure/hash-table

https://mangkyu.tistory.com/102

https://yoongrammer.tistory.com/82