[Data Structure] Hash Table

* Hash Table
해시테이블은 배열과 연결리스트의 장점을 취한 자료구조이다. 키-밸류 쌍의 자료를 저장한다. 배열과 유사한 구조로 각 칸별로 인덱스가 있다. 그 칸에 자료를 저장할 수 있다. 연결 리스트를 이용해 한 칸에 여러 개의 자료를 저장할 수 있다. 

 

* Hash Function

해시함수는 특정 키를 받으면 이를 일정한 규칙(함수)을 통해 해시코드를 만들어낸다.

2. 주어진 key 에 항상 같은 값을 반환

3. 무엇도 저장하지 않고, 그때그때 값을 줌

해시함수의 역할은 자료를 알맞게 구분해 해시테이블에 배분시키는 것이다. 따라서 해시함수가 얼마나 고르게 자료를 해시테이블에 배분하는지가 해시함수 알고리즘을 짤 때 가장 중요한 사항이다. 

* 예시

candy : sweet 이라는 자료가 있다고 가정하자. 내가 원하는 것은 candy 라는 키를 넣었을 때, sweet 이라는 밸류가 나오는 것이다. 해시테이블의 배열의 길이는 총 8칸으로 각 칸은 0부터 7까지의 인덱스를 가지고 있다고 가정한다. 해시테이블을 이용해 자료를 정리한다고 할 때, 다음과 같은 과정을 거친다. 

 

 

먼저 키(candy)를 해시함수에 집어 넣는다. 해시함수는 알고리즘을 바탕으로 키마다 다른 인덱스값을 부여한다. 이 경우에서는 해시함수를 통해 0~7 중 하나의 값을 받게 될 것이다. 이 케이스에서는 6을 받게 되었다고 가정한다. 따라서 인덱스 6에 해당하는 일곱 번째 칸에 밸류인 sweet을 집어넣는다. 

 

그런데, 자료의 양이 많아 여덟 칸이 부족하면 어떨까. 혹은 해시 함수의 알고리즘이 잘못 짜여저 서로 다른 키들이 같은 인덱스를 갖게 된다면 어떻게 될까. 예를 들어 lemon : sour 라는 자료를 넣었을 때, 해시함수를 통해 인덱스 6을 부여받았다고 가정해보자. 이 경우, 이미 인덱스 6에는 sweet 이 들어 있으므로 충돌이 발생한다. (collision) 

 

 

이를 해결하기 위해 사용되는 것이 Bucket 이다. 동일한 인덱스 값을 갖는 자료들은 모두 동일한 Bucket에 담긴다. 이 경우 sweet과 sour가 모두 동일한 bucket 안에 담겨 있다. 복수의 자료를 연결리스트처럼 자료를 이어서 붙여주는 것이 해시테이블의 특징이다.  먼저 Tuple을 이용해 키와 배열을 짝지어 이어준다. 그리고 이 Tuple 들을 Bucket에 연결리스트처럼 이어준다. 

 

* 장점

해시테이블을 이용해 자료를 정리하면 자료를 검색하는 속도가 굉장히 빨라진다. 같은 키를 받으면 해시함수는 항상 같은 인덱스를 반환한다. 따라서 자료의 키를 알고 있다면 자료를 다 볼 필요 없이 해당 인덱스에 있는 자료들만을 확인하면 된다. 다만 해시함수의 알고리즘이 자료를 고르게 분배하지 못한다면 그만큼 해시테이블의 효율성도 줄어든다. 

 

* Resizing

주어진 해시테이블에 비해 데이터가 너무 많을 경우, 혹은 너무 적을 경우 해시테이블은 리사이징된다.

 

보통 자료가 해시테이블의 75%이상이 넘어갈 때 해시테이블의 길이는 두 배가 되며, 25% 미만일 때 1/2 으로 리사이징된다. 이 경우, 데이터들은 다시 해시함수에 들어가 인덱스값을 새로 할당받는다 (rehash)

 

* Reference : 엔지니어대한민국 (https://www.youtube.com/watch?v=Vi0hauJemxA&t=304s)