Hash Table과 Direct Addressing Table

Hash Table이란?

 

Hash는 영어로 여러가지 뜻을 가지고 있지만  "뒤죽박죽" 이라는 뜻도 가지고 있습니다.

실제로 Hash Table은 배열에 충분히 큰 공간을 할당(이 공간을 보통 bucket이라고 부름)하고 해싱함수를 이용하여 배열 index에 일정한 값을 적용하여 검색시간을 획기적으로 줄여 O(1)의 시간을 가집니다. 예를 들면 테이블 인덱스에 들어갈 값을 충분히 큰 소수로 숫자를 나눠줍니다. 그리고 해당 숫자의 인덱스에 값을 매핑시킵니다. 키값을 해시함수에 입력시 해시값이 도출됩니다.

 

일반적인 배열의 경우 데이터를 중간에 추가, 삭제 하면 배열 데이터를 하나씩 앞으로 옮기거나 뒤로 옮겨야하는데 이런 작업을 수행할시 O(n)이라는 시간적, 공간적 비용이 필요합니다. 반면 Hash Table을 적용하면 이런 단점이 획기적으로 줄어듭니다.

 

그렇다면 Hash Table의 단점은 없을까요?

해시 테이블은 근본적으로 충돌 가능성을 가지고 있습니다.

쉽게 예를 들어 해싱 규칙을 13으로 나눈다로 세워봅시다. 임의의 숫자를 13으로 나눈 인덱스에 데이터를 넣습니다. 14를 테이블에 넣을 때와 1을 넣는다면 동일한 위치에 데이터가 매핑되는 충돌 가능성을 가지게 됩니다. 따라서 해싱 함수(해싱 규칙)은 최대한 충돌없이 고르게 분포할 수 있는 규칙을 사용해야합니다.

 

 

Direct Addressing Table은 범위가 크지 않은 값을 바로바로 사용할 수 있게 만들어둔 Hash Table이라고 볼 수 있습니다. 예를 들면 알파벳을 ASCII 값으로 매핑하여 저장한 후 불러오는 방식으로 사용할 수 있습니다.

(A=>'65번 인덱스에 매핑')

 

#include <iostream>

int main() 
{
	// DAT(Direct Addressing Table) - Hash Table
	// 값 자체를 index로 활용해서 사용합니다.(Hash Table에서는 특정한 함수를 사용)
	// 넉넉한 크기의 배열을 선언합니다.
	int bucket[256] = {};
	char target = 'A';
	// 'A'의 아스키코드는 65입니다.
	// bucket 배열의 65번째에 1을 대입
	bucket[target] = 1;

	return 0;
}