[자료구조] HashTable

HashTable(이하 해시테이블)은 데이터를 저장하고 빠른 검색을 하기위한 자료구조이다. 해시테이블에 데이터를 저장할때 키 값을 간단한 계산을 거쳐 인덱스로 만들고 해당 인덱스에 데이터를 저장한다.

💡 해싱
해시함수를 이용해 해시값을 만드는 과정 자체를 일컫는 말이다. 만들어진 값을 해시(값)이라고 부른다.

💡 해시함수
키를 이용해 인덱스로 만드는 알고리즘을 해시함수라고 부른다. 해시함수는 단방향 암호화 기법으로 복호화가 불가능한 기법이다. 따라서 간단한 매커니즘을 가지고 있다.

💡 해시충돌
해싱을 통해 생성된 인덱스가 중복되는 경우가 발생할 수 있다. 이를 해시충돌이라고 부르며 이러한 해시 충돌을 해결하기 위해 여러가지 메커니즘이 존재한다.

해시테이블은 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다는 장점을 가지고 있다. 또한 데이터 검색, 삽입, 삭제연산은 모두 O(1)의 시간복잡도를 가진다. 하지만 해시충돌이 여러번 발생하거나 해싱하고자하는 문자열의 길이에 따라 시간복잡도는 달라질 수 있다.

해시충돌 해결

비둘기 집의 원리(유한한 공간에 무한한 수의 입력값을 저장할때 반드시 2개이상의 값을 가지는 공간이 존재한다)에 의해 해시충돌은 필연적이라고 볼 수 있다. 충돌이 일어난다면 해결하는 방법이 필요한데, 이를 위해 해시 충돌 알고리즘이 사용된다. 해시 충돌 알고리즘에는 대표적으로 체이닝과 개방주소법이 존재하다.

1. 체이닝(Chaining)
   • 해시충돌 시 모두 하나의 해시값에 연결리스트에 담아 관리하는 방법
   • 검색 시 연결리스트에서 원소들을 선형으로 탐색하므로 O(n)의 복잡도가 나올 수 있다.
2. 개방 주소법(Open Addressing)
   • 충돌 시 다음 위치를 찾아서 데이터를 저장하는 방법
   • 선형탐색 - 다음 위치를 선형적으로 탐사
   • 제곱탐색(이차원) - 다음 위치를 제곱수열을 이용해 탐사
   • 이중해싱 - 이동 폭을 다른 해시함수를 통해 찾음

🤔 체이닝과 개방주소법 비교
공간 내 밀도가 높아진다면 충돌빈도가 높아지면서 개방주소법이 체이닝에 비해 느려질 수도 있다.

🤔 해시테이블의 단점
해시테이블은 일반적으로 배열의 형태로 구현되어진다. 따라서 미리 어느정도 미리 고정된 크기의 배열을 만들어 놓기 때문에 저장할 데이터가 적을땐 공간이 낭비될 수 있다는 단점이 존재한다. 이러한 문제점으로 메모리 공간이 중요한 경우에는 균형이진탐색트리를 이용하기도 한다.

해시테이블을 사용하는 예 - 주소록