해시 테이블(Hash Table)

해시 테이블이란?

해시 테이블은 key - value 시스템의 자료구조다다. key 는 배열의 index 처럼 value 에 바로 접근할 수 있도록 하는 값이다. index 와 달리 문자열, 파일 등 다양한 데이터가 가능해서 value와 관련 있는 값으로 설정할 수 있다.

fruits = {
	key: "사과", value: "맛있다",
    key: "복숭아", value: "딱딱한게 맛있다."
}

//key값으로 데이터 바로 접근
fruits["사과"] -> "맛있다"

 

어떻게 가능하지?

사실 해시테이블의 내부는 배열과 비슷하게 index 와 value 로 구성되어 있다. key 는 hash function 을 통해 해시 코드로 계산되고, 이 해시코드는 index 로 환산된다. hash function 은 입력되는 데이터의 길이가 얼만큼이든 상관없이 고정된 길이의 코드로 반환시켜주는 함수다. 그리고 이렇게 계산하는 알고리즘을 hash algorithm 이라고 한다. (참고로 hash 는 가변 길이의 데이터를 고정길이로 환산한 값을 의미한다.)

Hash Function

아주 간단한 hash algorithm 은 내부 buckets 이라 불리는 데이터 저장소의 사이즈만큼 나눈 나머지(나머지는 무조건 나누는 수 이하의 값이 나온다.)를 index 로 쓰는 것이다. 

const bucketSize = 3;

hash_function(data) {
	const index = data % bucketSize;
    
	return index;
}


hash_function(24) = 24%3 = 0
hash_function(20) = 20%3 = 2
hash_function(16) = 16%3 = 1

문제는 아래 같이, 다른 데이터인데 같은 index 값이 나오는 경우가 있다. 이런 상황을 Collision 이라고 한다. 

hash_function(15) = 15%3 = 0
hash_function(21) = 21%3 = 0

 

Collision

Collision 이 발생하면 대표적으로 두 가지 해결책을 쓴다. 첫번째는 공간을 같이 공유하는 것이고 두번째는 비어있는 다른 공간에 넣는 것이다.

 

해결법1. Chaning

Collision 이 발생한 데이터들이 공간을 같이 공유한다. 보통 Linked List 로 선언된다. 검색을 하는 경우 해당 index 로 접근하고 그 공간에서 선형검색을 한다. 따라서 해시테이블의 효율은 평균 O(1) 이지만, 최악의 경우 O(n) 이 된다.

 

해결법2. Open Addressing

비어있는 다른 공간을 찾아 넣는다. 비어있는 공간을 찾는 방법은 아래 세 가지가 있다.

• Linear Probing : 바로 다음 칸에 넣는다. 그 칸이 비어있지 않다면 그 다음 비어있는 칸을 찾는다. 검색하는 경우 key 로 환산한 index 에 접근해서, 검색하려는 데이터가 아니라면 다음칸을 검색한다.
• Quadratic probing : Linear Probing 은 +1 칸을 찾는데, Quadratic 은 1^2칸, 2^2칸, 3^2 칸과 같이 제곱수만큼 차이나는 칸을 탐색해 비어있는 곳에 넣는다. 이 경우 같은 index 로 환산된 데이터들의 이동폭이 같아지는 클러스터링 문제가 생긴다.
• Double hashing probing : 클러스터링 문제를 해결하기 위해 해시 함수를 2개 둔다. 하나는 index값 환산용이고, 다른 하나는 Collision 발생 시 비어있는 칸을 찾는 데 사용할 칸수를 계산하는 함수다. 즉, h2(key) 만큼 이동하며 비어있는 칸을 찾는다.

 

좋은 Hash Altorithm 이란...

Collision 이 너무 자주 일어나서 데이터가 한 공간에만 집중되면 해시 테이블의 효율이 떨어질 것이다. 그러므로 Collision 이 덜 발생할 수 있도록 hash algorithm 을 잘 짜야한다.(key-index 가 1:1로 나오는 완벽한 알고리즘은 하늘의 별따기다...) 이미 여러 프로그래밍 언어가 hash table 을 지원하고 있고, 똑똑한 사람들이 만든 hash algorithm 들이 많으니 참고하면 좋을 것이다.

 

해시테이블 vs 배열

해시 테이블은 내부적으로 배열과 같은 구조이다. hash_function(key) 을 통해 환산된 index 로 데이터에 바로 접근하고, 내부 데이터 공간의 사이즈가 정해져 있다. 그러나 배열의 index 는 0으로 시작하는 정수이므로 value 와 연관관계가 없어서 value 를 찾으려면 공간을 하나하나 탐색해야 한다. 해시 테이블은 value 와 관련있는 key 로 바로 접근할 수 있기 때문에 배열보다 탐색이 더 빠르다.

 

해시 테이블 Resize

아까 언급했듯 해시 테이블의 Bucket 의 사이즈는 미리 정해진다. 정해진 사이즈의 공간을 효율적으로 쓰고싶을 때 해시테이블 자료구조를 이용하면 좋다. 그러다 입력되는 데이터의 양이 더 많아져서 공간이 부족한 경우가 생기는데, 이럴 때 해시 테이블의 사이즈를 늘리는 방법이 있다. 보통 일정 개수 이상(보통 75%정도 차면) 이 되면 버킷 사이즈를 2배로 늘린다. 0.75 수치를 load factor 라고 한다.