해시 테이블

배경

 

컴퓨터 공학에서 해시 테이블(혹은 해시 맵 또는 연관 배열)은 데이터를 해시한 결과를 키로 사용해서 값을 찾을 수 있는(Mapping 하는) key-value 자료구조 중 하나이다.  탐색을 수행할 때 평균적으로 O(1) 정도의 알고리즘 복잡도를 기대할 수 있다. 다만 구현 방법이나 데이터의 입력에 따라 최악의 수행속도가 O(N) 까지 늘어날 수 있는 만큼 구현 시 고려해야 할 사항을 조사하고 필요한 요구사항에 따라 실제 인터페이스만 노출하는 방식으로 개발하여 본다.

 

기반자료

 

• 여러 자료구조의 평균 기능 수행 속도

 

	접근	탐색	삽입	삭제
배열	O(1)	O(N)	O(N)	O(N)
스택	O(N)	O(N)	O(1)	O(1)
큐	O(N)	O(N)	O(1)	O(1)
양방향 링크드 리스트	O(N)	O(N)	O(1)	O(1)
해시테이블	N/A	O(1)	O(1)	O(1)
이진 탐색 트리	O(log(N))	O(log(N))	O(log(N))	O(log(N))
B-트리	O(log(N))	O(log(N))	O(log(N))	O(log(N))
RB-트리	O(log(N))	O(log(N))	O(log(N))	O(log(N))

 

해시 테이블은 주요 기능을 수행할 때 기대할 수 있는 평균 수행 속도가 상수에 수렴한다. 이는 다른 자료구조에 비해서 가장 좋은 성능을 보일 수 있음을 보인다.

 

• 여러 자료구조의 최악 기능 수행 속도

 

	접근	탐색	삽입	삭제
배열	O(1)	O(N)	O(N)	O(N)
스택	O(N)	O(N)	O(1)	O(1)
큐	O(N)	O(N)	O(1)	O(1)
양방향 링크드 리스트	O(N)	O(N)	O(1)	O(1)
해시테이블	N/A	O(N)	O(N)	O(N)
이진 탐색 트리	O(N)	O(N)	O(N)	O(N)
B-트리	O(log(N))	O(log(N))	O(log(N))	O(log(N))
RB-트리	O(log(N))	O(log(N))	O(log(N))	O(log(N))

 

다만 최악의 경우를 확인해보면 해시 테이블은 O(N)까지 악화될 수 있음을 보인다. 자료구조에서 O(n)은 다른 자료구조를 사용하는것과 다르지 않은 속도이다. 이 자료구조를 위해 데이터를 키-값 구조로 연결하기 위해 해시 연산을 한 것을 고려하면 다른 자료구조보다 비용이 높음을 알 수 있다.

 

a. 해시 함수

데이터로부터 ‘키’를 얻어내기 위한 함수. 가장 대표적인 방법은 나눗셈 법과 자릿수 접기 두가지가 있다

 -나눗셈 법

값을 테이블의 크기로 나누어 그 나머지를 키로 사용하는 방법이다. 그 나머지는 테이블의 주소 범위 (0 ~ n-1)를 넘지 않는다는 특징이 있다. 다만 별다른 연산 없이 나눗셈만 사용한다면 n이 짝수일 경우 입력 값의 홀수, 짝수 여부가 그대로 해시에 반영되므로 n에 홀수를, 홀수 중에서도 소수(prime number)를 사용하는 것이 좋다.

 -자릿수 접기

데이터를 특정 단위로 나누어 덧셈이나 XOR 연산 등을 통해 해시 주소를 얻는 방식이다. 해시 테이블보다 더 큰 데이터, 즉 문자열이나 32바이트 데이터 등을 처리하기 좋다. 

 

b. 해시 충돌

이 문제는 키-값을 사상하기 위한 함수가 1:1이 아니라는 문제로 인해 발생한다. 극단적인 예시로 2^10 가지 입력으로 2^1가지, 즉 두가지 키를 생성하는 함수를 사용한다면 2^10가지 입력이 두가지 키가 되어 나오는 좋지 않은 일이 일어나게 된다. 그렇다고 2^10가지를 담기 위해 2^20가지 출력을 가지는 해시 함수를 사용한다면 충돌확률을 낮추어 O(1)에 가까운 속도를 보일 수 있지만 필연적으로 공간적 손해를 부른다. 해시 충돌은 좋은 해시 함수와 공간 복잡도로 개선할 수 있다. 하지만 공간 복잡도를 희생하지 않는 한 해시 충돌의 완전한 방지는 어려우므로 충돌이 발생함을 가정한 해결법을 설정해야 한다. 

 

해시 충돌이 발생 했을 때 ‘다음 주소’ 를 결정하는 방법에 따라 데이터가 군집을 이루는 현상이 발생할 수 있다.  군집 현상은 O(1)에 수렴할 수 있는 작업을 O(n)까지 지연시킬 수 있는 문제이다. 이를 염두하여 해시 함수와 공간 복잡도를 설계해야 한다.

 

다음은 해시 충돌에 대처하는 방법 중 Closed Hashing에 속하는 Open Addressing과 Chaining에 대한 소개이다.

 

- Open Addressing

Open Addressing(이하 개방 주소법)은 그 주소를 사용할 수 없으니 약속한 다음 주소를 활용하기 위한 기법이다. 이는 처음에 사용하고자 하는 메모리의 양을 벗어나지 않는 장점이 있지만, 저장할 수 있는 자료의 양을 조절하려면 데이터 전체를 다시 해시해야하는 한계가 있다.

 

  Linear Probing

Linear Probing(이하 선형 탐사)는 해시 충돌이 발생 했을 때 지정된 주소 만큼 이동하여 데이터를 저장하는 방식이다. 군집 현상의 가능성이 높다

  Quadratic probing

Quadratic Probing(이하 이차 탐사)는 선형 탐사와 마찬가지로 지정된 주소 만큼 이동하나 그 간격이 제곱으로 증가하는 방식이다. 공간의 군집 현상은 해결했지만 초기 해시 값이 같은 데이터에 대해 군집 문제가 있다.

Double Hashing probing

Double Hash Probing(이하 이중 해싱 탐사)는 충돌 문제가 일어났을 때 추가적인 해시 작업을 통해 예측할 수 없는 주소로 이동하는 방법이다. 추가적인 해시 작업을 통해 군집을 해결하였지만 연산 비용이 높다.

 

 - Chaining

Chaining(이하 체이닝) 은 충돌이 발생한 주소를 시작으로 데이터를 연속해서 달아 사용하는 방법이다. 메모리가 허용하는 한 데이터를 지속적으로 이어붙일 수 있는 특징이 있다.  개방 주소 방식의 이차 탐사와 비슷한 형식으로 공간 군집 현상을 해결했지만 초기 해시값이 같은 경우에는 여전히 군집 문제가 발생할 수 있다.

 Linked List

해시 충돌이 발생했을 때 연결 리스트를 순차 탐색하여 요청한 작업을 수행한다. 다만 모든 데이터가 해시 충돌로 인해 하나의 연결 리스트에 삽입될 경우 군집 현상과 동일한 단점이 있다. 대부분의 기본 라이브러리는 Linked List(이하 연결 리스트)를 통해 체이닝 방식을 구현한다.

 Red-Black Tree

최악 O(N)까지 시간이 소요되는 연결리스트 대신 균형잡힌 Red-Black Tree (이하 RB 트리) 로 요청한 작업을 수행하는 방식이다. 이는 연산 복잡도를 최악의 경우에도 O(logN)까지 낮출수 있는 장점이 있다.

기능

• 해시 함수

• 키를 결정하기 위한 함수이다. 일반적으로 설정하고자 하는 배열의 범위만큼 숫자 범위를 설정한다.

• 예시) 정수 n을 저장하기 위한 배열 arr[10] 에 대한 해시함수 n % 10

• 삽입

• 데이터를 테이블에 삽입하기 위한 기능. 데이터를 통해 키를 결정하고 해당하는 위치에 삽입을 시도한다. 이미 데이터가 있는 충돌의 경우개방 주소법 혹은 체이닝 방법식에 따라 데이터를 삽입한다.

• 검색

• 테이블에 데이터를 찾기 위한 기능, 찾고자 하는 데이터를 통해 키를 결정하여 데이터가 있어야 할 위치를 검색한다. 찾은 데이터가 의도한 데이터가 아닌경우 해시 충돌로 인해 다른 위치에 있는지 끝까지 검색해야 한다.

• 수정

• 테이블에 있는 데이터를 수정하기 위한 기능, 검색 기능을 통해 찾은 데이터를 수정한다.

• 삭제

• 테이블에 있는 데이터를 삭제하기 위한 기능, 검색 기능을 통해 찾은 데이터를 삭제한다.

• 재배열

• 해시테이블의 크기를 조절하기 위한 기능, 새로운 해시 함수를 설정하고 테이블에 있는 모든 데이터를 찾아 새로운 해시 함수에 따라 해시해야 한다.

 

 

분석

 

Chaining 방식의 계산 복잡도

최선: 1

평균: 1

최악: N

 

해시 테이블의 최적화

해시 테이블은 공간 복잡도를 희생하여 속도를 얻는 자료구조이다. 구현 방식에 따라 공간 사용량이 약 60%를 초과하는 경우 성능 저하가 발생할 수 있다. 

 

해시 테이블의 검색

해시 테이블의 구현 방식에 따라, 특히 개방 주소 방식으로 구현된 자료구조의 경우 데이터 검색에 문제가 발생할 수 있다. 시나리오는 a b c 를 순차적으로 삽입하여 모두 충돌이 발생하여 각각 n, n+1, n+2 에 저장한다. 이후  b를 삭제한 후 c를 검색하려고 하려면 c의 해시값을 가지고 a를 찾은 후 충돌 위치인 n+1이 비어있으므로 검색을 마치게 된다. 이런 오류를 방지하려면 제거를 완전한 제거가 아닌 제거되었음을 표시하는 특정 값을 표시하여 검색을 계속할 수 있도록 해야한다.

 

해시테이블의 재배열

자료 양 대비 공간을 적게 할당한 경우 속도 개선을 위해 해시테이블의 크기를 늘려야 하는 경우가 있다. 이 경우 새로운 해시 함수를 제공하고 테이블 내에 있는 모든 데이터의 키를 새로운 해시 함수에 따라 다시 작성해야 한다.

 

해시 테이블의 장단점

 

Pros

• 접목하기 쉬움

• (메모리가 허용하는 한) 확장 가능

• 키가 얼마나, 자주 삽입/삭제되는지 알수 없을 때 사용하기 좋음

Cons

• 확장에 링크드 리스트를 사용하는 체이닝 방식은 캐시 성능이 좋지 않음. 

• 일부 공간에 데이터가 들어가지 않을 가능성이 있음(공간 낭비)

• 충돌이 많아질수록 알고리즘 복잡도가 최악 O(n)에 수렴할 수 있음

• 해시 함수에 따라 링크에 더 많은 공간 사용

 

좋은 해시 기능

• 결정론적인 해시 함수

• 결과물의 균등한 분배

• 비슷한 입력으로 완전히 다른 결과물

설계

구현