해시 탐색 알고리즘이란?

오늘은 탐색 알고리즘 중 하나인 해시 탐색에 대해 알아보려고 한다

참고로 해시 탐색은 이름에서 알 수 있듯이 해시 테이블(해시 맵)을 사용하여 탐색해서 해시 탐색이라고 이름이 붙여졌다

해시 탐색이란?

해시 탐색이란 키를 값에 연결시켜 빠르게 검색을 수행할 수 있도록 도와주는 기법에 알고리즘으로 이를 위해 보통 일명 해시 테이블(해시 맵)을 사용하여 이루어지며

해시 테이블(해시 맵)은 키를 값과 매핑시켜주기 때문에 탐색 시 로그 시간 복잡도가 O(1)로 상수 시간 내에서 데이터를 탐색할 수 있는 매우 빠른 탐색 성능을 가진 알고리즘이다

해시 탐색의 작동 방식

이러한 해시 탐색은 다음과 같은 방식으로 작동한다

1. 해시 함수가 각 키를 받아 고유한 인덱스를 생성한다 (해당 인덱스는 해시 테이블에 값을 저장하거나 검색할 때 사용됨)
2. 생성된 인덱스에 값을 저장하고 이 인덱스를 통해 데이터에 접근한다
3. 검색 시 원하는 키를 해시 함수에 넣어 인덱스를 얻고 이를 사용하여 해시 테이블(해시 맵)에서 값을 찾는다

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 바나나를 찾을 때 해시 탐색 알고리즘을 사용한다고 했을 때

주어진 해시 테이블(해시 맵) :

1: "사과",
3: "바나나",
5: "체리"

첫 번째 진행:

키 3을 해시 함수를 통해 특정 인덱스를 생성 -> 해당 인덱스를 통해 "바나나"에 즉시 접근

이와 같은 과정을 통해서 해시 탐색은 주어진 값을 찾게 된다

해시 탐색의 장단점

마지막으로 해시 탐색 알고리즘에 장단점을 알아보자

장점:

1. 일반적인 경우 상수 시간인 O(1)의 시간 복잡도로 매우 빠르게 데이터에 접근할 수 있다
2. 키와 값의 쌍으로 데이터를 저장하므로 데이터 관리가 직관적이고 용이하다

단점:

1. 다른 키가 동일한 해시 값을 가지는 상황에서 이를 해결하는 알고리즘들이 있으나 구현이 복잡하거나 추가 메모리를 요구하기도 한다
2. 해시 테이블의 크기는 데이터보다 커야 효율적인데 이로 인해 메모리 낭비가 발생할 수 있다