해쉬 테이블(Hash Table)

해싱(Hashing)이란, 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업이다.

해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블이라고 한다.

이진 탐색 트리나 배열에 비해서 빠른 속도로 탐색/삽입/삭제가 가능하다.

 

해시함수를 사용하여 변환한 값을 index로 삼아, key-value를 저장한다.

기본연산으로는 Search, Insert, Delete가 있다.

 

● Direct Address Table

키 값을 주소(인덱스)로 사용하는 테이블이다.

- 장점

탐색, 삽입, 삭제가 O(1)에 가능하다.

 

- 한계점

최대 키 값을 알고 있어야 한다.

키 값이 퍼져있다면 메모리 낭비됨.

 

● Hash Table

해쉬함수를 이용해 특정 해쉬값을 알아내고 이를 인덱스로 변환하여 해당 위치에 키-데이터 저장하는 자료구조이다.

이 때 충돌의 문제가 생긴다. (다른 값에 대해 같은 해쉬값이 나옴)

키의 개수를 K, 해쉬테이블의 개수를 N이라 할 때 적재율은 K/N이다.

적재율이 1 초과, 즉 K > N이면 충돌이 필연적으로 발생한다.

 

만약 충돌이 발생하지 않는 경우 해시테이블의 연산은 O(1) 이지만

충돌이 발생할 때 최악의 경우에는 O(K)만큼 걸리게 된다.

충돌을 최대한 줄여서 연산속도를 높이는 것이 해쉬테이블의 핵심인데, 이 때 해쉬 함수를 구현하는 데 필요한 해쉬알고리즘이 중요하다. 

 

해쉬 테이블의 충돌을 완화하는 방법은 2가지가 있는데, 자세한 것은 아래 링크에 나와 있다.

[DS] 해쉬 테이블(Hash Table)이란? - 배하람의 블로그

해쉬테이블은 언어에 따라서 HashMap이라고도 불리며,

파이썬에서는 Dictionary와 Set이 해쉬테이블을 기반으로 구현되어 있다. (따라서 둘 다 연산속도 O(1))

C++ 의 경우에는 트리 기반이라 Set, Map 둘 다 O(logN) 이다.