Hash Table에 대하여

해시 테이블이란?

어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 리턴 값을 인덱스에 저장하는 자료구조이다.

그렇다면 왜 해시 테이블을 사용할까?

직접 주소 테이블 (Direct Address Table)

해시 테이블은 직접 주소 테이블이라는 자료구조에서부터 출발한다. 직접 주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다.

 

내가 소수 찾기 알고리즘을 풀 때 소수만 남기기 위해서 0~n까지의 배열을 만들었는데 바로 그 방식인 것이다.

index	0	1	2	3	4	5	6	7	8
value	0	1	2	3	4	5	6	7	8

 

찾고자 하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간 복잡도는 O(1)이다. 마찬가지로 테이블에 있는 값을 삽입, 수정, 삭제하는 행위도 값이 어디 있는지만 알고 있으면 모두 한 방에 해결할 수 있으므로 O(1)의 시간 복잡도로 해결할 수 있다.

 

이렇게 직접 주소 테이블은 내가 보고 싶은 값이 어디 있는지 알고 있기 때문에 바로 접근해서 이후 작업을 수행할 수 있다는 점에서 굉장히 편리하다.

 

하지만 단점도 있다. 바로 공간의 효율성이 좋지 않다는 것이다. 저장된 데이터를 제외하고 0으로 채워진 나머지 공간은 '값은 없지만 메모리 공간은 할당되어 있는 상태'인 것이다. 즉, 테이블에 넣고자 하는 데이터의 값의 범위보다 값의 개수가 작다면 공간적인 효율이 떨어지는 것이다.

 

이런 상황을 적재율(load factor)이 낮다고 표현하는데, 적재율은 값의 개수 / 테이블의 크기로 나타내게 된다. 따라서 직접 주소 테이블은 1, 2, 3과 같이 연속적인 값을 저장하거나 혹은 값들의 범위 차이가 크지 않은 데이터에서 큰 힘을 발휘한다고 할 수 있다.

이러한 단점을 해시 함수로 보완하다

이렇게 직접  주소 테이블은 값에 접근하기는 편하지만 공간 효율이 좋지 않다는 단점이 있다. 그래서 이를 보완한 것이 해시 테이블이란 것이다.

 

해시 테이블은 직접 주소 테이블처럼 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수라는 것에 한번 통과시켜서 사용한다. 해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이대 함수의 결과물을 해시라고 부른다.

 

해시 함수의 특성 중 하나는 해싱만 보고는 인자로 어떤 값을 받았는지 추측하기 힘들다는 것이다. 이러한 해시 함수의 특징은 암호학에서도 사용된다고 한다.

 

직접 주소 테이블의 단점이 바로 10000이라는 값이 하나만 들어오더라도 10000번 인덱스에 값을 저장하기 위해 10000의 크기를 가진 테이블을 생성해야하기 때문에 나머지 9999개의 버리는 공간이 생기는 것이다.

 

하지만 해시 함수를 사용하면 지정한 해시 테이블의 크기만큼으로 변환이 되기 때문에 공간을 효율적으로 사용할 수 있게 한다.

 

해시의 충돌(Collision)

물론 해시 테이블은 단점도 있다. 바로 해시의 충돌이다. 해시의 충돌이란 서로 다른 값을 넣었지만 같은 인자가 나오는 것을 말한다.

 

해시 테이블은 처음부터 고정적인 공간을 할당하고 값을 계속 우겨넣는 방식이다. 그렇다면 해시 테이블의 크기를 넘는 데이터를 집어넣는다면 남는 데이터가 발생하게 된다. 어쩌지..?

 

하지만 이를 해결하는 방법이 존재한다.

충돌 해결하기

해시 테이블을 운용할 때 중요한 것은 해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐이다.

 

그러나 해시 함수를 아무리 잘 짜더라도 근본적으로 충돌을 완전히 방지하지는 못한다. 그렇기 때문에 어느 정도는 충돌을 감안하되 최소화하기 위해 해시 함수의 알고리즘을 개발하거나, 충돌이 발생하더라도 우회해서 해결할 수 있는 방법을 사용한다.

 

개방 주소법 (Open Address)

개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소라고 한다.

 

1. 선형 탐사법 (Linear Probing)

선형 탐사법은 말 그대로 선형으로 순차적으로 탐사하는 방법이다. 선형 탐사법은 충돌이 났을 때 정해진 n 칸만큼의 옆 방을 주는 방법이다. 만약 n = 1이라면, 2번 인덱스를 주는 방식으로 말이다.

 

선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(Primary Clustering) 문제에 취약하다는 것이다.

 

같은 해시가 여러 번 나오는 경우 선형 탐사법을 사용하면 데이터가 연속되게 저장될 가능성이 높아진다. 즉, 데이터의 밀집도가 높아진다는 것이다. 이런 경우 해시의 값이 1이 나왔을 때뿐만 아니라 2나 3이 나왔을 때도 충돌이 발생한다. 이렇게 되면 거대한 덩어리를 형성하여 충돌 발생 확률이 계속해서 커지게 된다.

 

이를 보완한 다른 방법을 알아보자

2. 제곱 탐사법 (Quadratic Probing)

제곱 탐사법은 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어난다는 것이 다르다.

 

이렇게 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.

3.  이중해싱 (Double Hashing)

그래서 나온 방법이 바로 이중 해싱이다. 말 그대로 해시 함수를 이중으로 사용하는 것이다.

 

하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다. 이렇게 하면 최초 해시로 같은 값이 나오더라도 다시 다른 해시 함수를 거치면서 다른 탐사 이동폭이 나올 확률이 높기 때문에 매번 다른 공간에 값이 골고루 저장될 확률도 높아진다.

 

이때 테이블 사이즈와 두번째 해시함수에 사용될 수는 둘 다 소수를 사용하는 것이 좋다. 둘 중에 하나가 소수가 아니라면 결국 언젠가 같은 해싱이 반복되기 때문이다.

분리 연결법 (Separate Chaining)

분리 연결법은 개방 주소법과는 다른 개념으로 접근하는 충돌 우회 방법이다. 분리 연결법은 해시 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.

 

다음 예시를 보면, 테이블 크기가 5일 때 해시로 1을 반환하는 1991, 6, 13, 21을 저장할 때 분리 연결법을 사용하면 이렇게 된다.

0	1	2	3	4
	[21, 13, 6, 1991]

그런데 배열의 순서가 뒤집혀있다. 이렇게 순서를 뒤집는 이유는 데이터를 삽입할 때 조금이라도 수행 시간을 줄이기 위해서이다.

 

링크드 리스트는 각 노드마다 다음 노드에 대한 정보를 가지고 있는 것이 특징이다. 때문에 새 노드를 삽입할 때 첫 노드부터 접근을 하게 되면 마지막 노드까지 링크를 타야 하기 때문에 효율이 떨어진다. 따라서 순서를 뒤집어 바로 첫 번째에 삽입할 수 있도록 순서를 뒤집는 것이다.

 

이렇게 분리 연결법을 사용하려면 해시 함수의 역할이 굉장히 중요하다. 결국 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면 다른 곳은 텅텅 비어있는데 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문이다.

 

결국 내가 찾고자 하는 값이 리스트의 맨 마지막에 위치하고 있다면 링크드 리스트를 처음부터 끝까지 다 탐색해야하기 때문에 O(n)의 시간 복잡도를 가지게 된다. 그렇기 때문에 최대한 저장하고자 하는 데이터를 균일하게 퍼트려서 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요한 것이다.

 

테이블 크기 재할당 (Resizing)

해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가 데이터가 넘치기 마련이다.

 

개방 주소법의 경우에는 테이블이 꽉 차게되고, 분리 연결법의 경우에는 각각의 버킷에 저장되는 리스트가 점점 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것이다.

 

그렇기 때문에 해시 테이블은 꽉꽉 채우기보다 어느 정도 비워져 있는 것이 성능 상 더 좋으며, 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야 한다.

 

이건 특별한 알고리즘보다는 기존 크기의 두 배정도로 새로운 테이블을 선언해서 기존 테이블의 데이터를 그대로 옮겨 담는 방법을 사용한다. 분리 연결법을 사용한 경우 재 해싱(Rehashing)을 통해 너무 길어진 리스트의 길이를 나누어서 다시 저장하는 방법을 사용하기도 한다.

 

출처

https://medium.com/amhocode/hash-table-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-2223f2ae1528

Hash Table 이해하기

https://evan-moon.github.io/2019/06/25/hashtable-with-js/

JavaScript와 함께 해시테이블을 파헤쳐보자