[자료구조] Hash Table (해시 테이블)

Hash Table (해시 테이블)

기본개념 : 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것. 궁극의 탐색 알고리즘이다. 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.

Table[3819] = 123817;

데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다.

특징 : 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.

(통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다.)

용어정리 : 

1. Collision(충돌) : 서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 주소를 반환하는 것. 어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못합니다. 한마디로 말해서, 해시 함수의 충돌은 피할 수 없습니다.

2. Cluster(클러스터) : 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제

Hash function (해시 함수)

해시 함수의 알고리즘 종류

1. Division Method(나눗셈 법) 

2. Digit Folding(자릿수 접기)

1. Division Method(나눗셈 법) 

나눗셈법은 입력 값을 테이블의 크기로 나누고, 그 '나머지'를 테이블의 주소로 사용한다.

주소 = 입력 값 % 테이블의 크기

특징 : (1) 어떤 값이든 테이블의 크기로 나누면 그 나머지는 절대 테이블의 크기를 넘지 않는다.

   (2) 테이블의 크기를 n이라 할때, 0~n-1 사이의 주소를 반환함을 보장.

   (3) 테이블의 크기 n을 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다.

2. Digit Folding(자릿수 접기)

숫자의 각 자릿수를 더해 해시 값을 만드는 것.

특징 : (1) 문자열을 키로 사용하는 해시 테이블에 특히 잘 어울리는 알고리즘

 문자열의 각 요소를 ASCII  코드 번호(0~127)로 바꾸고 이 값을 각각 더하여 접으면 문자열을 해시 테이블 내의 주소로 변환 가능

ex) 

다음과 같이 7자리의 숫자가 있다고 해봅시다.

8 1 2 9 3 3 5

이 수의 각 자릿수를 더하면 새로운 값, 31이 나옵니다.

31 = 8 + 1 + 2 + 9 + 3 + 3 + 5

이번에는 두 자리씩 더해 봅시다.

148 = 81 + 29 + 33 + 5

Collision Resolution (충돌 해결하기)

해시 테이블의 충돌을 해결하는 방법

1. Open Hashing(개방 해싱) : 주소 밖에 새로운 공간을 할당하여 문제 해결

(1) Chaining(체이닝) : 개방 해싱인 동시에 폐쇠 해싱

2. Closed Hashing(폐쇄 해싱) : 처음에 주어진 해시 테이블의 공간 안에서 문제 해결

(1) Chaining(체이닝) 개방 해싱인 동시에 폐쇠 해싱

(2) Open Addressing(개방 주소법)

(가) Linear Probing(선형 탐사)

(나) Quadratic Probing(제곱 탐사)

(다) Double Hashing(이중 해싱)

(라) Rehashing(재해싱)

1. Chaining(체이닝)

충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법. 개방 해싱 알고리즘이다.

특징 :  (1) 새 데이터를 링크드 리스트의 가장 앞(즉, 헤드의 앞)에 삽입한다.

(그러면 데이터 삽입시, 링크드 리스트 테일을 찾는 '순차 탐색' 을 수행하지 않아도 된다.)

    (2) 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 가짐.

    (3) 해시 테이블 + 이진 탐색 트리의 결합은 최고!

체이닝 해시 테이블 형태

체이닝 기반 해시 테이블의 삽입

2. Chaining(개방 주소법)

개방 주소법은 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 충돌된 데이터를 입력하는 방식

(1) Linear Probing(선형 탐사)

해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.

특징 : Cluster(클러스터) 현상이 매우 잘 발생한다.

(2) Quadratic Probing(제곱 탐사)

선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.

특징 : 서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생

(3) Double Hashing(이중 해싱)

클러스터 방지를 위해, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용

(4) Rehashing(재해싱)

해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것