[자료구조] - 해쉬테이블

1. 해쉬테이블이란?

 - (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 다시 말해 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.

 - 해쉬테이블의 특징은 :

• 기본 연산으로 search, insert, delete가 있다
• 순차적으로 데이터 저장 X
• Key를 통해 Value 얻을 수 있다 (이진탐색트리나 배열에 비해 속도가 훨씬 빠름)
• 데이터 비교에 효율적이다.(커다란 데이터를 짧은 길이로 축약 가능하므로)
• key는 중복 불가, value는 가능
• 수정 가능
• 일반적으로 배열로 미리 해시 테이블 사이즈만큼 생성 후에 사용

해시 테이블은 key와 value가 1대 1로 매핑되어 있기에 search, insert, delete 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가진다. 공간복잡도는 O(n) , n은 키의 개수.

Hash table time complexity in Big O notation
Algorithm	Average	Worst case
space	O(n)	O(n)
search	O(1)	O(n)
insert	O(1)	O(n)
delete	O(1)	O(n)

 

2. 해시 함수란?

 - 해시 함수에서 중요한 것은 고유한 인덱스 값을 정하는 것이다. 즉, 해시 함수는 임의의 길이를 갖는 메시지를 입력 받아서 고정된 길이의 해시값을 출력하는 함수이다.

 - 해시 테이블에 사용되는 함수로는 

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

  - 해시 함수는 입력값의 길이와 관계 없이 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결과값이 나오는 경우가 있는 단점이 있다. 이 것을 해시 충돌이라고 표현하고, 해시 충돌이 적은 해시 함수가 좋은 해시 함수다.

 

 3. 해시값이 충돌하는 경우

  - 해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

 

  [ 분리 연결법(Separating Chaining) ] 

 분리 연결법이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 실제로 Java8의 해시 테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

 이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 Chaining 되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소하는 단점이 있다.

 

 [ 개방 주소법(Open Addressing) ] 

 개방 주소법이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. 이 방법을 구현하기 위한 방법은 대표적으로 세 가지가 있다.

1. Linear Probing : 현재의 버킷 index로부터 고정폭만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장
2. Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동, 그 다음 계속 충돌 발생 시 2^2,  3^2칸씩 옮기는 방식.
3. Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.