[CS][Data Structure] 해시테이블 (Hash Table)

해시테이블이란?

해시테이블은 키-값 쌍을 저장하고 검색하는 데 특화된 자료구조입니다. 키를 사용하여 값을 빠르게 검색할 수 있도록, 해시 함수를 이용해 키를 인덱스로 변환하여 값을 저장합니다.

이 과정에서 해시 충돌이 일어날 수 있는데 이를 해결하기 위해 개방 주소법이나 폐쇄 주소법을 사용할 수 있습니다.

※ 해시 충돌 : 해시테이블에서 서로 다른 두 개의 키가 같은 해시 함수 값을 가지는 상황을 의미합니다.

해시테이블 작동 원리

1. 해시 함수 : 키를 인덱스로 변환하기 위해 해시 함수를 사용합니다. 해시 함수는 키의 데이터를 정수 형태의 해시 값으로 변환하여 테이블 내 값의 위치를 저장합니다.
2. 해시 충돌 해결
   1. 개방 주소법 : 충돌이 발생한 경우, 빈 슬릇 발견할 때 까지 인덱스를 늘려 충돌을 해결하는 방식
   2. 폐쇄 주소법 : 충돌이 발생한 경우, 해당 인덱스에 연결 리스트를 사용하여 값을 저장하는 방식

해시테이블 장점

1. 일반적으로 삽입, 삭제, 조회 시 평균적으로 O(1)의 시간복잡도를 가집니다.
2. 키-값 쌍을 기반으로 한 연산에 매우 효율적입니다.

해시테이블 단점

1. 해시 충돌이 발생할 경우 시간 복잡도가 악화될 수 있습니다.

해시테이블 활용

데이터베이스

DBMS에서 인덱싱을 위한 자료구조로 활용합니다.

캐싱

웹 프록시나 웹 브라우저에서 URL과 관련된 데이터를 빠르게 검색할 때 사용합니다.

집합 구현

중복을 허용하지 않는 자료구조(Set)를 구현할 때 사용합니다.